Skip to content

Erdős Problem #804

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (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

For fixed n and m, define the minimal guaranteed independence alpha(G) over n-vertex G such that EVERY induced m-vertex subgraph has an independent set of size at least log n. The maintained statement inconsistently names f(m,n) and f(n); retain two-variable f(m,n) for clarity. Erdős–Hajnal conjectured f((log n)^2,n)>=n^(1/2-o(1)), and f((log n)^3,n)>> (log n)^3.

The function has two arguments: both the ambient order n and the subset scale m matter. The hypothesis concerns EVERY induced m-vertex subgraph, while the conclusion concerns ONE global independent set. The two specific strong predictions were refuted; the extremal optimization and its known logarithmic estimates remain mathematically meaningful.

A small example

In complete graph K4, every induced 2-vertex subgraph has alpha=1, while in empty graph on 4 vertices every induced 2-vertex subgraph has alpha=2 and global alpha=4. These fixtures distinguish alpha(G) from minimum alpha over induced m-subgraphs; they are not asymptotic evidence.

This finite fixture tests the conventions. It does not certify any of the asymptotic or all-graphs assertions.

What is known

Maintained #804 reports Alon–Sudakov [AlSu07] bounds f((log n)^2,n) between c (log n)^2/loglog n and C (log n)^2, and f((log n)^3,n) asymptotic (log n)^2/loglog n. Thus both ambitious conjectural comparisons fail. 'DISPROVED' refers to subquestions, not the existence of the f optimization. The authors' 2007 abstract and Princeton publication record directly establish the cubic-scale independence result; complete proofs, and the exact squared-scale rounding, have not been independently replayed. quantifier and parameter rounding need independent source audit.

The distinctions between established partial theorems, original open parts, and disproved universal claims have been preserved. Historical publications are attributed, rather than presented as new GCL mathematics.

The recorded Alon–Sudakov bounds compare the two regimes

\[ \frac{(\log n)^2}{\log\log n} \ll f((\log n)^2,n)\ll(\log n)^2 \]

and

\[ f((\log n)^3,n)\asymp \frac{(\log n)^2}{\log\log n}. \]

The notation \(f(m,n)\) makes the two independent size parameters explicit. Exact floor and ceiling conventions are part of the outstanding original-source review.

GCL's current state

The original authenticated source-return record has a disposition of STATUS_CONFLICT. This explanatory manuscript is editorially reviewed through the protected EC-BULK-005-R4 batch. Its original STATUS_CONFLICT source report remains intact, and editorial acceptance does not provide a GCL theorem-proof certificate. The mathematical status of individual subquestions is not determined by a single registry label.

What remains

Locate original Alon–Sudakov 2007 theorem with exact m=(log n)^2 and (log n)^3 rounding. Audit two-argument notation and base of logs. Explicitly distinguish #804 induced-independent lower property from #805 simultaneous induced clique AND independent property.

An accountable editorial review can verify the source-attributed distinction using the authors' abstract and finite fixtures. Formal theorem-proof certification still requires independent replay of the published argument.

Sources and claim boundaries

  • Erdos problem #804 and maintained source and bibliography, retrieved by web search 14 October 2026.
  • Authenticated issue-bound return for #804, preserving source limitations and open proof obligations.
  • Pinned teorth/erdosproblems repository revision 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml, source blob 4e60263a80af6207aca494d2e1388e44fa372889. No protected source lock was silently changed.
  • Editorial acceptance: Protected V2 batch EC-BULK-005-R4, exact-hash bound. Source publication: protected merge completed. Public mathematical rendering: verified before admission. New theorem certification: NONE.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2075 — 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