Thecrossing numberof a graph is the minimum possible number of intersecting pairs of edges in any planar drawing.

Crossing Lemma (Ajtai, Chvátal, Newborn, and Szemerédi; Leighton):Any graph withnvertices ande> 4nedges has crossing numberOmega(e^{3}/n^{2}).

Proof (folklore):Consider a planar embedding of a graph withnvertices,eedges, andcpairs of crossing edges. Euler's formula implies thatc>e-3n. Take a random subset of the vertices, each vertex with probabilityp. The expected number of vertices, edges, and crossings in the induced subgraph are at leastpn,p^{2}e, andp^{4}c, respectively. Thus,p^{4}c>p^{2}e- 3pn, which impliesc>e/p^{2}- 3n/p^{3}. Takingp= 4n/egives us, c>e^{3}/64n^{2}QED.

Theorem (Dey):Any set ofnpoints in the plane has at mostO(n^{4/3}) halving lines.

Proof (Dey):Assume without loss of generality thatnis even. LetSbe a set ofnpoints in the plane. LetHbe the set of line segments with endpointsp,qinS, such that the line throughpqis a halving line.The segments in

Hcan be decomposed inton/2 convex chains as follows. Start with a vertical line through one of then/2 leftmost pointspinS, and rotate this line clockwise aroundpuntil it contains a segmentpqinH. Initially, there are less thann/2 points above the line; this number goes down whenever the line hits a point to the left ofp, and goes up whenever it hits a point to the right ofp. It follows thatqmust lie to the right ofp. Continue rotating the line clockwise aroundquntil it hits another segment inH(which will lie to the right ofq), and so on, until the line is vertical again. The sequence of segments hit by the rotating line forms a convex chain, and every segment inHis in exactly one convex chain. (These convex chains are dual to the concave chains studied by Agarwal, Aronov, and Sharir.)

A set of 14 points with 14 halving lines, split into 7 convex chainsThe number of intersections between any two convex chains is no more than the number of upper common tangents between the same two chains. Any line between two points in

Sis an upper common tangent of at most one pair of chains. Thus, there are at mostO(n^{2}) intersections between the segments inH. By the Crossing Lemma, any graph withnvertices and crossing numberO(n^{2}) has at mostO(n^{4/3}) edges, soShas at mostO(n^{4/3}) halving lines,QED.Dey's proof of the O(

nk^{1/3}) upper bound onk-sets is almost this simple. The only other result he needs is that the maximum number of <k-sets isn(k-1), which was proved by Alon and Gyõri.Thanks to Pankaj Agarwal for pointing out a gap in an earlier version of this proof.

"folklore":

According to János Pach, this probabilistic proof has been independently rediscovered several times, by Lovász, Matousek, Füredi, Alon, Seidel, and many others, but was not published since it is essentially equivalent to the original counting argument of Ajtai et al. The proof was first published by Székely. Using a more complicated probabilistic argument, Pach and Tóth (Proc. Graph Drawing '96, Springer LNCS 1190, 1997, pp. 345-354) recently improved the constant from 1/64 to 4/135, which is currently the best known.

Halving lines and