|
Organizers |
Curves in the Plane and the Crossing Number of Cm×Cn
by
R. Bruce Richter
University of Waterloo
The crossing number cr(Cm×Cn) of the Cartesian product of two cycles has long been conjectured to be (m-2)n, for 3 <= m <= n. This is now known for m <= 7. The purpose of this talk is to indicate how generalizations of drawings of Cm×Cn have been used to prove these results.
The first generalization is a mesh. An (m, n)-mesh is a pair (C1, C2) of families of closed curves in the plane such that: (a) |C1|=m, |C2|=n; and (b) every curve in C1 intersects every curve in C2. Thus, there are mn ``forced'' intersections (corresponding to the vertices of Cm×Cn) and all the remaining intersections are ``crossings''. The main advantage to working with meshes is that in an (m, n)-mesh with fewest crossings, the curves are all necessarily simple. The main disadvantage is that they are too general - a (3, n)-mesh can have only n/2 crossings, while cr(C3×Cn)=n.
Between meshes and drawings of Cm×Cn are circular arrangements. An (m, n)-circular arrangement is an (m, n)-mesh (C1, C2) such that all curves in C1 meet all curves in C2 in the same cyclic order. That cr(C7×Cn)=5n is proved by showing that every (7, 7)-mesh has at least 35 crossings and then by induction on n >= m that every (7, n)-circular arrangement has at least 5n crossings.
Date received: November 28, 2000
Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cafp-35.