GRID MINORS OF GRAPHS ON THE TORUS

We show that any graph G embedded on the torus with face-width r greater-than-or-equal-to 5 contains the toroidal right perpendicular 2/3 left perpendicular-grid as a minor. (The face-width of G is the minimum value of \C and G\, where C ranges over all homotopically nontrivial closed curves on the torus. The toroidal k-grid is the product C(k) x C(k) of two copies of a k-circuit C(k.)) For each fixed r greater-than-or-equal-to 5, the value right perpendicular 2/3 r left perpendicular 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 rho(H) such that every graph G embedded on S with face-width at least rho(H) contains H as a minor. Our result implies that for H = C(k) x C(k) embedded on torus, rho(H): = inverted right perpendicular 3/2 k inverted left perpendicular 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 lambda2(K) . lambda1(K*) less-than-or-equal-to 3/2 and that this bound is smallest possible. (Here lambda(i) (K) denotes the minimum value of lambda such that lambda . K contains i linearly independent integer vectors. K* is the polar convex body.) (C) 1994 Academic Press, Inc.