TY - JOUR

T1 - An extended lower bound on the number of (≤ k)-edges to generalized configurations of points and the pseudolinear crossing number of Kn

AU - Ábrego, B. M.

AU - Balogh, J.

AU - Fernández-Merchant, S.

AU - Leaños, J.

AU - Salazar, G.

N1 - Funding Information:
1 Supported by NSF grants DMS-0302804, DMS-0600303, DMS-0603769, UIUC Campus Research Board #07048 and OTKA grant T04939. 2 Supported by CONACYT Grant 45903 and by FAI-UASLP.

PY - 2008/10

Y1 - 2008/10

N2 - Recently, Aichholzer, García, Orden, and Ramos derived a remarkably improved lower bound for the number of (≤ k)-edges in an n-point set, and as an immediate corollary, an improved lower bound on the rectilinear crossing number of Kn. We use simple allowable sequences to extend all their results to the more general setting of simple generalized configurations of points and slightly improve the lower bound on Sylvester's constant from 0.37963 to 0.379688. In other words, we prove that the pseudolinear (and consequently the rectilinear) crossing number of Kn is at least 0.379688 ((n; 4)) + Θ (n3). We use this to determine the exact pseudolinear crossing numbers of Kn and the maximum number of halving pseudolines in an n-point set for n = 10, 11, 12, 13, 15, 17, 19, and 21. All these values coincide with the corresponding rectilinear numbers obtained by Aichholzer et al.

AB - Recently, Aichholzer, García, Orden, and Ramos derived a remarkably improved lower bound for the number of (≤ k)-edges in an n-point set, and as an immediate corollary, an improved lower bound on the rectilinear crossing number of Kn. We use simple allowable sequences to extend all their results to the more general setting of simple generalized configurations of points and slightly improve the lower bound on Sylvester's constant from 0.37963 to 0.379688. In other words, we prove that the pseudolinear (and consequently the rectilinear) crossing number of Kn is at least 0.379688 ((n; 4)) + Θ (n3). We use this to determine the exact pseudolinear crossing numbers of Kn and the maximum number of halving pseudolines in an n-point set for n = 10, 11, 12, 13, 15, 17, 19, and 21. All these values coincide with the corresponding rectilinear numbers obtained by Aichholzer et al.

KW - Allowable sequences

KW - Complete graphs

KW - Halving lines

KW - Halving pseudolines

KW - Pseudolinear crossing number

KW - Rectilinear crossing number

KW - k-edges

UR - http://www.scopus.com/inward/record.url?scp=50649091377&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=50649091377&partnerID=8YFLogxK

U2 - 10.1016/j.jcta.2007.11.004

DO - 10.1016/j.jcta.2007.11.004

M3 - Article

AN - SCOPUS:50649091377

VL - 115

SP - 1257

EP - 1264

JO - Journal of Combinatorial Theory - Series A

JF - Journal of Combinatorial Theory - Series A

SN - 0097-3165

IS - 7

ER -