TOPICS
Search

Guy's Conjecture

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

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

Z(n)=1/4|_n/2_||_(n-1)/2_||_(n-2)/2_||_(n-3)/2_|,
(1)

where |_x_| is the floor function, which can be rewritten

Z(n)={1/(64)n(n-2)^2(n-4) for n even; 1/(64)(n-1)^2(n-3)^2 for n odd.
(2)

The values for n=1, 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 n<=10, a result extended to n<=12 by Pan and Richter (2007).

It is known that

0.8594Z(n)<=nu(K_n)<=Z(n)
(3)

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

See also

Complete Bipartite Graph, Complete Graph, Graph Crossing Number, Zarankiewicz's Conjecture

Explore with Wolfram|Alpha

References

Brodsky, A.; Durocher, S.; and Gethner, E. "The Rectilinear Crossing Number of K_(10) 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 K_(m,n) and K_n." 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 K_(11) is 100." J. Graph Th. 56, 128-134, 2007.Sloane, N. J. A. Sequence A000241/M2772 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Guy's Conjecture

Cite this as:

Weisstein, Eric W. "Guy's Conjecture." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GuysConjecture.html

Subject classifications