{"id":"arxiv/2611.00663","url":"https://arxiv.org/abs/2611.00663","tags":["math.CO","cs.DM"],"score":0,"title":"$K_h$-Minor-Free Graphs Have Balanced Separators of Size $O(h\\sqrt{n})$","domain":"math.CO","source":"arxiv","authors":["Jonathan Conroy","Hung Le","Jack Spalding-Jamieson"],"reviews":0,"subject":"math.CO","summary":"We show that every $K_h$-minor-free graph with $n$ vertices has a balanced separator of size $O(h\\sqrt{n})$ for any parameter $h \\in \\mathbb{N}$, resolving the conjecture posed by Alon, Seymour, and Thomas [AST90] in 1990. The proof is elementary, building on the combinatorial framework by Le [Le26]. A key new idea of the proof is the existence of a short hitting walk on vertex expanders: given $k$ large (not necessarily disjoint) subsets of vertices, there is a walk of length $O(k/ψ(G))$ hitting every subset, where $ψ(G)$ is the vertex expansion. This technical result substantially improves…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-31","reactions":{}}