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

B. M. Ábrego, J. Balogh, S. Fernández-Merchant, J. Leaños, G. Salazar

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1257-1264
Number of pages8
JournalJournal of Combinatorial Theory. Series A
Volume115
Issue number7
DOIs
StatePublished - Oct 2008
Externally publishedYes

Keywords

  • Allowable sequences
  • Complete graphs
  • Halving lines
  • Halving pseudolines
  • Pseudolinear crossing number
  • Rectilinear crossing number
  • k-edges

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'An extended lower bound on the number of (≤ k)-edges to generalized configurations of points and the pseudolinear crossing number of K<sub>n</sub>'. Together they form a unique fingerprint.

Cite this