Grid Minors of Graphs on the Torus

AbstractWe show that any graph G embedded on the torus with face-width r ≥ 5 contains the toroidal ⌊23r⌋-grid as a minor. (The face-width of G is the minimum value of |C∩G|, where C ranges over all homotopically nontrivial closed curves on the torus. The toroidal k-grid is the product Ck × Ck of two copies of a k-circuit Ck.) For each fixed r ≥ 5, the value ⌊23r⌋ is largest possible. This applies to a theorem of Robertson and Seymour showing, for each graph H embedded on any compact surface S, the existence of a number ρH such that every graph G embedded on S with face-width at least ρH contains H as a minor. Our result implies that for H = Ck × Ck embedded on torus, ρH ≔ ⌈32k⌉ is the smallest possible value. Our proof is based on deriving a result in the geometry of numbers. It implies that for any symmetric convex body K in R2 one has λ2(K)·λ1(K*) ≤ 32 and that this bound is smallest possible. (Here λi(K) denotes the minimum value of λ such that λ·K contains i linearly independent integer vectors. K* is the polar convex body.