Convex Quadrilaterals and k-Sets

We prove that the minimum number of convex quadrilaterals determined by n points in general position in the plane – or in other words, the rectilinear crossing number of the complete graph Kn – is at least (3 8 +10−5)¡n 4¢+O(n3). Our main tool is a lower bound on the number of (≤ k)-sets of the point set: we show that for every k ≤ n/2, there are at least 3¡k+1 2 ¢subsets of size at most k that can be separated from their complement by a straight line.