|
%I M2772 N1115 #136 Apr 24 2024 12:48:14
%S 0,0,0,0,0,1,3,9,18,36,60,100,150,225,315
%N Crossing number of complete graph with n nodes.
%C It was conjectured by A. Hill in 1958 (see Guy 1960 and Harary-Hill 1963) that a(n) = floor(n/2)*floor((n-1)/2)*floor((n-2)/2)*floor((n-3)/2)/4 (see A028723). This is also sometimes referred to as Guy's conjecture. - _N. J. A. Sloane_, Jan 21 2015
%C Verified for n = 11, 12 by Shengjun Pan and R. Bruce Richter, in "The Crossing Number of K_11 is 100", J. Graph Theory 56 (2) (2007) 128-134.
%C Also the sum of the dimensions of the irreducible representations of su(3) that first occur in the (n-5)-th tensor power of the tautological representation. - James Dolan (jdolan(AT)math.ucr.edu), Jun 02 2003
%C From _Paul Barry_, Oct 02 2008: (Start)
%C Another version of the conjecture is that a(n)=C(floor(n/2),2)*C(floor((n-1)/2),2).
%C We conjecture that this sequence is also given by one half of the third coefficient of the denominator polynomial of the n-th convergent to the g.f. of n!.
%C (End)
%C From the Lackenby reference: "One of the most basic questions in knot theory remains unresolved: is crossing number additive under connected sum? In other words, does the equality c(K1#K2) = c(K1) + c(K2) always hold, where c(K) denotes the crossing number of a knot K and K1#K2 is the connected sum of two (oriented) knots K1 and K2? Theorem 1.1. Let K1, . . .,Kn be oriented knots in the 3-sphere. Then (c(K1) + . . . + c(Kn)) / 152 <= c(K1# . . . #Kn) <= c(K1) + . . . + c(Kn)." - _Jonathan Vos Post_, Aug 26 2009
%C From the Pan and Richter reference: 0.8594 Z(n) <= a(n) <= Z(n), where Z(n) is the conjectured formula (Richter and Thomassen 1997, de Klerk et al. 2007). - _Danny Rorabaugh_, Mar 12 2015
%C a(n) <= A028723(n) for n = 13-21, 23, 25, 27, and 29 based on crossing numbers equal to A028723(n) found using QuickCross. - _Eric W. Weisstein_, May 02 2019
%D Ábrego, Bernardo M.; Aichholzer, Oswin; Fernández-Merchant, Silvia; Ramos, Pedro; Salazar, Gelasio. The 2-Page Crossing Number of K_n. Discrete Comput. Geom. 49 (2013), no. 4, 747-777. MR3068573
%D E. de Klerk, D. V. Pasechnik, and A. Schrijver, "Reduction of Symmetric Semidefinite Programs Using the Regular *-Representation." Math Program. 109 (2007) 613-624.
%D Jean-Paul Delahaye, in Pour La Science, Feb. 2013, #424, Logique et Calcul. Le problème de la fabrique de briques. (The problem of the brick factory), in French.
%D R. K. Guy, The crossing number of the complete graph, Bull. Malayan Math. Soc., Vol. 7, pp. 68-72, 1960.
%D Harary, Frank, and Anthony Hill. "On the number of crossings in a complete graph." Proceedings of the Edinburgh Mathematical Society (Series 2) 13.04 (1963): 333-338.
%D T. L. Saaty, The number of intersections in complete graphs, Engrg. Cybernetics 9 (1971), no. 6, 1102-1104 (1972).; translated from Izv. Akad. Nauk SSSR Tehn. Kibernet. 1971, no. 6, 151-154 (Russian). Math. Rev. 58 #21749.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D C. Thomassen, Embeddings and minors, pp. 301-349 of R. L. Graham et al., eds., Handbook of Combinatorics, MIT Press.
%H Oswin Aichholzer, <a href="https://projects.cs.dal.ca/cccg2021/wordpress/wp-content/uploads/2021/08/CCCG2021.pdf">Another Small but Long Step for Crossing Numbers: cr(13) = 225 and cr(14) = 315</a>, Proceedings of the 33rd Canadian Conference on Computational Geometry (CCCG 2021).
%H Martin Balko, Radoslav Fulek, and Jan Kynčl, <a href="http://arxiv.org/abs/1312.3679">Crossing numbers and combinatorial characterization of monotone drawings of K_n</a>, arXiv preprint arXiv:1312.3679 [math.CO], 2013. Also Discrete Computat. Geom., 53 (2015), 107-143.
%H Drago Bokal, Gasper Fijavz and David R. Wood, <a href="http://arXiv.org/abs/math/0609707">The Minor Crossing Number of Graphs with an Excluded Minor</a>, arXiv:math/0609707 [math.CO], 2006.
%H J. Dolan et al., <a href="http://mathforum.org/epigone/sci.math.research/stroblequy">su(3) and Zarankiewicz's conjecture</a>
%H P. Erdős and R. K. Guy, <a href="http://www.jstor.org/stable/2319261">Crossing Number Problems </a>The American Mathematical Monthly, Vol. 80, No. 1. (1973), pp. 52-58.
%H James Grime and Brady Haran, <a href="https://www.youtube.com/watch?v=xBfAYxxRsjY">The Brick Factory Problem</a>, Numberphile video (2023).
%H Paul C. Kainen, <a href="http://dx.doi.org/10.1016/S0021-9800(68)80013-4">On a problem of P. Erdős</a>, J. Combinatorial Theory 51968 374--377. MR0231744 (38 #72)
%H Marc Lackenby, <a href="http://arxiv.org/abs/0805.4706">The crossing number of composite knots</a>, arXiv:0805.4706 [math.GT], 2009.
%H D. McQuillan and R. B. Richter, <a href="http://www.jstor.org/stable/10.4169/000298910X480117">A parity theorem for drawings of complete and bipartite graphs</a>, Amer. Math. Monthly, 117 (2010), 267-273.
%H A. Owens, <a href="http://dx.doi.org/10.1109/TCT.1971.1083266">On the biplanar crossing number</a>, IEEE Trans. Circuit Theory, 18 (1971), 277-280.
%H A. Owens, <a href="/A007333/a007333.pdf">On the biplanar crossing number</a>, IEEE Trans. Circuit Theory, 18 (1971), 277-280. [Annotated scanned copy]
%H Shengjun Pan and R. Bruce Richter, <a href="http://dx.doi.org/10.1002/jgt.20249">The Crossing Number of K_11 is 100</a>, J. Graph Theory 56 (2) (2007) 128-134.
%H R. B. Richter and C. Thomassen, <a href="http://www.jstor.org/stable/2974980">Relations Between Crossing Numbers of Complete and Complete Bipartite Graphs</a>, Amer. Math. Monthly 104 (1997) 131-137.
%H Thomas L. Saaty, <a href="http://dx.doi.org/10.1016/0097-3165(71)90024-0">On polynomials and crossing numbers of complete graphs</a>, J. Combinatorial Theory Ser. A 10 (1971), 183--184. MR0291013 (45 #107)
%H T. L. Saaty, <a href="http://www.pnas.org/content/52/3/688.full.pdf">The Minimum Number Of Intersections In Complete Graphs</a>, PNAS 1964 52 (3) 688-690.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CompleteGraph.html">Complete Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GraphCrossingNumber.html">Graph Crossing Number</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GuysConjecture.html">Guy's Conjecture</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ZarankiewiczsConjecture.html">Zarankiewicz's Conjecture</a>
%F a(n) ~ n^4/64 (Guy, Kainen).
%F Empirical g.f.: -x^5*(1+x+x^2)/(x+1)^3/(x-1)^5, which is the same as the conjectured formula of A. Hill. - _Simon Plouffe_, Feb 06 2013
%Y It is conjectured that this sequence coincides with A028723.
%Y Cf. A007333, A014540, A030179, A121021, A191928.
%K nonn,more,nice,changed
%O 0,7
%A _N. J. A. Sloane_
%E Bokal et al. link from _Jonathan Vos Post_, Dec 08 2006
%E Entry revised by _N. J. A. Sloane_, Jan 21 2015
%E Conjectured data values deleted by _Eric W. Weisstein_, May 01 2019
%E a(13) and a(14) computed by O. Aichholzer and added by _Manfred Scheucher_, Apr 24 2024
| 