Skip to content

Erdős Problem #802

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (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 K_r-free graph (no complete r-vertex subgraph) on n vertices with average degree t is conjectured to have an independent vertex set of size at least c_r n log(t)/t, in the asymptotic regime t sufficiently large. Independence means no edges between any two selected vertices. The positive constant may depend on r but not n,t.

K_r-free means no copy of the complete r-vertex graph, not merely an upper bound on degree. The conjectured independent-set size is on the order of n log(t)/t for large average degree t, with a constant depending on r. The extra loglog(t) denominator in Shearer's general bound is a genuine, presently unresolved loss for larger r.

A small example

A 5-cycle C5 is triangle-free (r=3), has n=5, average degree t=2 and independent number alpha=2 (non-adjacent vertices such as 0 and 2). K_r-free is GLOBAL absence of a clique, not a condition on just local degrees. Lower expression log(t) is an asymptotic target, not an exact 5-vertex inequality with unspecified c_r.

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

What is known

Maintained Erdős #802 (directly read via public search, 2026-10-14) reports original Ajtai–Erdős–Komlós–Szemerédi [AEKS81] bound n loglog(t+1)/t; Shearer [Sh95] n log(t)/(t loglog(t+1)); Ajtai–Komlós–Szemerédi [AKS80] proves sought bound for r=3; Alon [Al96b] proves bound under stronger neighborhood chromatic-number <=r-2 hypothesis. General r remains OPEN. Original four papers not fully proof-checked; no external status promotion.

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 target bound for fixed \(r\) and sufficiently large average degree \(t\) is

$$

\alpha(G)\gg_r \frac{n\log t}{t}.

$$

The established general-r bound attributed to Shearer instead has an extra logarithm of a logarithm in the denominator. The \(r=3\) result does not automatically extend to all larger forbidden cliques.

GCL's current state

The original authenticated RESULT/1 source return records BOUNDED_TASK_DESIGNED and retains the original mathematical qualifications. This is an editorially reviewed explanatory article in the EC-BULK-005-R9 protected batch, effective only when that exact-hash transaction merges. The corresponding maintained Erdős statement and its bibliography were inspected. This editorial decision does not certify any full original theorem proof, independent external formalization, or Lean kernel check.

Preserved source-review qualifications: open kr free independence general r while r3 known. See the immutable 128-case critical review record for the complete source-return caveats.

What remains

Source-lock original AEKS81 and Sh95 theorem quantifiers and r=3 case. Reproduce alpha(C5)=2 by enumerating independent subsets; tabulate the gap between log t and log t/loglog t. No conclusion for arbitrary fixed r>=4.

Before protected admission the responsible editor must inspect full original proofs where not yet read, verify the executable finite example and mathematical notation, test actual public rendering, and record a critical review disposition. Local gate success alone is insufficient.

Sources and claim boundaries

Editorial source decision: R9 critical review, REVIEWED as a source-grounded explanation only. All open mathematical questions, primary-proof fidelity obligations, and external formalization caveats remain separate.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2073 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: STATEMENT_CAPTURE_REQUIRED.
  • 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