A014540 -id:A014540 - cp's OEIS frontend

A298445 Triangle T(n,k) read by rows: number of n-node simple graphs with rectilinear crossing number k (k=0..A014540(n)).

1, 2, 4, 11, 33, 1, 142, 12, 1, 1, 822, 162, 39, 16, 1, 2, 1, 0, 0, 1, 6966, 3183, 1291, 559, 172, 82, 48, 12, 15, 8, 4, 1, 3, 0, 0, 1, 0, 0, 0, 1, 79853

Offset: 1

Eric W. Weisstein, Jan 19 2018

Computed up to n=8 using data provided by Geoffrey Exoo. (There appear to be some problems with n=9 data.)

			Triangle begins:
1
2
4
11
33, 1
142, 12, 1, 1
822, 162, 39, 16, 1, 2, 1, 0, 0, 1
6966, 3183, 1291, 559, 172, 82, 48, 12, 15, 8, 4, 1, 3, 0, 0, 1, 0, 0, 0, 1

Eric Weisstein's World of Mathematics, Rectilinear Crossing Number
Eric Weisstein's World of Mathematics, Simple Graph

Cf. A014540 (rectilinear crossing number for K_n).
Cf. A298446 (counts for simple connected graphs).
Cf. A307071 (number of simple graphs with crossing number 1).

T(n,0) = A005470(n).
T(n,1) = A307071(n).
kmax(n) = A014540(n).
T(n,kmax(n)) = 1 for n > 4.
Sum_{k=0..kmax(n)} T(n,k) = A000088(n).

Corrected by Eric W. Weisstein, Mar 28 2019

A298446 Triangle T(n,k) read by rows: number of n-node connected graphs with rectilinear crossing number k (k=0..A014540(n)).

Original entry on oeis.org

1, 1, 2, 6, 20, 1, 99, 11, 1, 1, 646, 149, 38, 15, 1, 2, 1, 0, 0, 1, 5974, 3008, 1251, 542, 171, 80, 47, 12, 15, 7, 4, 1, 3, 0, 0, 1, 0, 0, 0, 1, 71885

Offset: 1

Eric W. Weisstein, Jan 19 2018

Computed up to n=8 using data provided by Geoffrey Exoo. (There appear to be some problems with n=9 data.)

T(9,1) >= 71335. - Eric W. Weisstein, Mar 28 2019

			Triangle begins:
1
1
2
6
20,1
99,11,1,1
646,149,38,15,1,2,1,0,0,1
5974,3008,1251,542,171,80,47,12,15,7,4,1,3,0,0,1,0,0,0,1

Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Rectilinear Crossing Number

Cf. A014540 (rectilinear crossing number for K_n).

Cf. A298445 (counts for simple graph).

T(n,0) = A003094(n).
kmax(n) = A014540(n).
T(n,kmax(n)) = 1 for n > 4.
sum(k=0..kmax(n), T(n,k)) = A001349(n).

Corrected by Eric W. Weisstein, Mar 28 2019

A135515 Number of inequivalent drawings of the complete graph Kn on n vertices that attain the corresponding rectilinear crossing number (A014540).

Original entry on oeis.org

1, 1, 1, 3, 2, 10, 2, 374

Offset: 4

Don Pedro Esq. (info(AT)servierlaboratories.org), Feb 09 2008

Some lower bounds: a(13) >= 272, a(14) >= 2, a(15) >= 360, a(16) >= 7, a(17) >= 7532, a(18) >= 2, a(19) >= 069 and a(20) >= 4.

O. Aichholzer, F. Aurenhammer and H. Krasser, On the crossing number of complete graphs, Computing, 76:165-176, 2006. [alternative link]

A307891 Rectilinear crossing number A014540(n) - crossing number A000241(n) of complete graph on n nodes.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 0, 2, 2, 3, 4, 9, 6, 15, 14, 21, 22, 37, 30, 53, 52, 69, 74, 102, 96

Offset: 1

Ed Pegg Jr, May 03 2019

			For 8 nodes the crossing number is 18 and the rectilinear crossing number is 19.  The difference for 8 nodes is 1.  Thus a(8)=1.

Cf. A000241, A014540, A028723.

A030179 Quarter-squares squared: A002620^2.

Original entry on oeis.org

