This site is supported by donations to The OEIS Foundation.



Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000241 Crossing number of complete graph with n nodes.
(Formerly M2772 N1115)
0, 0, 0, 0, 0, 1, 3, 9, 18, 36, 60, 100, 150, 225, 315, 441, 588 (list; graph; refs; listen; history; text; internal format)



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.

The values for n >= 13 are probably only conjectural.

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

It appears that a(n)=C(floor(n/2),2)*C(floor((n-1)/2),2). [Paul Barry, Oct 02 2008]

From Paul Barry, Oct 02 2008: (Start)

We conjecture that this sequence is given by one half of the third coefficient of the denominator polynomial of the n-th convergent to the g.f. of n!, in which case the next numbers are 784,1008,1296,1620, 2025, 2475,...

Essentially sum{k=0..n, (-1)^(n-k)*floor(k/2)*ceiling(k/2)*floor((k-1)/2)*ceiling((k-1)/2)/2}. (End)

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]


Á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

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.

R. K. Guy, The crossing number of the complete graph, Bull. Malayan Math. Soc., Vol. 7, pp. 68-72, 1960.

Shengjun Pan and R. Bruce Richter, "The Crossing Number of K_11 is 100", J. Graph Theory 56 (2) (2007) 128-134.

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.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

C. Thomassen, Embeddings and minors, pp. 301-349 of R. L. Graham et al., eds., Handbook of Combinatorics, MIT Press.


Table of n, a(n) for n=0..16.

Drago Bokal, Gasper Fijavz and David R. Wood, The Minor Crossing Number of Graphs with an Excluded Minor, math.CO/0609707.

J. Dolan et al., su(3) and Zarankiewicz's conjecture

P. Erdos and R. K. Guy, Crossing Number Problems The American Mathematical Monthly, Vol. 80, No. 1. (1973), pp. 52-58.

Paul C. Kainen, On a problem of P. Erdos, J. Combinatorial Theory 51968 374--377. MR0231744 (38 #72)

Marc Lackenby, The crossing number of composite knots, Aug 25 2009. [From Jonathan Vos Post, Aug 26 2009]

D. McQuillan and R. B. Richter, A parity theorem for drawings of complete and bipartite graphs, Amer. Math. Monthly, 117 (2010), 267-273.

A. Owens, On the biplanar crossing number, IEEE Trans. Circuit Theory, 18 (1971), 277-280.

Thomas L. Saaty, On polynomials and crossing numbers of complete graphs, J. Combinatorial Theory Ser. A 10 (1971), 183--184. MR0291013 (45 #107)

T. L. Saaty, The Minimum Number Of Intersections In Complete Graphs

Eric Weisstein's World of Mathematics, Graph Crossing Number.

Eric Weisstein's World of Mathematics, Guy's Conjecture.

E. Weisstein, Zarankiewicz's Conjecture.html


a(n) ~ n^4/64 (Guy, Kainen)

Empirical g.f.: -x^5*(1+x+x^2)/(x+1)^3/(x-1)^5, which is the same as the conjectured formula of Guy and Saaty. [Simon Plouffe, Feb 06 2013]


a[n_] := 1/4*Floor[n/2]*Floor[(n-1)/2]*Floor[(n-2)/2]*Floor[(n-3)/2]; Table[a[n], {n, 0, 16}] (* Jean-François Alcover, Feb 06 2013, after R.K. Guy and Thomas Saaty's conjectured formula *)


It is not known if A000241 and A028723 agree. Cf. A007333, A014540, A030179.

Cf. A121021, A191928.

Sequence in context: A246695 A132920 A127645 * A028723 A213291 A057578

Adjacent sequences:  A000238 A000239 A000240 * A000242 A000243 A000244




N. J. A. Sloane.


Bokal et al. link from Jonathan Vos Post, Dec 08 2006



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

Content is available under The OEIS End-User License Agreement .

Last modified December 22 02:03 EST 2014. Contains 252326 sequences.