# Title: Short edges in topological graphs

## Speaker: Andrew Suk, UCSD

## Date and time: 6pm (New York time), Tuesday, October 17, 2023

## Place: WWH1314 (room 1314 Warren Weaver Hall, 251 Mercer Street)

### ...and on Zoom, details on the seminar mailing list

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)=\Omega(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.