Math Conjectures

Erd\u0151s–Simonovits Compactness Conjecture

OPENMajorConjectureProposed 1982 · Standard version

Canonical statement

For every finite nonempty family F\mathcal F of graphs, each containing a cycle, there are F∈FF\in\mathcal F and C>0C>0 such that
ex⁡(n,F)≤Cex⁡(n,F) \operatorname{ex}(n,F)\le C\operatorname{ex}(n,\mathcal F)
for all sufficiently large nn, where ex⁡(n,F)\operatorname{ex}(n,\mathcal F) is the largest number of edges in an nn-vertex graph containing no member of F\mathcal F.
View source LaTeX
For every finite nonempty family \(\mathcal F\) of graphs, each containing a cycle, there are \(F\in\mathcal F\) and \(C>0\) such that
\[
  \operatorname{ex}(n,F)\le C\operatorname{ex}(n,\mathcal F)
\]
for all sufficiently large \(n\), where \(\operatorname{ex}(n,\mathcal F)\) is the largest number of edges in an \(n\)-vertex graph containing no member of \(\mathcal F\).
GRAPH-028:[ErdosSimonovits1982Compactness][FurediSimonovits2013Degenerate][OpenAI2026TenAdvances]
Graph theoryCombinatorics

Notes

The corrected Erdős–Simonovits compactness conjecture asks whether a finite cyclic forbidden family always has extremal number within a constant factor of one member [ErdosSimonovits1982Compactness]. The cycle restriction excludes elementary forest counterexamples. The August 1, 2026 manuscript claims a connected bipartite family with a polynomial separation [OpenAI2026TenAdvances]. Because the finite family and its two asymptotic estimates had not been independently verified, the stable record remains open.

Proof-claim watch (1)

Counterexample to Erdős–Simonovits compactness

Grade C

Full counterexample claim awaiting independent verification.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.