Erdős Problem #88
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: graph theory, ramsey 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 Ramsey-like if it has neither a very large clique nor a very large independent set. Erdős and McKay conjectured that a graph \(G\) with \(n\) vertices and no clique or independent set of size \(\epsilon\log n\) has an induced subgraph containing exactly \(m\) edges for every integer in a long initial interval:
Here \(\epsilon>0\) is fixed and \(\delta>0\) may depend on it. Once vertices are selected, all edges among them must be retained. Arbitrarily deleting unwanted edges would change the question.
A small example
In a five-cycle, one selected vertex induces zero edges, two adjacent vertices induce one edge, and three consecutive vertices induce two edges. Thus several successive edge counts are realized. However, a complete graph on \(n\) vertices only realizes counts \(\binom{t}{2}\) and misses most intermediate integers. The complete graph violates the Ramsey-like hypothesis for large \(n\).
The conjecture asserts substantially more than density alone: it prescribes each integer in an interval of length proportional to \(n^2\).
What is known
PROVED. Matthew Kwan, Ashwin Sah, Lisa Sauermann and Mehtaab Sawhney, Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture, establish refined bounds on the distribution of induced-edge counts of random vertex subsets of Ramsey graphs. Their 2022 primary abstract explicitly identifies the Erdős–McKay conjecture as a consequence.
Erdős and McKay previously proved a version with only \(\delta(\log n)^2\) in place of \(\delta n^2\). The original historical statement also assumed positive density of edges; the maintained source records that earlier Erdős–Szemerédi work implies this from the no-large-clique/no-large-independent-set hypothesis. The complete proof invokes several deep anticoncentration and Fourier-analytic tools and has not been independently reproduced here.
GCL's current state
Both the pinned catalogue and maintained #88 report PROVED. The original issue is #1357. The primary 2022 abstract and its semantic correspondence have been inspected; there is no admitted GCL kernel proof and no new solution claim.
The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.
What remains
A bounded source-semantics fixture is to enumerate graphs on five or six vertices and compute all induced-edge counts by examining vertex subsets. Acceptance: a second implementation using adjacency matrices agrees on every count, including \(m=0\), and rejects arbitrary noninduced edge deletion. This checks the definition, not the asymptotic theorem. An independent reading of Kwan–Sah–Sauermann–Sawhney's technical lemmas remains a separate optional proof-audit undertaking.
Sources and claim boundaries
- Kwan, Sah, Sauermann and Sawhney, arXiv:2208.02874, primary original abstract.
- Erdős #88, exact conjecture and historical density clarification.
- GCL source issue #1357; pinned revision 536408716724a2402bdfa7c1d764bf83d64a8c89.
No new anticoncentration result, mathematical certification or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1357 — 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.