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∼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.