Černý–Kynčl–Tóth dense stability conjecture

Let $\mathscr G$ be a family of graphs. It is stable if there exist positive constants $\delta=\delta(\mathscr G)$, $\gamma=\gamma(\mathscr G)$, and $n(\mathscr G)$ such that, for every graph $G\in\mathscr G$ with at least $n(\mathscr G)$ vertices and $m$ edges, a positive fraction of all subgraphs of $G$ with $(1-\delta)m$ edges has crossing number at least $\gamma\operatorname{cr}(G)$. Equivalently, if $G'$ is obtained from $G$ by deleting each edge independently with probability $\delta$, then with high probability $\operatorname{cr}(G')\geq\gamma\operatorname{cr}(G)$.

Černý–Kynčl–Tóth dense stability conjecture. There exists an $\overline{\epsilon}\in(1/3,1)$ such that, for each $\epsilon\in(\overline{\epsilon},1]$, the family of graphs with $\Theta(n^{1+\epsilon})$ edges is stable.

The original all-$\epsilon$ stability conjecture was disproved for $\epsilon\leq 1/3$. This restricted conjecture remains open for denser graph families, and concerns the robustness of crossing numbers under random edge deletion.