0, 0, 1, 4, 16, 36, 81, 144, 256, 400, 625, 900, 1296, 1764, 2401, 3136, 4096, 5184, 6561, 8100, 10000, 12100, 14641, 17424, 20736, 24336, 28561, 33124, 38416, 44100, 50625, 57600, 65536, 73984, 83521, 93636, 104976, 116964

Offset: 0

N. J. A. Sloane, Jan 10 2002

Conjectured to be crossing number of complete bipartite graph K_{n,n}. Known to be true for n <= 7.
If the Zarankiewicz conjecture is true, then a(n) is also the rectilinear crossing number of K_{n,n}. - Eric W. Weisstein, Apr 24 2017
a(n+1) is the number of 4-tuples (w,x,y,z) with all terms in {0,...,n}, and w,x,y+1,z+1 all even. - Clark Kimberling, May 29 2012

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

G. C. Greubel, Table of n, a(n) for n = 0..1000
G. Xiao, Contfrac.
Eric Weisstein's World of Mathematics, Complete Bipartite Graph.
Eric Weisstein's World of Mathematics, Graph Crossing Number.
Eric Weisstein's World of Mathematics, Rectilinear Crossing Number.
Eric Weisstein's World of Mathematics, Zarankiewicz's Conjecture.
Index entries for linear recurrences with constant coefficients, signature (2,2,-6,0,6,-2,-2,1).

Cf. A000241, A002620, A014540.

List([0..40], n-> (2*n^4 -2*n^2 +1 +(-1)^n*(2*n^2 -1))/32); # G. C. Greubel, Dec 28 2019

[(Floor(n^2/4))^2: n in [0..40]]; // G. C. Greubel, Dec 28 2019

seq( (2*n^4 -2*n^2 +1 +(-1)^n*(2*n^2 -1))/32, n=0..40); # G. C. Greubel, Dec 28 2019

f[n_]:=Floor[n^2/2]; Table[Nest[f,n,2],{n,5!}]/2 (* Vladimir Joseph Stephan Orlovsky, Mar 10 2010 *)
LinearRecurrence[{2,2,-6,0,6,-2,-2,1}, {0,0,1,4,16,36,81,144}, 40] (* Harvey P. Dale, Apr 26 2011 *)
Floor[Range[0, 30]^2/4]^2 (* Eric W. Weisstein, Apr 24 2017 *)

a(n) = (n^2\4)^2 \\ Charles R Greathouse IV, Jun 11 2015

[floor(n^2/4)^2 for n in (0..40)] # G. C. Greubel, Dec 28 2019

a(n) = floor(n^2/4)^2.
From R. J. Mathar, Jul 08 2010: (Start)
G.f.: x^2*(1+2*x+6*x^2+2*x^3+x^4) / ( (1+x)^3*(1-x)^5 ).
a(n) = 2*a(n-1) +2*a(n-2) -6*a(n-3) +6*a(n-5) -2*a(n-6) -2*a(n-7) +a(n-8). (End)
a(n) = (2*n^4 -2*n^2 +1 +(-1)^n*(2*n^2 -1))/32. - Luce ETIENNE, Aug 11 2014
Sum_{n>=2} 1/a(n) = Pi^4/90 + Pi^2/3 - 3. - Amiram Eldar, Sep 17 2023

A000241 Crossing number of complete graph with n nodes.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 3, 9, 18, 36, 60, 100, 150, 225, 315

Offset: 0

