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

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

2006-08-24

arxiv.org/abs/math/0608610v2

Mathematics

Combinatorics

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

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

New lower bounds for the number of $(\leq k)$-edges and the rectilinear crossing number of $K_n$ does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with New lower bounds for the number of $(\leq k)$-edges and the rectilinear crossing number of $K_n$, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and New lower bounds for the number of $(\leq k)$-edges and the rectilinear crossing number of $K_n$ will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-339665