\(k\)-sets, convex quadrilaterals, and the rectilinear crossing number of \(K_{n}\) (Q2498933)

Imagine a cluster of \(n\) points in general position in the plane. A \((\leq k)\)-set is a subset of size \(\leq k\) that can be separated from the other points by a line. The enumeration of these is, in general, a difficult problem, not yet solved. It is related to the problem of estimating the number of convex quadrilaterals determined by \(n\) points in the plane; to the problem of minimizing the number of crossings in a planar rectilinear graph on \(n\) vertices; and determining the probability that four randomly-chosen points (independently chosen from a specified probability distribution) form a convex quadrilateral (a problem first investigated by Sylvester in 1865.) As we travel in the plane around a cluster of points in general position, their apparent linear ordering changes occasionally, with pairs of adjacent elements occasionally interchanging their position in the permutation, until the original order is reversed. A circular sequence is an abstract combinatorial structure that models this. The authors begin by finding an improved lower bound on the number of ``shallow'' transpositions in a circular sequence -- transpositions of elements near the beginning or end of the permutation. From this purely combinatorial result, bounds for the geometric problems mentioned above are obtained, refining results of Abrego and Fernandez-Merchant (2005), and of Lovasz, Vesztergombi, Wagner and Welzl (2004).