Guy's Conjecture

Guy's conjecture, which has not yet been proven or disproven, states that the graph crossing number for a complete graph  is

(1)

where  is the floor function, which can be rewritten

(2)

The values for , 2, ... are then given by 0, 0, 0, 0, 1, 3, 9, 18, 36, 60, 100, 150, 225, 315, 441, 588, ... (OEIS A000241).

Guy (1972) proved the conjecture for , a result extended to  by Pan and Richter (2007).

It is known that

(3)

(Richter and Thomassen 1997, de Klerk et al. 2007, Pan and Richter 2007).

REFERENCES

Brodsky, A.; Durocher, S.; and Gethner, E. "The Rectilinear Crossing Number of  Is 62." 22 Sep 2000.

 http://arxiv.org/abs/cs/0009023.de Klerk, E.; Pasechnik, D. V.; and Schrijver, A. "Reduction of Symmetric Semidefinite Programs Using the Regular -Representation." Math Program. 109, 613-624, 2007

.de Klerk, E.; Maharry, J.; Pasechnik, D. V.; Richter, R. B.; Salazar, G. "Improved Bounds for the Crossing Numbers of  and ." 2004.

 https://arxiv.org/pdf/math/0404142.pdf.Guy, R. K. "The Crossing Number of the Complete Graph." Bull. Malayan Math. Soc. 7, 68-72, 1960.

Guy, R. K. "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.

Pan, S. and Richter, R. B. "The Crossing Number of  is 100." J. Graph Th. 56, 128-134, 2007.

Sloane, N. J. A. Sequence A000241/M2772 in "The On-Line Encyclopedia of Integer Sequences."