On Short Edges in Complete Topological Graphs

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)\) $h(n)=O(n^2/{log}^{1/4}n)$ , and in the other direction, gave constructions showing that \(h(n) = \Omega (n^{3/2})\) $h(n)=\mathrm{\Omega }(n^{3/2})$ . In this paper, we prove that \(h(n) = O(n^{7/4})\) $h(n)=O(n^{7/4})$ . Along the way, we establish a new variant of Chazelle and Welzl’s matching theorem for set systems with bounded VC-dimension, which we believe to be of independent interest.