| Displaying 1-8 of 8 results found.
page
1
Triangle T(n,k) read by rows: number of n-node simple graphs with rectilinear crossing number k (k=0.. A014540(n)).
+20
1
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
COMMENTS
Computed up to n=8 using data provided by Geoffrey Exoo. (There appear to be some problems with n=9 data.)
FORMULA
T(n,kmax(n)) = 1 for n > 4.
Sum_{k=0..kmax(n)} T(n,k) = A000088(n).
EXAMPLE
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
CROSSREFS
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).
Triangle T(n,k) read by rows: number of n-node connected graphs with rectilinear crossing number k (k=0.. A014540(n)).
+20
1
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
COMMENTS
Computed up to n=8 using data provided by Geoffrey Exoo. (There appear to be some problems with n=9 data.)
FORMULA
T(n,kmax(n)) = 1 for n > 4.
sum(k=0..kmax(n), T(n,k)) = A001349(n).
EXAMPLE
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
CROSSREFS
Cf. A014540 (rectilinear crossing number for K_n). Cf. A298445 (counts for simple graph).
Number of inequivalent drawings of the complete graph Kn on n vertices that attain the corresponding rectilinear crossing number ( A014540).
+20
0
1, 1, 1, 3, 2, 10, 2, 374
COMMENTS
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.
AUTHOR
Don Pedro Esq. (info(AT)servierlaboratories.org), Feb 09 2008
Rectilinear crossing number A014540(n) - crossing number A000241(n) of complete graph on n nodes.
+20
0
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
EXAMPLE
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.
Quarter-squares squared: A002620^2.
+10
20
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
COMMENTS
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
REFERENCES
C. Thomassen, Embeddings and minors, pp. 301-349 of R. L. Graham et al., eds., Handbook of Combinatorics, MIT Press.
FORMULA
a(n) = floor(n^2/4)^2.
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
MAPLE
seq( (2*n^4 -2*n^2 +1 +(-1)^n*(2*n^2 -1))/32, n=0..40); # G. C. Greubel, Dec 28 2019
MATHEMATICA
LinearRecurrence[{2, 2, -6, 0, 6, -2, -2, 1}, {0, 0, 1, 4, 16, 36, 81, 144}, 40] (* Harvey P. Dale, Apr 26 2011 *)
PROG
(Magma) [(Floor(n^2/4))^2: n in [0..40]]; // G. C. Greubel, Dec 28 2019 (Sage) [floor(n^2/4)^2 for n in (0..40)] # G. C. Greubel, Dec 28 2019 (GAP) List([0..40], n-> (2*n^4 -2*n^2 +1 +(-1)^n*(2*n^2 -1))/32); # G. C. Greubel, Dec 28 2019
Crossing number of complete graph with n nodes.
(Formerly M2772 N1115)
+10
13
0, 0, 0, 0, 0, 1, 3, 9, 18, 36, 60, 100, 150, 225, 315
COMMENTS
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
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
REFERENCES
Á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.
FORMULA
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
CROSSREFS
It is conjectured that this sequence coincides with A028723.
EXTENSIONS
a(13) and a(14) computed by O. Aichholzer and added by Manfred Scheucher, Apr 24 2024
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.
(Formerly M0917)
+10
12
1, 1, 1, 2, 3, 16, 135, 3315, 158830, 14320182, 2343203071, 691470685682, 366477801792538
COMMENTS
Also the number of nonisomorphic nondegenerate acyclic rank 3 oriented matroids on n elements. - Manfred Scheucher, May 09 2022
REFERENCES
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
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 Alexander Pilz and Emo Welzl, Order on order types, Discrete & Computational Geometry, 59 (No. 4, 2015), 886-922.
FORMULA
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
EXTENSIONS
a(11) from Franz Aurenhammer (auren(AT)igi.tu-graz.ac.at), Feb 05 2002
Least number of empty convex quadrilaterals (4-gons) determined by n points in the plane.
+10
3
0, 1, 3, 6, 10, 15, 23, 32, 42, 51
REFERENCES
K. Dehnhardt. Leere konvexe Vielecke in ebenen Punktmengen. PhD thesis, TU Braunschweig, Germany, 1987.
CROSSREFS
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.
Search completed in 0.013 seconds
| 