Erdős Problem #22
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: graph theory.
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
A graph is free of four-cliques if no four vertices are all mutually connected. Its independence number is the greatest number of vertices with no edges between them. Erdős Problem #22 asked whether, for every fixed \(\varepsilon>0\), all sufficiently large numbers of vertices \(n\) admit a four-clique-free graph having at least \(n^2/8\) edges and independence number at most \(\varepsilon n\).
The exact edge threshold matters. Having \((1/8-o(1))n^2\) edges is close asymptotically, but does not by itself guarantee at least \(n^2/8\). The original question is proved.
A small example
A four-cycle has four vertices and four edges, so it contains no four-clique and has more than \(4^2/8=2\) edges. But its independence number is 2, half its vertices. Hence for \(\varepsilon<1/2\) this finite graph fails the required small-independence condition despite having plenty of edges.
It illustrates why controlling edge count alone is insufficient; both requirements must hold in the same graph at arbitrarily large sizes.
What is known
Fox, Loh and Zhao, The critical window for the classical Ramsey–Turán problem, Combinatorica 35 (2015), 435–476, established exact-threshold constructions with independence number bounded by
for some absolute constant \(C\) and all sufficiently large \(n\). Because the factor involving logarithms tends to zero, this yields the requested \(\varepsilon n\) upper bound for each fixed \(\varepsilon>0\) while retaining at least \(n^2/8\) edges.
Earlier Bollobás–Erdős constructions established the limiting density near one eighth; these alone did not supply the exact-threshold theorem.
GCL's current state
Source audit #1291 inspects the frozen formal-provider statement, the stronger quantitative variant, and its unfilled proof bodies. It checks the elementary logarithmic-limit implication and the four-cycle sanity example. This editorial analysis is not a newly independently compiled proof of the deep graph construction.
What remains
The historical existence question is settled. A separate formalization effort could replay the exact Fox–Loh–Zhao construction and its independence bound or investigate sharper quantitative variants, subject to the existing mathematical certification process.
Sources and claim boundaries
- Erdős Problems #22: solved statement and published bounds.
- Fox–Loh–Zhao (2015), author preprint; published DOI.
- GCL source return #1291: statement reconciliation and elementary consequence, not a deep proof replay.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1291 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.