New lower bounds for the number of (≤k)(\leq k)-edges and the rectilinear crossing number of KnK_n

preprint2006arXivOpen access

Abstract

We provide a new lower bound on the number of (≤k)(\leq k)-edges of a set of nn points in the plane in general position. We show that for 0≤k≤⌊n−22⌋0 \leq k \leq\lfloor\frac{n-2}{2}\rfloor the number of (≤k)(\leq k)-edges is at least Ek(S)≥3(k+22)+∑j=⌊n3⌋k(3j−n+3), E_k(S) \geq 3\binom{k+2}{2} + \sum_{j=\lfloor\frac{n}{3}\rfloor}^k (3j-n+3), which, for k≥⌊n3⌋k\geq \lfloor\tfrac{n}{3}\rfloor, improves the previous best lower bound in [J. Balogh, G. Salazar, Improved bounds for the number of (≤k\leq k)-sets, convex quadrilaterals, and the rectilinear crossing number of KnK_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 nn points in the plane in general position. We show that the crossing number is at least (41/108+ε)(n4)+O(n3)≥0.379631(n4)+O(n3), \Bigl({41/108}+ε\Bigr) \binom{n}{4} + O(n^3) \geq 0.379631 \binom{n}{4} + O(n^3), which improves the previous bound of 0.37533(n4)+O(n3)0.37533 \binom{n}{4} + O(n^3) in [J. Balogh, G. Salazar, Improved bounds for the number of (≤k\leq k)-sets, convex quadrilaterals, and the rectilinear crossing number of KnK_n] and approaches the best known upper bound 0.38058(n4)0.38058\binom{n}{4} in [O. Aichholzer, H. Krasser, Abstract order type extension and new results on the rectilinear crossing number].

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.