This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000241 Crossing number of complete graph with n nodes.
(Formerly M2772 N1115)

%I M2772 N1115

%S 0,0,0,0,0,1,3,9,18,36,60,100,150

%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 Balko, Martin, 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 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. [From _Jonathan Vos Post_, Aug 26 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 Graphr</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.html</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

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 17 11:44 EDT 2019. Contains 328108 sequences. (Running on oeis4.)