New lower bounds for the number of \((\leq k)\)-edges and the rectilinear crossing number of \(K_{n}\) (Q2385147)

Given a set of \(n\) points \(S\) in general position in the plane, a \(j\)-edge (\(0\leq j\leq \lfloor (n-2)/2\rfloor\)) is a segment spanned by two points of \(S\) such that there are exactly \(j\) points in one of the open halfplanes defined by the line of the segment. A \((\leq k)\)-edge is a \(j\)-edge for some \(j=0,1,\dots,k\). The paper shows that for \(0\leq k\leq \lfloor (n-2)/2\rfloor\), the number of \((\leq k)\)-edges is at least \(3{k+2\choose 2} +\sum_{j=\lfloor n/3\rfloor}^k (3j-n+3)\), which improves the previous best lower bound of J. Balogh and G. Salazar, when \(\lfloor n/3 \rfloor \leq k \leq 0.4864n\). As consequence, an improved lower bound is obtained for the rectilinear lower bound of complete graphs, i.e. the minimum number of convex quadrilaterals determined by \(n\) points in the plane in general position. The new lower bound for the rectilinear crossing number of complete graphs is \(0.379688{n\choose 4} +O(n^3)\), the old lower bound was \(0.37533{n\choose 4} +O(n^3)\), while the best upper bound is \(0.380559{n\choose 4} +O(n^3)\). Particular new values of rectilinear crossing numbers have also been determined. The rectilinear crossing number of \(K_{19}\) is 1318 and of \(K_{21}\) is 2055.