NYU CG seminar. Tuesday, October 17, 2023

Let h(n) be the minimum integer such that every complete n-vertex simple
topological graph contains an edge that crosses at most h(n) other edges.
In 2009, Kynčl and Valtr showed that h(n)=O(n^2/log^{1/4}n), and in the
other direction, gave constructions showing that h(n)=Ω(n^{3/2}). In this
talk, I will sketch a proof showing that h(n)=O(n^{7/4}). The proof is
based on a variant of Chazelle-Welzl's matching theorem for set systems
with bounded VC-dimension, which may be of independent interest. I will
also discuss several other related problems.