N. J. A. Sloane

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
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.
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
From Paul Barry, Oct 02 2008: (Start)
Another version of the conjecture is that a(n)=C(floor(n/2),2)*C(floor((n-1)/2),2).
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!.
(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
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
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

Á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
E. de Klerk, D. V. Pasechnik, and A. Schrijver, "Reduction of Symmetric Semidefinite Programs Using the Regular *-Representation." Math Program. 109 (2007) 613-624.
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.
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.
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.

Oswin Aichholzer, Another Small but Long Step for Crossing Numbers: cr(13) = 225 and cr(14) = 315, Proceedings of the 33rd Canadian Conference on Computational Geometry (CCCG 2021).
Martin Balko, Radoslav Fulek, and Jan Kynčl, Crossing numbers and combinatorial characterization of monotone drawings of K_n, arXiv preprint arXiv:1312.3679 [math.CO], 2013. Also Discrete Computat. Geom., 53 (2015), 107-143.
Drago Bokal, Gasper Fijavz and David R. Wood, The Minor Crossing Number of Graphs with an Excluded Minor, arXiv:math/0609707 [math.CO], 2006.
J. Dolan et al., su(3) and Zarankiewicz's conjecture
P. Erdős and R. K. Guy, Crossing Number Problems The American Mathematical Monthly, Vol. 80, No. 1. (1973), pp. 52-58.
James Grime and Brady Haran, The Brick Factory Problem, Numberphile video (2023).
Paul C. Kainen, On a problem of P. Erdős, J. Combinatorial Theory 51968 374--377. MR0231744 (38 #72)
Marc Lackenby, The crossing number of composite knots, arXiv:0805.4706 [math.GT], 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.
A. Owens, On the biplanar crossing number, IEEE Trans. Circuit Theory, 18 (1971), 277-280. [Annotated scanned copy]
Shengjun Pan and R. Bruce Richter, The Crossing Number of K_11 is 100, J. Graph Theory 56 (2) (2007) 128-134.
R. B. Richter and C. Thomassen, Relations Between Crossing Numbers of Complete and Complete Bipartite Graphs, Amer. Math. Monthly 104 (1997) 131-137.
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, PNAS 1964 52 (3) 688-690.
Eric Weisstein's World of Mathematics, Complete Graph
Eric Weisstein's World of Mathematics, Graph Crossing Number
Eric Weisstein's World of Mathematics, Guy's Conjecture
Eric Weisstein's World of Mathematics, Zarankiewicz's Conjecture

It is conjectured that this sequence coincides with A028723.

Cf. A007333, A014540, A030179, A121021, A191928.

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 A. Hill. - Simon Plouffe, Feb 06 2013

Bokal et al. link from Jonathan Vos Post, Dec 08 2006
Entry revised by N. J. A. Sloane, Jan 21 2015
Conjectured data values deleted by Eric W. Weisstein, May 01 2019
a(13) and a(14) computed by O. Aichholzer and added by Manfred Scheucher, Apr 24 2024

A006247 Number of simple arrangements of n pseudolines in the projective plane with a marked cell. Number of Euclidean pseudo-order types: nondegenerate abstract order types of configurations of n points in the plane.

Original entry on oeis.org

1, 1, 1, 2, 3, 16, 135, 3315, 158830, 14320182, 2343203071, 691470685682, 366477801792538

Offset: 1

N. J. A. Sloane

Also the number of nonisomorphic nondegenerate acyclic rank 3 oriented matroids on n elements. - Manfred Scheucher, May 09 2022

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

O. Aichholzer, Order Types for Small Point Sets
O. Aichholzer, F. Aurenhammer and H. Krasser, Enumerating order types for small point sets with applications, In Proc. 17th Ann. ACM Symp. Computational Geometry, pages 11-18, Medford, Massachusetts, USA, 2001. [Computes a(10)]
Stefan Felsner and Jacob E. Goodman, Pseudoline Arrangements, Chapter 5 of Handbook of Discrete and Computational Geometry, CRC Press, 2017, see Table 5.6.1. [Specific reference for this sequence] - _N. J. A. Sloane_, Nov 14 2023
J. Ferté, V. Pilaud and M. Pocchiola, On the number of simple arrangements of five double pseudolines, arXiv:1009.1575 [cs.CG], 2010; Discrete Comput. Geom. 45 (2011), 279-302.
Lukas Finschi, A Graph Theoretical Approach for Reconstruction and Generation of Oriented Matroids, A dissertation submitted to the Swiss Federal Institute of Technology, Zurich for the degree of Doctor of Mathematics, 2001.
Lukas Finschi, Homepage of Oriented Matroids
L. Finschi and K. Fukuda, Complete combinatorial generation of small point set configurations and hyperplane arrangements, pp. 97-100 in Abstracts 13th Canadian Conference on Computational Geometry (CCCG '01), Waterloo, Aug. 13-15, 2001.
Henry Förster, Philipp Kindermann, Tillmann Miltzow, Irene Parada, Soeren Terziadis, and Birgit Vogtenhuber, Geometric Thickness of Multigraphs is (exists in reals)-complete, arXiv:2312.05010 [cs.CG], 2023.
Jacob E. Goodman, Joseph O'Rourke, and Csaba D. Tóth, editors, Handbook of Discrete and Computational Geometry [alternative link], CRC Press, 2017, see Table 5.6.1. [General reference for 2017 edition of the Handbook] - _N. J. A. Sloane_, Nov 14 2023
J. E. Goodman and R. Pollack, Semispaces of configurations, cell complexes of arrangements, J. Combin. Theory, A 37 (1984), 257-293.
D. E. Knuth, Axioms and hulls, Lect. Notes Comp. Sci., Vol. 606.
Alexander Pilz and Emo Welzl, Order on order types, Discrete & Computational Geometry, 59 (No. 4, 2015), 886-922.
Manfred Scheucher, Hendrik Schrezenmaier, and Raphael Steiner, A Note On Universal Point Sets for Planar Graphs, arXiv:1811.06482 [math.CO], 2018.

Cf. A006248, A014540, A063852, A063666, A325595, A325628, A006245

Asymptotics: a(n) = 2^(Theta(n^2)). This is Bachmann-Landau notation, that is, there are constants n_0, c, and d, such that for every n >= n_0 the inequality 2^{c n^2} <= a(n) <= 2^{d n^2} is satisfied. For more information see e.g. the Handbook of Discrete and Computational Geometry. - Manfred Scheucher, Sep 12 2019

a(11) from Franz Aurenhammer (auren(AT)igi.tu-graz.ac.at), Feb 05 2002
a(12) from Manfred Scheucher and Günter Rote, Aug 31 2019
a(13) from Manfred Scheucher and Günter Rote, Sep 12 2019
Definition clarified by Manfred Scheucher, Jun 22 2023

A063542 Least number of empty convex quadrilaterals (4-gons) determined by n points in the plane.

Original entry on oeis.org

0, 1, 3, 6, 10, 15, 23, 32, 42, 51

Offset: 4

N. J. A. Sloane, Aug 14 2001

K. Dehnhardt. Leere konvexe Vielecke in ebenen Punktmengen. PhD thesis, TU Braunschweig, Germany, 1987.

O. Aichholzer and H. Krasser, The point set order type data base: a collection of applications and results, pp. 17-20 in Abstracts 13th Canadian Conference on Computational Geometry (CCCG '01), Waterloo, Aug. 13-15, 2001.
O. Aichholzer, R. Fabila-Monroy, T. Hackl, C. Huemer, A. Pilz, and B. Vogtenhuber. Lower bounds for the number of small convex k-holes. Computational Geometry: Theory and Applications, 47(5):605-613, 2014.
O. Aichholzer, R. Fabila-Monroy, T. Hackl, C. Huemer, A. Pilz, B. Vogtenhuber, A set of 12 points minimizing the numbers of convex 3-, 4-, and 5-holes.
O. Aichholzer, T. Hackl, and M. Scheucher, A set of 13 points minimizing the numbers of convex 3-, 4-, and 5-holes.
M. Scheucher, Counting Convex 5-Holes, Bachelor's thesis, Graz University of Technology, Austria, 2013, in German.

Cf. A063541 and A276096 for empty convex 3- and 5-gons (a.k.a. k-holes), respectively. The rectilinear crossing number A014540 is the number of (not necessarily empty) convex quadrilaterals.

a(11)-a(13) from Manfred Scheucher, Aug 17 2018

cp's OEIS Frontend

A298445 Triangle T(n,k) read by rows: number of n-node simple graphs with rectilinear crossing number k (k=0..A014540(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A298446 Triangle T(n,k) read by rows: number of n-node connected graphs with rectilinear crossing number k (k=0..A014540(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A135515 Number of inequivalent drawings of the complete graph Kn on n vertices that attain the corresponding rectilinear crossing number (A014540).

Views

Author

Keywords

Comments

Links

A307891 Rectilinear crossing number A014540(n) - crossing number A000241(n) of complete graph on n nodes.

Views

Author

Keywords

Examples

Crossrefs

A030179 Quarter-squares squared: A002620^2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A000241 Crossing number of complete graph with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A006247 Number of simple arrangements of n pseudolines in the projective plane with a marked cell. Number of Euclidean pseudo-order types: nondegenerate abstract order types of configurations of n points in the plane.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A063542 Least number of empty convex quadrilaterals (4-gons) determined by n points in the plane.

Views

Author

Keywords

References

Links

Crossrefs

Extensions