Skip to content

Erdős Problem #1156

Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: open (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.

UNACCEPTED DRAFT — mathematical editorial review pending

This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.

Review the underlying draft on GitHub.

The question in plain language

Erdős Problem #1156. How tightly can the chromatic number of a binomial random graph concentrate, and how strongly must it spread out?

\[ G\sim G(n,\tfrac12),\qquad\chi(G)=\text{chromatic number of }G. \]

G∼G(n,1/2), with independently chosen edges. Ask whether some UNIVERSAL constant C has chi(G) concentrated on at most C integer values asymptotically. A second formulation asks whether for every arbitrary centering f(n) and slowly divergent omega(n), probability |chi(G)-f(n)|<omega(n) is <1/2 for all sufficiently large n. The two questions have different quantifiers; avoid calling them logically identical.

A small example

Exhaustive enumeration of all 8 graphs on 3 vertices gives chromatic distribution chi=1 with count1, chi=2 count6, chi=3 count1. All 64 labelled graphs on 4 vertices give histogram chi1:1, chi2:40, chi3:22, chi4:1. These exact finite distributions are not asymptotic concentration evidence.

What is known

https://www.erdosproblems.com/1156 OPEN [AlSp92],[Va99,3.6]. Bollobás [Bo88] chi(G)∼n/(2log_2 n) whp; Shamir–Spencer [ShSp87] concentration within much larger widths. Heckel [He21] proves whp concentration width omega(n) must exceed n^c infinitely often for every c<1/4, improved by Heckel–Riordan [HeRi23] to every c<1/2. These polynomial lower bounds on WHP windows do not literally imply the separately quantified <1/2 anti-concentration assertion. Review the exact 2023 theorem conditions.

GCL's current state

Authenticated original-issue source return establishes the bounded question, relevant external results, and independently tested finite fixture. The reproducible checks are in ci/erdos_compendium_007_phase18_checks.py.

The source return disposition is PARTIAL. Neither an original-paper proof review nor any Lean kernel replay or protected editorial acceptance has been completed.

What remains

ERDOS-1156-CHROMATIC-CONCENTRATION-001: pin Heckel/Riordan 2023 proof, verify concentration width/n^c exponent and failure infinitely often vs eventually. Derive exact small-n chromatic distributions and rigorously test non-equivalence of whp window width and <1/2 window claim.

Both strong formulations OPEN; modern results external pending source-proof review.

Sources and claim boundaries

https://www.erdosproblems.com/1156 ; [Bo88],[ShSp87],[He21],[HeRi23]; exhaustive finite graph enumeration.

This is a locally validated, UNACCEPTED editorial draft. Assertions beyond the exact finite checks are attributed to original external sources and remain subject to source-fidelity review.

Catalogue and evidence provenance

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