Does large chromatic number force triangle-free subgraphs of chromatic number $\kappa$? (Erdős #1175)
Statement
Let $\kappa$ be an uncountable cardinal. Must there exist a cardinal $\lambda$ such that every graph with chromatic number $\lambda$ contains a triangle-free subgraph with chromatic number $\kappa$? (Triangle-free: containing no three pairwise adjacent vertices.)
Acceptance. FULLY RESOLVES: a ZFC proof that for every uncountable cardinal $\kappa$ there is a cardinal $\lambda$ such that every graph of chromatic number $\lambda$ contains a triangle-free subgraph of chromatic number $\kappa$; OR a proof that a negative answer is consistent in full strength — a model of ZFC containing an uncountable $\kappa$ such that for every cardinal $\lambda$ some graph of chromatic number $\lambda$ has no triangle-free subgraph of chromatic number $\kappa$; OR a proof of outright independence combining both directions. All use of axioms beyond ZFC must be clearly flagged. Machine-checkable (Lean 4; a formal statement exists) preferred, else a complete written proof. ADVANCES: settling the principal case $\kappa=\aleph_1$ (exhibiting a $\lambda$ that provably or consistently works, or extending Shelah's $\lambda=\aleph_1$ consistency result stated in the background to larger explicit $\lambda$); a positive answer under clearly flagged large-cardinal or forcing-axiom hypotheses; or the analogous problem with triangle-free strengthened to larger odd girth, strictly beyond the results stated in the background or properly cited literature. Deliver the proof file.
Background
Catalogued from the reference [Va99, 7.92]; listed as open on erdosproblems.com/1175 (fetched 2026-07-13, status 'open', tagged 'set theory | chromatic number'). This is the transfinite analogue of a classical finite phenomenon: by a theorem of Rödl, for every finite $k$ every graph of sufficiently large chromatic number contains a triangle-free subgraph of chromatic number at least $k$. The question is whether any such behaviour survives at uncountable cardinals. Known frontier (from the page): Shelah proved that a negative answer is consistent for $\kappa=\lambda=\aleph_1$ — that is, consistently there is a graph of chromatic number $\aleph_1$ all of whose triangle-free subgraphs have chromatic number at most $\aleph_0$, so $\lambda=\aleph_1$ does not suffice for $\kappa=\aleph_1$. Whether some larger $\lambda$ works — provably in ZFC, consistently, or under large-cardinal hypotheses — is open. Closely related in spirit to the unavoidable-substructure problems for uncountably chromatic hypergraphs, Erdős #593 (erdosproblems.com/593) and Erdős #1177 (erdosproblems.com/1177). A Lean formal statement exists in google-deepmind/formal-conjectures. The attacker's tool: set-theoretic constructions and forcing — either extending Shelah's consistency result to kill every candidate $\lambda$ for some uncountable $\kappa$, or reflection/compactness arguments (e.g. at strongly compact cardinals) producing a $\lambda$ that provably or consistently works.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1175 (T. F. Bloom) | website |
| REF-02 | Lean formal statement (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.