A graph of chromatic number $\aleph_2$ whose $\aleph_1$-vertex subgraphs are countably chromatic (Erdős #918)
Statement
For an infinite graph, the chromatic number is the least cardinal $\kappa$ such that the vertices can be properly coloured with $\kappa$ colours. Is there a graph with $\aleph_2$ vertices and chromatic number $\aleph_2$ such that every subgraph on $\aleph_1$ vertices has chromatic number $\leq\aleph_0$? Is there a graph with $\aleph_{\omega+1}$ vertices and chromatic number $\aleph_1$ such that every subgraph on $\aleph_\omega$ vertices has chromatic number $\leq\aleph_0$?
Acceptance. FULLY RESOLVES: for the first question, a ZFC proof that such a graph exists (a construction with full proofs that its chromatic number is $\aleph_2$ and that every subgraph on $\aleph_1$ vertices has chromatic number $\leq\aleph_0$) or a ZFC proof that none exists; or a proof that the statement is independent of ZFC (consistency in both directions via forcing/inner models, clearly flagged as an independence result). Machine-checkable (Lean/Coq) proof preferred, else a complete written proof with all steps. ADVANCES: (a) resolve either question under a stated additional hypothesis (e.g. GCH, $V=L$, MA, a large-cardinal assumption), clearly flagged; (b) resolve the second ($\aleph_{\omega+1}$) question in either direction; (c) strengthen the Erdős–Hajnal companion theorem stated in the background (e.g. a single graph of chromatic number $\aleph_1$ all of whose subgraphs on fewer than $\aleph_\omega$ vertices are countably chromatic); (d) a Lean formalisation, with proof, of the Erdős–Hajnal companion theorem. Deliver the proof file (Lean preferred) or the complete written proof including the construction.
Background
A question of Erdős and Hajnal [ErHa68b], restated in [Er69b, p.28]; listed as open on erdosproblems.com/918 (fetched 2026-07-13, status 'open', tagged 'graph theory | chromatic number'; page last edited 24 October 2025). Erdős and Hajnal proved the companion theorem that for every finite $k$ there is a graph with chromatic number $\aleph_1$ in which every subgraph on fewer than $\aleph_k$ vertices has chromatic number $\leq\aleph_0$; the two questions ask whether the whole graph's chromatic number can be pushed up to $\aleph_2$ (first form) or the smallness threshold pushed out to $\aleph_\omega$ (second form). The [Er69b] printing asked for chromatic number exactly $\aleph_0$, but, as the site records (observation of louisd in the comments), that version is trivially impossible when 'subgraph' is not restricted to induced subgraphs, so the intended form is the one given here, as posed in [ErHa68b]. Questions in this genus (chromatic spectra of uncountably chromatic graphs) interact deeply with cardinal arithmetic and independence: Baumgartner proved (1984, by a forcing construction) that it is consistent with ZFC + GCH that such a graph exists — one of size and chromatic number $\aleph_2$ all of whose subgraphs of size $<\aleph_2$ are countably chromatic — a consistent positive answer to the first question, so what remains is whether such a graph provably exists in ZFC or whether its non-existence is also consistent (which would make the statement independent). The statement has been formalised in Lean in the google-deepmind/formal-conjectures repository (ErdosProblems/918.lean). The attacker's tool: infinite combinatorics — elementary-submodel and chain arguments toward non-existence, and forcing or GCH-style hypotheses for consistency results — with Lean formalisation of any partial theorem as the checkable artifact.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #918 (T. F. Bloom) | website |
| REF-02 | Formalised statement of Erdős #918 (Lean, google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.