Order type $\omega_2^2$, chromatic number $\aleph_2$, lesser-type subgraphs countably chromatic? (Erdős #919)
Statement
Is there a graph $G$ whose vertex set is well-ordered with order type $\omega_2^2$ (the ordinal square, i.e. pairs ordered lexicographically) and which has chromatic number $\aleph_2$, such that every subgraph whose vertex set has order type less than $\omega_2^2$ has chromatic number $\leq \aleph_0$? What if instead we ask for $G$ to have chromatic number $\aleph_1$? (The chromatic number of an infinite graph is the least cardinal $\kappa$ admitting a proper colouring with $\kappa$ colours.)
Acceptance. FULLY RESOLVES: for the first question, a ZFC proof of existence (a construction with full proofs that the chromatic number is $\aleph_2$ and that every subgraph of vertex order type $<\omega_2^2$ has chromatic number $\leq\aleph_0$) or of non-existence; or a clearly-flagged proof of independence from ZFC (consistency both ways). Resolving the $\aleph_1$ variant analogously completes the second question. Machine-checkable (Lean/Coq) proof preferred, else a complete written proof. ADVANCES: (a) resolve either question under a stated additional axiom (GCH, $V=L$, ...), clearly flagged; (b) resolve the second ($\aleph_1$) question alone; (c) sharpen the analysis of the Erdős–Hajnal $\omega_2^2$ construction described in the background — e.g. prove that its lesser-type subgraphs cannot all be countably chromatic, or that some modification achieves it; (d) a Lean formalisation, with proof, of the $\omega_1^2$ construction and its two properties. Deliver the proof file (Lean preferred) or the complete written proof including the construction.
Background
Posed by Erdős [Er69b]; listed as open on erdosproblems.com/919 (fetched 2026-07-13, status 'open', tagged 'graph theory | chromatic number'). The question is inspired by a theorem of Babai: every graph on a well-ordered vertex set with chromatic number $\geq\aleph_0$ contains a subgraph on vertices of order type $\omega$ with chromatic number $\aleph_0$. Erdős and Hajnal showed this does not generalise to higher cardinals: they constructed (see [Er69b]) a graph on $\omega_1^2$ with chromatic number $\aleph_1$ in which every subgraph of strictly smaller order type has chromatic number $\leq\aleph_0$ — the vertices are the pairs $(x_\alpha,y_\beta)$ for $1\leq\alpha,\beta<\omega_1$, ordered lexicographically, with $(x_{\alpha_1},y_{\beta_1})$ joined to $(x_{\alpha_2},y_{\beta_2})$ if and only if $\alpha_1<\alpha_2$ and $\beta_1<\beta_2$. The analogous construction on $\omega_2^2$ yields chromatic number $\aleph_2$, but its lesser-type subgraphs are only known to have chromatic number $\leq\aleph_1$; the problem asks whether the drop can be pushed all the way to $\leq\aleph_0$, or (second question) whether chromatic number $\aleph_1$ on $\omega_2^2$ is achievable with countably chromatic lesser-type subgraphs. Closely related to Erdős #918 (erdosproblems.com/918), which poses the cardinality (rather than order-type) version. The attacker's tool: infinite combinatorics — refined lexicographic/shift-type constructions for existence, partition-calculus and elementary-submodel arguments for non-existence, and set-theoretic independence techniques if the answer is model-dependent.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #919 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #918 (T. F. Bloom) — the cardinality version of this question | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.