For a finite forbidden family $\mathcal{F}$, does some $G\in\mathcal{F}$ have $\mathrm{ex}(n;G)\asymp\mathrm{ex}(n;\mathcal{F})$? (Erdős #180)
Statement
For a finite family $\mathcal{F}$ of finite graphs, let $\mathrm{ex}(n;\mathcal{F})$ be the maximum number of edges in an $n$-vertex graph containing no member of $\mathcal{F}$ as a subgraph. Trivially $\mathrm{ex}(n;\mathcal{F})\leq \mathrm{ex}(n;G)$ for every $G\in\mathcal{F}$. Erdős–Simonovits question: is it true that for every finite family $\mathcal{F}$ there is a single graph $G\in\mathcal{F}$ with $$\mathrm{ex}(n;G)\ll_{\mathcal{F}}\mathrm{ex}(n;\mathcal{F})\,?$$ Equivalently, is the family Turán number always controlled — up to a constant depending only on $\mathcal{F}$ — by the Turán number of one of its members? (As literally stated for EVERY $\mathcal{F}$ this is false; see the background for the known counterexample. The live problem is to characterize the families for which it holds, excluding the degenerate cases.)
Acceptance. FULLY RESOLVES: either (a) a complete proof that for every finite family $\mathcal{F}$ satisfying a precisely-stated non-degeneracy condition (one that provably excludes the star-plus-matching type counterexamples) some $G\in\mathcal{F}$ satisfies $\mathrm{ex}(n;G)\ll_{\mathcal{F}}\mathrm{ex}(n;\mathcal{F})$, together with a proof that the condition is the right dividing line; or (b) a new finite family $\mathcal{F}$, structurally different from the star-plus-matching example, with a proof that no member controls $\mathrm{ex}(n;\mathcal{F})$, sharpening the boundary of falsity. Deliver a full written proof with all steps (machine-checkable Lean/Coq preferred). ADVANCES, each with proof or reproducible certificate: prove the statement for a natural subclass (e.g. all families of bipartite graphs each of minimum degree $\geq 2$); exhibit and prove a new counterexample family; or computationally map $\mathrm{ex}(n;\mathcal{F})$ against $\min_{G\in\mathcal{F}}\mathrm{ex}(n;G)$ over a catalogued set of small families to identify candidate separations, with reproducible code. Deliver the proof, the counterexample-with-proof, or the computational map plus code.
Background
A problem of Erdős and Simonovits [ErSi82]. It is trivially true when $\mathcal{F}$ contains no bipartite graph: by the Erdős–Stone theorem, if the minimum chromatic number among members of $\mathcal{F}$ is $r\geq 2$, then $\mathrm{ex}(n;\mathcal{F})=\mathrm{ex}(n;H)=\left(\frac{r-2}{r-1}+o(1)\right)\binom{n}{2}$ for the relevant $H$. Erdős and Simonovits observed that the analogous statement is FALSE for infinite families (e.g. the family of all cycles). Crucially, a 'folklore' finite counterexample attributed to Hunter defeats the naive universal conjecture: take $\mathcal{F}=\{H_1,H_2\}$ where $H_1$ is a star and $H_2$ a matching, each with at least two edges; then $\mathrm{ex}(n;\mathcal{F})\ll 1$ (bounded), while $\mathrm{ex}(n;H_1)\asymp n$ and $\mathrm{ex}(n;H_2)\asymp n$, so no single member controls the family Turán number. Bloom notes the conjecture may still hold for all $\mathcal{F}$ outside such degenerate cases, and that is the live open problem. Related: Erdős #575 (erdosproblems.com/575); this is #47 in the Extremal Graph Theory problem collection. Listed as open on erdosproblems.com/180 (fetched 2026-07-13, status 'open'), tagged graph theory | turan number. Attacker's tool: extremal graph theory — supersaturation, the Erdős–Stone–Simonovits machinery, and constructions of families witnessing separations — plus computation of $\mathrm{ex}(n;\cdot)$ for small $n$ over catalogued families to surface candidate counterexamples. Proof-shaped.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #180 (T. F. Bloom) | website |
| REF-02 | Extremal Graph Theory collection #47 — Turán number of a family | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.