Hereditary Turán theory in (c,t)-sparse graphs

Problem 1.1 · arXiv:2405.05902

arXiv Problem high confidence— first stated 2024-06-08

Authors: Jacob Fox, Rajko Nenadov, Huy Tuan Pham

Status open high confidence

Problem 1.1 calls for a unified Turán-type theory determining ex(Γ, 𝒫) for any (c,t)-sparse host graph Γ and any hereditary property 𝒫 that excludes some bipartite graph. The source paper itself resolves this for certain bipartite forbidden graphs when Γ is a dense random graph or a Paley graph, and the contemporaneous independent work of Clifton, Liu, Mattos, and Zheng (arXiv:2405.09486, May 2024) fully settles the G(n,p) case for all such 𝒫. No post-2024 paper addressing the complete (c,t)-sparse generalization has been found.

Reviewer notes. The contemporaneous paper arXiv:2405.09486 (Clifton, Liu, Mattos, Zheng, May 2024) independently resolves the G(n,p) special case of Problem 1.1 (Theorem 1.1: for every non-trivial hereditary property 𝒫 missing some bipartite L and every fixed p∈(0,1), ex(G(n,p),𝒫) ≤ n^{2−ε} w.h.p.). The acknowledgements of that paper note that Fox, Nenadov and Pham obtained a similar result independently. Because 2405.09486 is from the same year (2024) as the source paper, it is not listed in since_posted. The full (c,t)-sparse problem (non-random-graph hosts) remains open. The source paper was published in Combinatorica 45(6), 2025.

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

Problem. Given a hereditary property $\mathcal{P}$ which misses a bipartite graph and a $(c,t)$-sparse graph $\Gamma$, determine $\mathrm{ex}(\Gamma,\mathcal{P})$.

Context

The authors introduce the notion of a $(c,t)$-sparse graph $\Gamma$ (one where the edge density between any two vertex subsets of size at least $t$ is at most $1-c$), which generalizes both dense random graphs and $K_{t,t}$-free graphs. This problem asks for a unified Turán-type theory covering both settings, extending a question of Alon, Krivelevich, and Samotij on hereditary properties in random graphs.

Source paper

The largest subgraph without a forbidden induced subgraph
Jacob Fox, Rajko Nenadov, Huy Tuan Pham · 2024-06-08
https://arxiv.org/abs/2405.05902