נתן רובין

We show that any set of n points in general position in the plane determines n¹−o(1⁾ pairwise crossing segments. The best previously known lower bound, Ω n, was proved more than 25 years ago by Aronov, Erdős, Goddard, Kleitman, Klugerman, Pach, and Schulman. Our proof is fully constructive, and extends to dense geometric graphs.