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
First of all , a few words about the 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 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 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 SOURCE: SCIENTIFIC AMERICA, by: June 1999, Mathematical Recreations, pg. 94-96 Return to the words of wisdom, science index..
Church of the Science of GodLa Jolla, California 92038-3131 (858)220-1604 © Church of the Science of GOD, 1993 |