Skip to content

Erdős Problem #750

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: graph theory, chromatic number.

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 EVERY nonnegative function f(m)→∞, must there exist one graph G of infinite chromatic number such that every m-vertex subgraph contains an independent set of size at least m/2−f(m)? The frozen 2025 catalogue labels the problem PROVED, and the GCL-pinned FormalConjectures #750 records answer(True), and the current maintained page now explicitly reports a GPT-5.5 Pro solution prompted by Chojecki. This is not equivalent to a GCL proof certificate. This discrepancy is material. Do not promote a pinned answer(True) annotation with a sorry proof body to verified GCL mathematical certification.

A small example

The odd cycle C_5 has chromatic number three. Removing one vertex leaves a path on four vertices, so any induced subgraph on m≤5 vertices has an independent set of size at least floor(m/2). In particular the full C5 has α(C5)=2≥5/2−1. This finite example does not have INFINITE chromatic number and cannot decide the theorem.

What is known

Erdős, Hajnal and Szemerédi [EHS82] prove the weaker, linear-error formulation for every fixed ε>0: one can arrange α(H)≥(1/2−ε)|V(H)| in all finite induced H while maintaining infinite chromatic number. That corresponds to f(m)=εm, much larger than an arbitrary slowly divergent f(m) such as logloglog m. The GCL-pinned #750.lean at 85f863718beeec7b58a3a1926ee92e3472bc2020 contains the main arbitrary f theorem with answer(True) but by sorry, plus ε and c>1/4 auxiliary variants also sorry. The currently reported model-assisted construction and its Lean sketch require independent scrutiny; the external sketch reportedly assumes Stiebitz's theorem as an axiom and the GCL-pinned main proof body is still unproved.

GCL's current state

The original authenticated RESULT/1 source return has historical disposition STATUS_CONFLICT. This status and the original research exceptions are preserved, not silently converted into a theorem verdict. The maintained Erdős source and source-specific mathematical definitions were reviewed, and this article is editorially reviewed as a source-exception-annotated explanation under EC-BULK-005-R10, effective only after the exact-hash protected admission merges.

Source interpretation and unresolved mathematical qualification: The EHS82 fixed-epsilon linear-error construction is weaker than arbitrary divergent f(m); external stronger proof and pinned sorry remain unverified.

The explanation is accepted for publication of established background, examples, and explicitly attributed current claims. It does not establish or formally certify the disputed original theorem, external model-assisted proof, historical interpretation, or any unreplayed Lean kernel file. Original source-fidelity and proof-review research holds remain.

What remains

ERDOS-750-CLAIMED_FULL_STRENGTH_REVIEW. Retrieve the public claimed proof, inspect every dependency showing infinite chromatic number and the universal every-m-subgraph independent-set inequality for arbitrary f→∞. Compare to EHS82 linear error, and verify whether a proof has been independently certified. Distinguish the source-reported full solution from an independently certified proof until that scrutiny is complete.

Sources and claim boundaries

Maintained Problem #750; original GCL issue return. Full historical proof papers and external Lean kernels unreviewed. The public explanatory draft is protected-published, but no exact-hash V2 editorial admission or new GCL mathematical certificate is claimed.

Qualified editorial critical review: R10 source-exception dossier. The source-semantic exception is visible and its original research hold remains. Publication classification: REVIEWED EXPLANATORY ARTICLE WITH UNRESOLVED SOURCE/PROOF QUALIFICATIONS. Independent theorem proof or Lean certification: NOT CLAIMED.

Catalogue and evidence provenance

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

Back to catalogue · Compendium introduction