Erdős Problem #59
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (not automatically the live result).
Subject areas: graph theory, turan number.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
For a fixed graph \(H\), let \(f_H(n)\) be the number of labeled graphs on \([n]\) containing no copy of \(H\), and let \(\mathrm{ex}(n,H)\) be the largest number of edges in an \(H\)‑free graph on \(n\) vertices. Erdős asked whether
for every fixed \(H\).
The lower bound \(f_H(n)\ge 2^{\mathrm{ex}(n,H)}\) is immediate: all subgraphs of an extremal \(H\)‑free graph remain \(H\)‑free. Erdős–Frankl–Rödl proved the matching asymptotic upper bound for every non-bipartite \(H\), using the regularity method. Thus the conjecture is correct whenever \(\chi(H)\ge 3\).
It is false in general. Morris and Saxton proved that for \(H=C_6\), there are infinitely many \(n\) for which
for some constant \(c>0\). The weaker estimate \(f_H(n)\le 2^{O_H(\mathrm{ex}(n,H))}\) is known for several bipartite families, including all even cycles, but remains open for general cyclic bipartite graphs. See Erdős’s 1990 source, the Erdős–Frankl–Rödl paper, and the Morris–Saxton paper.
===SIX_SECTION_MATHEMATICAL_EXPLANATION===
The correct interpretation is:
The graph \(H\) is fixed before \(n\to\infty\). The forbidden copy is non-induced. The natural lower bound is
Therefore the question asks whether the number of \(H\)‑free graphs is determined to first order by the largest possible edge count.
A small example
Let \(X\) be an extremal \(H\)‑free graph with \(e(X)=\mathrm{ex}(n,H)\). Every subset of \(E(X)\) defines an \(H\)‑free graph, so
This is the basic reusable interface for any enumeration proof: only the upper bound requires substantial structure.
For \(H=C_6\) and \(n=6\), the graph \(K_5\) with one pendant vertex has \(11\) edges and is \(C_6\)‑free. Thus
To verify \(\mathrm{ex}(6,C_6)=11\), suppose a six-vertex graph has \(12\) edges. Its complement has three edges.
If the complement has maximum degree at most \(2\), the original graph has minimum degree at least \(3=6/2\), so Dirac’s theorem gives a Hamilton cycle.
If the complement has a vertex of degree \(3\), all three complement edges form a star. The other five vertices induce \(K_5\), while the center has exactly two allowed neighbors. Ordering those two neighbors as \(a,b\) and the remaining three vertices as \(x,y,z\) gives
a copy of \(C_6\). Hence every \(12\)‑edge graph contains \(C_6\), while the \(11\)‑edge pendant construction does not.
What is known
If \(\chi(H)=r\ge 3\), Erdős–Frankl–Rödl prove
The Erdős–Stone–Simonovits theorem gives
Combining the two relations yields
This proves the original estimate for every non-bipartite forbidden graph.
Morris–Saxton prove that there is \(c>0\) and infinitely many \(n\) such that
Because \(c\) is fixed and positive, the exponent is not asymptotic to \(\mathrm{ex}(n,C_6)\). Thus the original universal claim is false.
Their same paper proves, for every \(\ell\ge 2\),
For \(C_6\), this is an \(O(n^{4/3})\) exponent, consistent with the known order of \(\mathrm{ex}(n,C_6)\) and hence gives the weaker \(2^{O(\mathrm{ex}(n,C_6))}\) estimate.
GCL's current state
As of 2026-10-12, the maintained catalogue status is DISPROVED. GCL source assignment and evidence (source report pending posting). This is an editorial source audit, not GCL proof certification or mathematical acceptance.
NONE for the source lock.
PARTIAL formalization status only: the issue’s reported Lean metadata is not supported by an accessible formal statement or proof. No source blocker affects the mathematical disposition.
The original issue contains the authenticated RESULT/1 source report. This is source evidence, not independent mathematical certification or editorial admission.
What remains
Input: the fixed forbidden graph \(H=C_6\), the definition of \(\mathcal F_n(H)\), and the finite graph checker on vertex set \([6]\).
Target: formalize and verify the reusable lower-bound interface
together with the exact finite result \(\mathrm{ex}(6,C_6)=11\).
Method: formalize edge-subset monotonicity; separately verify the \(6\)‑vertex complement argument or exhaust all \(2^{15}\) graphs.
Acceptance: a proof of the injection and either a formal complement proof or an independently replayable exhaustive checker returning maximum \(11\) and no \(12\)‑edge \(C_6\)‑free graph.
Falsification: exhibit a \(12\)‑edge \(C_6\)‑free graph on six vertices, or identify a failure in the edge-subset injection.
Source dependencies: the definitions above and standard Dirac Hamiltonicity theorem only.
Stopping rule: stop after the finite verification and proof replay; do not infer anything about the unresolved all-bipartite \(2^{O(\mathrm{ex})}\) conjecture.
Sources and claim boundaries
Maintained problem #59; pinned catalogue revision 536408716724a2402bdfa7c1d764bf83d64a8c89.
The sharp universal statement is disproved.
- Erdős–Frankl–Rödl, Graphs and Combinatorics 2 (1986), 113–121, define \(F_n(H)\) and prove in Theorem 1.6, p. 114, that for \(\chi(H)\ge 3\),
Their proof uses the regularity reduction on pp. 116–117. Accessible primary paper: PDF; publisher record: Springer DOI.
- Morris–Saxton, “The number of \(C_{2\ell}\)‑free graphs,” arXiv:1309.2927v3 (2015), Proposition 1.4, prove that for some \(c>0\) and infinitely many \(n\),
This directly disproves the sharp \((1+o(1))\) claim. See the primary paper, especially pp. 3–4 and 8–9.
- The weaker conjecture
for every fixed cyclic bipartite \(H\) remains open in the audited literature. Morris–Saxton prove it for every even cycle, including \(C_6\), via \(f_{C_{2\ell}}(n)\le 2^{O(n^{1+1/\ell})}\). Jiang–Longbrake (2024) state that the general bipartite problem remains open and prove it under a broad balanced-supersaturation hypothesis; see the 2024 paper and journal version.
Pinned catalogue drift: the issue packet pins commit 536408716724a2402bdfa7c1d764bf83d64a8c89, with catalogue status “disproved” and update date 2025-08-31. The live page was last edited 2026-01-23 and agrees mathematically: non-bipartite \(H\) is positive, \(C_6\) disproves the sharp estimate, and the weaker bound remains conjectural. The issue metadata reports Lean, but the live page says “Formalised statement? No”; no accessible Lean statement or proof artifact was found.
Reused evidence: the local issue.json and live.html, the pinned catalogue metadata, Erdős–Frankl–Rödl, Morris–Saxton, and Jiang–Longbrake. No sibling or cooperative return was inspected.
Claim boundary: the sharp conjecture is disproved by the published \(C_6\) result; the non-bipartite case is proved; the weaker general cyclic-bipartite bound remains open in the audited sources. No novelty, certification, Lean verification, or award claim is made.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1328 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.