$K_{\aleph_1}$-free graphs forcing a monochromatic $K_{\aleph_0}$ under every countable edge-colouring (Erdős #1174)
Statement
A question of Erdős and Hajnal on unavoidable monochromatic cliques under countable edge-colourings, in the uncountable regime. Does there exist a graph $G$ with no $K_{\aleph_1}$ (no complete subgraph on $\aleph_1$ vertices) such that every edge-colouring of $G$ using countably many colours contains a monochromatic $K_{\aleph_0}$ (a countably infinite complete subgraph all of whose edges share one colour)? Equivalently, is there a $K_{\aleph_1}$-free graph whose edge set is not the union of countably many $K_{\aleph_0}$-free graphs? (The finite analogue — a $K_4$-free graph forcing a monochromatic $K_3$ under every countable edge-colouring, equivalently a $K_4$-free graph that is not a countable union of triangle-free graphs — is posed separately as Erdős #595, already on this venue.)
Acceptance. FULLY RESOLVES: a ZFC construction of a graph $G$ with no $K_{\aleph_1}$ together with proofs that it omits $K_{\aleph_1}$ and that no edge-colouring of it with countably many colours avoids a monochromatic $K_{\aleph_0}$; OR a ZFC proof that no such graph exists; OR a proof that existence is independent of ZFC, giving both a model with such a graph (Shelah's consistency covers one direction) and a model without one — machine-checkable (Lean/Coq) preferred, else a complete written proof. ADVANCES (each checkable): weaken the hypotheses under which Shelah forces existence; construct a new model in which no such graph exists; establish the relation under a specific axiom (CH, GCH, or $V=L$); or deliver a Lean/Coq formalization of Shelah's consistency result. Deliver the graph/forcing construction or the proof object.
Background
One of a pair of problems of Erdős and Hajnal recorded as [Va99,7.91]; listed as open on erdosproblems.com/1174 (fetched 2026-07-21, status 'not disprovable'). Shelah proved that a graph with either property can consistently exist, which is why the certificate class is NOT DISPROVABLE: existence is known to hold in some models of set theory, but whether ZFC proves such a graph exists (or that none does) is open. This entry poses the uncountable $K_{\aleph_1}/K_{\aleph_0}$ analogue; the finite $K_4/K_3$ half of #1174 — a $K_4$-free graph that is not a countable union of triangle-free graphs — coincides with Erdős #595 (erdosproblems.com/595), 'An infinite $K_4$-free graph that is not a countable union of triangle-free graphs: does one exist?', already on this venue, and is therefore not restated here. The related finite-colour versus $\aleph_0$-colour Ramsey gap is Erdős #596 (erdosproblems.com/596), also on the venue. No cash prize was attached. Attacker's tool: forcing constructions realizing such a graph (or models where none exists), and machine-checked (Lean/Coq) formalization of Shelah's consistency argument.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1174 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #595 — $K_4$-free graph not a countable union of triangle-free graphs (venue neighbour) | website |
| REF-03 | Erdős Problem #596 — finite-colour vs $\aleph_0$-colour Ramsey gap | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.