Let f(m) be some function such that f(m)→ ∞ as m→ ∞. Does there exist a graph G of infinite chromatic number such that every subgraph on m vertices contains an independent set of size at least fracm2-f(m)?

Erdős Problem #750 — Let f(m) be some function such that f(m)→ ∞ as m→ ∞.

Erdős Problem #750, recorded in 1994–1995, asks whether an infinite-chromatic graph can have an independent set nearly half as large as every finite subgraph. The page also records earlier linear-error versions.

Known results

Erdős–Hajnal proved the claim when $f(m)\geq cm$ for every $c>1/4$ .
Erdős–Hajnal–Szemerédi (1982) proved the stronger special case $f(m)=\epsilon m$ for fixed $\epsilon>0$ , via large induced bipartite subgraphs.

May–July 2026 claimed construction

Chojecki’s prompting of GPT-5.5 Pro allegedly produced a construction using generalized Mycielski graphs and vertex odd-cycle transversals, yielding the required local bounds. A Lean formalization is reported, but it uses Stiebitz’s theorem as an axiom; the available Lean statement still contains sorry, and no independent publication or proof artifact was found.

Current status (as of July 2026): A full solution is claimed, but absent independent verification, Problem #750 remains mathematically unconfirmed.

Erdős Problem #750 — Let $f(m)$ be some function such that $f(m)\to \infty$ as $m\to \infty$ .

Primary source

Additional references

Progress summary

Solutions 0