IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

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.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC