Polynomial saving in bipartite hereditary ex

Informal Conjecture (polynomial saving in the bipartite case) · arXiv:2210.12754

arXiv Informal medium confidence— first stated 2022-10-23

Authors: Noga Alon, Michael Krivelevich, Wojciech Samotij

Status solved high confidence

Clifton, Liu, Mattos, and Zheng (arXiv:2405.09486, 2024) fully resolve the conjecture by proving as Theorem 1.1 that for every non-trivial hereditary property $\mathcal{P}$ missing some bipartite graph $L$, we have $\mathrm{ex}(G(n,p),\mathcal{P}) \leq n^{2-\varepsilon}$ whp for some $\varepsilon = \varepsilon(\mathcal{P}) > 0$. Their paper explicitly states it answers a question of Alon, Krivelevich, and Samotij.

Cited literature (1)

proof Subgraphs of random graphs in hereditary families (2024)

Alexander Clifton, Hong Liu, Leticia Mattos, Michael Zheng · arXiv preprint · arXiv:2405.09486 · doi:10.48550/arXiv.2405.09486

Proves Theorem 1.1: for every hereditary property missing a bipartite graph, ex(G(n,p),P) <= n^(2-epsilon) whp, directly answering the conjecture of Alon, Krivelevich, and Samotij.

Reviewer notes. Conjecture fully resolved by arXiv:2405.09486 (5-page paper, submitted May 2024). No journal publication listed at time of review.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. It seems plausible that in the bipartite case $\mathrm{ex}(G, \mathcal{P}) \leq n^{2-\varepsilon}$ for some $\varepsilon = \varepsilon(\mathcal{P}) > 0$.

Context

When $\mathcal{P}$ misses a bipartite graph, Theorem 1.1 gives only $\mathrm{ex}(G(n,p),\mathcal{P}) = o(n^2)$ whp. The authors speculate that the saving over the trivial $O(n^2)$ bound is in fact polynomial, not merely sub-polynomial.

Notes. PDF source; signaled by the phrase 'It seems plausible that'. Math notation appears clean despite PDF extraction.

Source paper

Largest subgraph from a hereditary property in a random graph
Noga Alon, Michael Krivelevich, Wojciech Samotij · 2022-10-23
https://arxiv.org/abs/2210.12754 PDF source