AI Proof WatchKeep up with AI contributions

Erdős Problem 111: bipartizing finite subgraphs of uncountably chromatic graphs

If a graph is not countably colorable, h_G(n)/n tends to infinity, where h_G(n) is the largest minimum number of edge deletions needed to make an n-vertex subgraph bipartite. Equivalently, a uniform linear deletion bound on all finite subgraphs forces countable colorability. The limit holds for the whole sequence, for graphs of any uncountable chromatic cardinality.

Sources for this record

What was already known

Erdős, Hajnal and Szemerédi asked about finite bipartization costs in graphs of chromatic number ℵ₁. The 1981 formulation asked for unbounded ratios; the 1987 question asked for divergence. The source claims the full limit without a rate.

AI involvement AI-autonomous

Plasma AI reports unattended alternating research runs by GPT-6 Astra and Claude Opus 5.5 that found the argument. Human direction covered the target and formalization/publication setup; no human mathematical proof input is recorded. The original research contribution, rather than the later formalization management, supports AI-autonomous.

Importance Notable

Resolves the specified longstanding Erdős question, subject to the stated scope. The earlier theorems and later human work retain their credit.

Limitations

No quantitative divergence rate or complete description of possible growth functions is supplied. The named human lead checked statement correspondence; the argument, review and formalization are attributed to agents. No outside human proof review or explanation is documented.

Technical verification Formal (Lean)

Palomar reports exact selected-statement comparison and kernel checking with Lean, NanoDa and con-ron on 19 October. No local proof rebuild was performed.

Formal checking

Palomar reports exact selected-statement comparison and kernel checking with Lean, NanoDa and con-ron on 19 October. No local proof rebuild was performed.

Checker
Palomar: Lean, NanoDa and con-ron
Scope
countably_colorable_of_linear, tendsto_of_not_countably_colorable and erdos_111; arbitrary vertex cardinality in the general statement, and chromatic cardinal ℵ₁ in the named corollary; standard Lean axioms only.
Basis
Reported by the linked checker
Check date
2026-10-19
Evidence source

Checking a formal statement does not establish that it matches the original problem.

Human understanding Few

Few is the default when evidence for a higher level is insufficient. The available blueprint and proof reviews are AI-produced. Human statement correspondence checks do not document a human explanation of the central argument. Few is the evidence default.

Correction and publication history

2026-10-19 · publication

Added this sourced contribution with its stated scope, AI attribution, checking evidence and research limits.

Read this published revision