Subgraphs of the same infinite chromatic number avoiding short odd cycles (Erdős #740)
Statement
Let $\mathfrak{m}$ be an infinite cardinal and $G$ be a graph with chromatic number $\mathfrak{m}$. Let $r\geq 1$. Must $G$ contain a subgraph of chromatic number $\mathfrak{m}$ which does not contain any odd cycle of length $\leq r$? (Since the shortest odd cycle has length 3, the question is nontrivial for $r\geq 3$.)
Acceptance. FULLY RESOLVES: a complete proof that for every infinite cardinal $\mathfrak{m}$, every graph of chromatic number $\mathfrak{m}$, and every $r$, such a subgraph exists; or a counterexample — a graph of chromatic number $\mathfrak{m}$ for some specific infinite $\mathfrak{m}$ and $r$, with a proof that every subgraph of chromatic number $\mathfrak{m}$ contains an odd cycle of length $\leq r$; or a proof that the statement (for some specific $\mathfrak{m}, r$) is independent of ZFC. Machine-checkable proof (Lean/Coq) preferred; otherwise a complete written proof with all steps. ADVANCES: any new case beyond Rödl's $\mathfrak{m}=\aleph_0$, $r=3$ theorem stated in the background (e.g. all finite $r$ at $\aleph_0$, or $r=3$ at $\aleph_1$ or all cardinals); a proof or refutation of any new case of the stronger Erdős–Hajnal $f_r(\mathfrak{m})$ formulation; progress on the girth variant; or a Lean formalization of Rödl's theorem. Deliver the proof file or the formalization artifact (Lean sources that compile against a stated toolchain).
Background
A question of Erdős and Hajnal, raised repeatedly by Erdős across [Er69b], [Er71], [Er81], and [Er95d]; listed as open on erdosproblems.com/740 (fetched 2026-07-13, status 'open', tagged 'graph theory | chromatic number'). Rödl proved the answer is yes when $\mathfrak{m}=\aleph_0$ and $r=3$; the finitary version of that statement is Erdős #108 (erdosproblems.com/108). More generally, Erdős and Hajnal asked whether for every infinite cardinal $\mathfrak{m}$ and integer $r$ there exists $f_r(\mathfrak{m})$ such that every graph with chromatic number $\geq f_r(\mathfrak{m})$ contains a subgraph of chromatic number $\mathfrak{m}$ with no odd cycle of length $\leq r$. Erdős [Er95d] emphasized that even the $r=3$ case of this stronger form is open: must every graph of sufficiently large chromatic number contain a triangle-free subgraph of chromatic number $\mathfrak{m}$? In [Er81] Erdős posed the girth variant, where the subgraph must avoid all cycles (odd and even) of length $\leq r$. Beyond Rödl's $\aleph_0$, $r=3$ theorem no further cases appear in the site's commentary. The attacker's tool: infinite combinatorics — transfinite colouring and elementary-submodel arguments in the Erdős–Hajnal partition-calculus tradition, building on Rödl's proof; the problem is purely proof-shaped (potentially independence-prone at large cardinals) with no computational purchase, though a Lean formalization of Rödl's theorem would be a concrete first artifact.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #740 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.