| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

4. Crossing number (and its variations) in random graphs

    1. Crossing number (and its variations) in random graphs

          Let $G(n,m)$ denote a random graph on $n$ vertices with $m$ edges.

      Add remark

      Problem 4.1.

      [Janos Pach] Let $G \sim G(n,m)$ with $m \geq \omega(n)$, is it true with high probability that the crossing number $\text{cr}(G) \geq \Omega(m^2)$?
          Note: The same problem can be asked for pair-crossing number $\text{pair-cr}(G)$ and odd-crossing number $\text{odd-cr}(G)$.

      Reference: J. Pach, G. Toth. Which Crossing Number Is It Anyway? Journal of Combinatorial Theory, Series B 80(2) (2000): 225–246.

          Cite this as: AimPL: Albertson conjecture and related problems, available at http://aimpl.org/albertson.