Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269 - Combinatorics

Natan Rubin

Ben-Gurion University

Planar point sets determine many pairwise crossing segments

Abstract:

We show that any set of $n$ points in general position in the plane determines $n^{1-o(1)}$ pairwise crossing segments. The best previously known lower bound, $\Omega(\sqrt{n})$ was proved more than 25 years ago by Aronov, Erd\H os, Goddard, Kleitman, Klugerman, Pach, and Schulman. Our proof is fully constructive, and extends to dense geometric graphs. This is joint work with J\'anos Pach and G\'abor Tardos.

Host: Andrew Suk

October 15, 2019

2:00 PM

AP&M 7321

****************************