CROSSED LINES IN THE BRICK FACTORY.
O ne of the charms of mathematics is how some very simple problems can baffle the best brains in the world for centuries. Examples include Fermat’s last theorem, Kepler’s conjecture and the four-color conjecture, all of which have been solved by mathematicians only in the past few decades. The four-color conjecture in particular attracted a lot of attention from recreational mathematicians, and it was in some ways a pity when it was finally proved, because a source of apparently endless fun had dried up. Given all the recent progress, it might seem that there are no interesting challenges left for the amateur to have a go at—but this is not the case, as we shall see.
First of all , a few words about the four-color conjecture, which was originally . posited about 150 years ago. The conjecture states that only four colors are needed in any two-dimensional map to ensure that no adjacent regions are colored the same. It was proved with computer assistance in 1976 by Kenneth Appel and Wolfgang Haken of the University of Illinois. The four-color theorem, as it is now called, belongs to the of branch of mathematics known as graph theory. A graph is a collection of in “nodes,” represented by dots, joined by “edges,” represented by lines. A two-dimensional map can be drawn as a graph—simply mark a node for each region on the map and draw edges between the nodes that represent adjacent regions. So the four-color problem can be rephrased as a question about coloring the nodes of the appropriate graph.
Graph theory is a source of numerous problems that are easy to state but tricky as hell to prove. Many such problems concern the crossing number of a graph the smallest number of times that two edges cross each other for a given number of nodes. (The edges must cross each other at isolated points.) In 1970 mathemati-cians Paul Erdös and Richard Guy wrote: “Almost all questions one can ask about crossing numbers remain unsolved.” That remark is equally true today. It is very hard to prove much about crossing numbers, hut recreational mathematicians can get a lot of pleasure from experimenting with various graphs and trying to reduce the number of crossings. It is conceivable that such experimentation might disprove some outstanding conjectures by yielding a graph with a crossing number that is less than the expected value.
Graphs with a crossing number of zero are fully explained by Kuratowski’s theo-rem which was proved by Polish mathematician Kazimierz Kuratowski. Such graphs are planar—the edges connecting the nodes do not cross one another at all.
Consider the first graph on the photo following, in which 10 edges connect 10 nodes. The edges cross each other four times, but in fact the graph is planar because the edges and nodes can he moved around so that the nodes form a ring and all the crossings are eliminated. This graph is called a cycle of 10 nodes and is denoted hy the symbol C10. Similar graphs with n nodes are called C-n..
Now consider the second graph, which is called a complete graph with five nodes. The 10 edges in this graph join each node to all the others. The graph is denoted by the symbol K5, and analogous complete graphs for n nodes are called Kn. K5 is not planar—no matter how the nodes and edges are rearranged, there will always he at least one crossing. Therefore, K5 has a crossing number of one.
The third graph is an example of a complete bipartite graph. It has two sets of three nodes each, and each node in one set is joined to all the nodes in the other set. The symbol of this graph is K3,3; it also has a crossing number of one. Similar bipartite graphs can he defined: if there are m nodes in one set and n nodes in the other, the graph is denoted by Km,n.
The concept of crossing numbers arose in 1944, when Hungarian mathematician Paul Turin was working in a brick factory outside Budapest. The factory had a number of kilns where the bricks were baked and a number of storage yards. Railroad tracks ran from each kiln to each yard. Workers put the bricks onto a small truck, pushed it along the rails to a yard and then unloaded it. This task was relatively easy except where one set of rails crossed another. At the crossings the truck would often jump the rails, and the bricks would fall out.
An engineer probably would have considered how to redesign the crossings. Turin, being a mathematician, wondered how to create as few crossings as possible by redesigning the layout of the rails. After a few days he realized that there were unnecessary crossings in this particular factory. But the general problem continued to intrigue him. With m kilns and n storage yards, and assuming that every kiln has rails to every yard, the problem can he stated as: find the crossing number for all complete bipartite graphs Km,n.
The problem remains unsolved. (Since 1944) Nadine C. Myers of Hamlinc University recently noted in Mathematics Magazine (December 1998) that crossing numbers are known only for graphs with small numbers of nodes: complete graphs Kn when n < 10, and complete bipartite graphs Km,n when 3 S m S 6. Very little is known about graphs with greater numbers of nodes.
Still another type of graph is the rectangular grid on a torus, ( shown in the illustration below)
Two families of circles appear in this graph: eight vertical circles with seven nodes
each (denoted by the symbol C7 and seven horizontal circles with eight nodes each (C8). These circles can he drawn on the surface of a tortis (which is the mathematical term for a doughnut) so that no crossings occur: the circles intersect only at the nodes. But when this graph—C7 x C8 —is projected onto the plane, five crossings occur for each of the eight vertical circles, yielding a total of 40 crossings.
The same kind of projection can he carried out with m horizontal circles and n vertical ones, where we follow the convention that m S n. We find that each vertical circle intersects the innermost and outermost horizontal circles just once, at a node. Each vertical circle intersects the other m - 2 horizontal circles twice—once at a node, which represents a real intersection on the torus, and once between nodes, which is a result of projecting the graph onto the plane. So each vertical circle contributes m - 2 crossings, and the graph has a total of (m - 2)n crossings.
It is widely believed that this number represents the fewest crossings possible for such a torus-grid graph; in other words, the crossing number of Cm x Cn is (m-2)n Yet this (m,n) conjecture has never been proved. It is known to he true when 3 Sm S 6 and when m=n=7. .The smallest unproved case is C7 x C8, for which the conjectured crossing number is 40. Can you find a way to draw the graph with 39 or fewer crossings? If so, the (m,n) conjecture would he proved false. It may seem astonishing, hut this problem has defied the combined brainpower of the world’s mathematicians for years.
In 1997 Gclasio Salazar of Carleton University in Ottawa proved that if the crossing number of C x C is less than (— 2)n, it cannot he much less. Never- theless, Salazar’s theorem leaves room for the possibility of a crossing number below the conjectured value. The (m,n) conjecture could very well turn out to be he false, which would explain why it has been so hard to prove for so long by so many.. Or the conjecture could he like Fermat’s theorem, Kepler’s conjecture or the four-color conjecture: true but hard to prove!
SCIENTIFIC AMERICA, by: Ian Stewart
June 1999, Mathematical Recreations, pg. 94-96
Church of the Science of God
La Jolla, California 92038-3131
© Church of the Science of GOD, 1993