New lower bounds for the number of $(\le k)$-edges and the rectilinear crossing number of $K_n$

Abstract

We provide a new lower bound on the number of $(\le k)$-edges of a set of $n$ points in the plane in general position. We show that for $0\le k\le \lfloor \frac{n-2}{2}\rfloor$ the number of $(\le k)$-edges is at least $$E_k(S)\ge 3\left(\genfrac{}{}{0ex}{}{k+2}{2}\right)+\sum _{j=\lfloor \frac{n}{3}\rfloor }^k(3j-n+3),$$ which, for $k\ge \lfloor \frac{n}{3}\rfloor$, improves the previous best lower bound in [J. Balogh, G. Salazar, Improved bounds for the number of ($\le k$)-sets, convex quadrilaterals, and the rectilinear crossing number of $K_n$]. As a main consequence, we obtain a new lower bound on the rectilinear crossing number of the complete graph or, in other words, on the minimum number of convex quadrilaterals determined by $n$ points in the plane in general position. We show that the crossing number is at least $$(41/108+\epsilon )\left(\genfrac{}{}{0ex}{}{n}{4}\right)+O(n^3)\ge 0.379631\left(\genfrac{}{}{0ex}{}{n}{4}\right)+O(n^3),$$ which improves the previous bound of $0.37533\left(\genfrac{}{}{0ex}{}{n}{4}\right)+O(n^3)$ in [J. Balogh, G. Salazar, Improved bounds for the number of ($\le k$)-sets, convex quadrilaterals, and the rectilinear crossing number of $K_n$] and approaches the best known upper bound $0.38058\left(\genfrac{}{}{0ex}{}{n}{4}\right)$ in [O. Aichholzer, H. Krasser, Abstract order type extension and new results on the rectilinear crossing number].

14 pages, 4 figures, submitted to Discrete and Computational Geometry, fixed a gap in the proof of Theorem 10

References in corpus (1)

• Toward the Rectilinear Crossing Number of $K_n$: New Drawings, Upper Bounds, and Asymptotics

Cited by in corpus (11)

• Crossing numbers and combinatorial characterization of monotone drawings of $K_n$
• Point sets that minimize $(\le k)$-edges, 3-decomposable drawings, and the rectilinear crossing number of $K_{30}$
• New results on lower bounds for the number of (at most k)-facets
• The Orchard crossing number of an abstract graph
• Extending drawings of complete graphs into arrangements of pseudocircles
• 3--symmetric and 3--decomposable drawings of $K_n$ (extended version)
• Plane Hamiltonian Cycles in Convex Drawings
• Drawings of Kn with the same rotation scheme are the same up to Reidemeister moves. Gioan's Theorem
• Errata and Addenda to Mathematical Constants
• On polynomials associated to Voronoi diagrams of point sets and crossing numbers
• On 3-decomposable geometric drawings of $K_n$