## Midrange crossing constant(s)

- Aug. 30, 2019
- 2:30 p.m.
- LeConte 312

## Abstract

The crossing number of a graph is the minimum number of crossings it can be drawn in a plane.
Let $\kappa(n,m)$ the minimum crossing number of graphs with $n$ vertices and $m$ edges.
The crossing lemma states that for $m>4n$, $\kappa(n,m)\ge \frac{1}{64}\frac{m^3}{n^2}$.

Amazingly, ten years before the crossing lemma, Erdős and Guy conjectured that for
any $m=m(n)$ satisfying $n<<m<<n^2$ $\lim\limits _ {n\rightarrow\infty}\frac{\kappa(n,m)n^2}{m^3}$
exists and is positive; this has been dubbed the midrange crossing constant. Pach, Spencer and
Tóth proved this conjecture. We extend their proof to show that the midrange crossing constant
exists for graph classes that satisfy a certain set of graph properties. The crossing constant
(for the class of all graphs) have been shown to be between $\frac{1}{19}$ and $\frac{8}{9\pi^2}$.
The computation for the upper bound is very cumbersome. We show an alternative probabilistic
construction that is relatively easy. Joint wok with László Székely, Zhiyu Wang, Josiah Reiswig and
inne Singgih.