Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.

Description

It is shown that for each \$t\$, there is a separator of size \$O(t sqrt{n})\$ in any \$n\$-vertex graph \$G\$ with no \$K_t\$-minor.

This settles a conjecture of Alon, Seymour and Thomas (J. Amer. Math. Soc., 1990 and STOC'90), and generalizes a result of Djidjev (1981), and Gilbert, Hutchinson and Tarjan (J. Algorithm, 1984), independently, who proved that every graph with \$n\$ vertices and genus \$g\$ has a separator of order \$O(sqrt{gn})\$, because \$K_t\$ has genus \$Omega(t^2)\$.

The bound \$O(t sqrt{n})\$ is best possible because every 3-regular expander graph with \$n\$ vertices is a graph with no \$K_t\$-minor for \$t=cn^{1/2}\$, and with no separator of size \$dn\$ for appropriately chosen positive constants \$c,d\$.

In addition, we give an \$O(n^2)\$ time algorithm to obtain such a separator, and then give a sketch how to obtain such a separator in \$O(n^{1+epsilon})\$ time for any \$epsilon > 0\$. Finally, we discuss several algorithm aspects of our separator theorem, including a possibility to obtain a separator of order \$g(t)sqrt{n}\$, for some function \$g\$ of \$t\$, in an \$n\$-vertex graph \$G\$ with no \$K_t\$-minor in \$O(n)\$ time.