GRID MINORS OF GRAPHS ON THE TORUS

We show that any graph G embedded on the torus with face-width r great er-than-or-equal-to 5 contains the toroidal right perpendicular 2/3 le ft 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 c losed 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 Seymou r showing, for each graph H embedded on any compact surface S, the exi stence of a number rho(H) such that every graph G embedded on S with f ace-width at least rho(H) contains H as a minor. Our result implies th at for H = C(k) x C(k) embedded on torus, rho(H): = inverted right per pendicular 3/2 k inverted left perpendicular is the smallest possible value. Our proof is based on deriving a result in the geometry of numb ers. It implies that for any symmetric convex body K in R2 one has lam bda2(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 l ambda such that lambda . K contains i linearly independent integer vec tors. K is the polar convex body.) (C) 1994 Academic Press, Inc.