Erdős Problem 111: graphs that are not countably colorable need superlinear deletions to become bipartite

A Lean-checked proof that if every finite subgraph on $m$ vertices of a graph can be made bipartite by deleting at most $Cm$ edges, the graph is countably colorable, so $h_G(n)/n \to \infty$ for every graph of chromatic number $\aleph_1$, answering the second question of Erdős Problem 111; the proof was found by GPT-6 Astra and Claude Opus 5.5 in alternation.

What was found

For a graph $G$, $h_G(n)$ is the least number such that every subgraph on $n$ vertices can be made bipartite by deleting at most $h_G(n)$ edges. Erdős, Hajnal and Szemerédi showed that $h_G(n) \gg n$ for every graph of chromatic number $\aleph_1$ and built such graphs with $h_G(n) \le 2n^{3/2}$, and Erdős asked whether $h_G(n)/n \to \infty$. The proof builds random sign assignments along a continuous chain of closed vertex sets, forces each vertex with an infinite trace to oppose its derived sign, passes to limits along an ultrafilter, and splits the resulting signs, as unit vectors in $L^2$, into countably many classes within which greedy coloring succeeds. Per the repository, Claude Opus 5.5 wrote the first complete proof and GPT-6 Astra checked and revised it, and Claude Opus 5.5 then wrote the Lean. The first, open-ended question of the problem, the exact growth of $h_G(n)$, is not addressed.

Novelty check

On 2026-10-20 erdosproblems.com listed Problem 111 as open with no proof claims. The repository records its own search of 17 October, of arXiv, the web and Formal Conjectures, which has no merged statement of the problem and two open pull requests that state it without proof. An Erdős Problem a Day report of 26 July 2026 proves the reduction of the limit to the finite-density form for graphs of chromatic number $\aleph_1$, by the same countable-deletion and packing argument, but does not solve the problem; the repository says its argument does not rely on it.

Machine-checked elsewhere

Graded claimed for verification and ai-led for autonomy. What these mean.

Cite this entry

whataifound.org. (2026). Erdős Problem 111: graphs that are not countably colorable need superlinear deletions to become bipartite. whataifound.org: A Registry of AI Scientific and Mathematical Discoveries. https://whataifound.org/finding/2026-10-19-erdos-111-bipartization

@misc{whataifound-plasmaai-2026-bipartization,
  title        = {Erdős Problem 111: graphs that are not countably colorable need superlinear deletions to become bipartite},
  author       = {{whataifound.org}},
  year         = {2026},
  howpublished = {whataifound.org: A Registry of AI Scientific and Mathematical Discoveries},
  note         = {Result by Plasma AI. Verification: Claimed. Autonomy: AI-led.},
  url          = {https://whataifound.org/finding/2026-10-19-erdos-111-bipartization}
}

Related findings

← All mathematics findings in the registry