Skip to content

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:

\[ 0\le m\le\delta n^2. \]

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

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.

Back to catalogue · Compendium introduction