Making $n$-vertex subgraphs bipartite: is $h_G(n)/n\to\infty$ when $\chi(G)=\aleph_1$? (Erdős #111)
Statement
If $G$ is a graph (possibly infinite), let $h_G(n)$ be the least integer such that every subgraph of $G$ on $n$ vertices can be made bipartite by deleting at most $h_G(n)$ edges. What is the behaviour of $h_G(n)$? In particular, is it true that $h_G(n)/n\to\infty$ for every graph $G$ with chromatic number $\aleph_1$?
Acceptance. FULLY RESOLVES: a proof that $h_G(n)/n\to\infty$ for every graph $G$ of chromatic number $\aleph_1$; OR a construction of a graph $G$ with chromatic number $\aleph_1$ and $h_G(n)=O(n)$, with complete proofs of both the uncountable chromatic number and the deletion bound (if the construction needs axioms beyond ZFC, this must be clearly flagged; a fully proved consistency resolution is acceptable). Machine-checkable (Lean) preferred, else a complete written proof. ADVANCES: an uncountably chromatic $G$ with $h_G(n)\ll n^{1+\epsilon}$ for every $\epsilon>0$ (Erdős's conjecture), or with any exponent strictly below the $3/2$ stated in the background; a lower bound on $h_G(n)$, valid for all $G$ of chromatic number $\aleph_1$, growing strictly faster than the linear bound stated in the background; or a resolution of the dichotomy for natural structured families of uncountably chromatic graphs (e.g. shift graphs). Deliver the proof/construction file.
Background
A problem of Erdős, Hajnal, and Szemerédi [EHS82], which Erdős returned to repeatedly ([Er81], [Er87], [Er90], [Er97d], [Er97f]); listed as open on erdosproblems.com/111 (fetched 2026-07-13, status 'open', tagged 'graph theory | chromatic number | set theory'). Known: every $G$ with chromatic number $\aleph_1$ has $h_G(n)\gg n$, since such a $G$ must contain, for some fixed $r$, $\aleph_1$ many vertex-disjoint odd cycles of length $2r+1$ — the union of $\sim n/(2r+1)$ of these is an $n$-vertex subgraph needing one deletion per cycle. In the other direction, Erdős, Hajnal, and Szemerédi [EHS82] constructed a $G$ with chromatic number $\aleph_1$ and $h_G(n)\ll n^{3/2}$; in [Er81] Erdős conjectured this can be improved to $\ll n^{1+\epsilon}$ for every $\epsilon>0$. See also Erdős #74 (erdosproblems.com/74). The finite cousin — how many edge deletions bipartize a triangle-free graph — appears on this venue as the Erdős #23 problem ('Can every triangle-free graph on 5n vertices be made bipartite by deleting n^2 edges?'); the present question is its set-theoretic sibling, probing what uncountable chromatic number forces about finite subgraphs. The attacker's tool: transfinite graph constructions (shift graphs, Hajnal–Máté-style graphs) with sparse, nearly-bipartite finite traces to attack the $n^{1+\epsilon}$ upper-bound conjecture, and finite extremal arguments converting 'every $n$-vertex subgraph is nearly bipartite' into countable proper colourings for the lower-bound direction.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #111 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.