The Crossing Number of Cm X Cn: A Reluctant Induction
Nadine C. Myers · Mathematics Magazine · 1998
Even a fool, remarked Paul Erdo's in one of his many lectures, ask questions that the wisest man cannot answer. This statement is true for many areas of mathematics-perhaps nowhere more than in graph theory. The four-color theorem, proved more than a century after it was proposed, illustrates Erdo's's point. Another example is Turan's Brick Factory Problem. Although it was thought for some years to have been solved, flaws in the proof were discovered nearly twenty years later, and it remains open today. In this article, we explore another combinatorial problem, one that is simple to state and would seem to be provable by induction, but that has been found to be tantalizingly difficult. It is a crossing number problem that can be stated roughly as follows: For a rectangular grid on a torus, is there a planar drawing of this graph that has fewer crossings than the one shown in FIGURE 1? Attempts to solve this