The history of the crossing number of the complete graph

We have already introduced the first half of a paper by Lowell Beineke and Robin Wilson1, which traces the origins of the crossing number of a graph. After focusing on the brick factory problem, proposed by the Hungarian number-theoretist Paul Turán, the second half of the paper is devoted to the crossing number of the complete graph and the geometrical explorations of the British artist Anthony Hill.

Lacking of any formal training in higher mathematics, Anthony Hill described himself as a constructivist working as a geometric formalist and made his way to deserve an Honorary Research Fellow in the Department of Mathematics at University College, London.

Unaware of the brick factory problem (which wonders about the smallest possible number of rail crossings when connecting m kilns and n storage yards), Hill considered given a set of n points and wondered about the smallest possible number of crossings when joining by curves every pair of those points. In mathematical terms, the brick factory problem deals with the bipartite graph K_{m,n}, while this crossing-number problem deals with the complete graph K_{n}.

Credit: David Orden
Credit: David Orden

Figure 1 shows drawings of K_{n} for n\in\{4,5,6\} having, respectively, 0, 1, and 3 crossings. Indeed, it can be proved that there is no drawing with fewer crossings, so for those graphs the crossing number, denoted as cr(K_{n}) and defined as the smallest number of crossings in any possible drawing, is actually cr(K_{4})=0, cr(K_{5})=1, and cr(K_{6})=3. Furthermore, observe that in those drawings the curves which join the vertices are actually straight-line segments. Such an extra condition leads to a different problem, interesting on its own.

The problem of finding the crossing number of the complete graph has a more fuzzy history than its bipartite counterpart. It is such a natural question that several people might have attacked it before giving up, discouraged by its difficulty. In particular, Paul Erdős claimed in 1960 that he had already been thinking on the problem for at least 20 years (which might sound a bit strange, since he was well known for spreading open problems).

According to several unpublished notes and correspondence, it seems that the first serious investigations on the problem are due to Hill, around 1958. After consulting some colleagues about whether the problem was known, Hill performed a great deal of experimentation which allowed him to find drawings of K_{6} with 3 crossings (like the one in Figure 1), of K_{7} with 9 crossings, of K_{8} with 18 crossings, and of K_{9} with 36 crossings. Figure 2 shows part of Hill’s notes.

Credit: Beineke & Wilson (2010)
Credit: Beineke & Wilson (2010)

His idea was looking at diagonals of polygons, some inside and some outside. This can be checked in Figure 3, which shows Hill’s construction for K_{7} with the vertices placed on two dashed circles (note that the edges in this case are actually curves).

Credit: Beineke & Wilson (2010)
Credit: Beineke & Wilson (2010)

Such an idea led Hill to state, in the late 1950s, which is probably the first conjecture for the crossing number of the complete graph, with two cases according to the parity of n. Those two cases were later combined into a single formula by J. Blažek and M. Koman 2, who in addition proved Hill’s conjectured value to be actually an upper bound for the crossing number of the complete graph:

cr(K_n)\leq 1/4\cdot\lfloor n/2\rfloor \cdot \lfloor (n-1)/2\rfloor \cdot \lfloor (n-2)/2\rfloor \cdot \lfloor (n-3)/2\rfloor.

By the spring of 1959, Hill and his friend the American artist John Ernest had arrived at the above conjecture and approached some professional mathematicians about the problem. One of them suggested contacting Andrew Booth at Birkbeck College, University of London, who was a computer pioneer in the 1940s. In May 1961, H. P. Goodman, a student of Booth’s, wrote a letter to Nature 3 describing their attempts to solve this seemingly intractable problem using a computer:

This problem does not appear tractable analytically, so it was programmed for the University of London Mercury computer. The programme was written on the assumption that a minimum for n+1 points can be obtained by adding an extra point in a suitable place on a minimum solution [with m crossings] for n points. However, the computations have proved that this apparently natural assumption is false: Two different minimum configurations for n=7, m=9 were taken, and one led to the true minimum n=8, m=18, while the other led to n=8, m=19.

By December 1960, their computer had yielded the values of 60 for n=10 and 100 for n=11, results that were later been proved correct.

Hill had already communicated the problem to Proffessor Ambrose Rogers, from University College, when Richard Guy gave a seminar there in November 1959, attended by Hill. Hearing about the complete graph problem, probably via Rogers, Guy published the first paper on it4 in 1960. Around this time, Hill communicated his results to the graph-theorist Frank Harary, with whom he wrote a paper5 summarizing the progress on the problem.

But it was also Guy who, in a later paper6, proved that the conjecture does provide the right crossing numbers for n\leq 10. Actually, the conjecture is known both as the Harary-Hill conjecture or as Guy’s conjecture. Since then, 47 years were needed until Pan and Richter7 in 2007 extended the validity of the conjecture to n\leq 12

Credit: Beineke & Wilson (2010)
Credit: Beineke & Wilson (2010)

which is the current status of the crossing-number problem for the complete graph. Nevertheless, very recent results8 seem to have settled some particular cases and might have opened a door towards the resolution of the problem.

References

  1. Beineke L. & Wilson R. (2010). The Early History of the Brick Factory Problem, The Mathematical Intelligencer, 32 (2) 41-48. DOI:
  2. J. Blažek and M. Koman. A minimal problem concerning complete plane graphs, In: Theory of Graphs and Its Applications (ed. M. Fiedler), Czechoslovak Academy of Sciences (1964), 113–117.
  3. H. P. Goodman. The complete n-point graph, Letter to Nature,190, No. 4778 (27 May 1961), 840.
  4. Richard K. Guy. A combinatorial problem, Nabla (Bull. Malayan Math. Soc.) 7 (1960), 68–72.
  5. Frank Harary and Anthony Hill. On the number of crossings in a complete graph, Proc. Edinb. Math. Soc. (II) 13 (1962–63), 333–338.
  6. Richard K. Guy. Crossing Numbers of Graphs. In: Graph Theory and Applications: Proceedings of the Conference at Western Michigan University, Kalamazoo, Mich., May 10-13, 1972 (Ed. Y. Alavi, D. R. Lick, and A. T. White). New York: Springer-Verlag, pp. 111-124, 1972.
  7. Shengjun Pan and R. Bruce Richter. The crossing number of K_11 is 100, J. Graph Theory 56 (2007), 128–134. http://dx.doi.org/10.1002/jgt.20249.
  8. Bernardo M. Ábrego, Oswin Aichholzer, Silvia Fernández-Merchant, Pedro Ramos & Gelasio Salazar (2013). Shellable drawings and the cylindrical crossing number of K_n, arXiv:

Leave a reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>