← All problems

Erdős Problem #750 — Infinite-chromatic graphs with large local independent sets

56 years old · documented by

Let f(m)f(m) be some function such that f(m)→∞f(m)\to \infty as m→∞m\to \infty. Does there exist a graph GG of infinite chromatic number such that every subgraph on mm vertices contains an independent set of size at least m2−f(m)\frac{m}{2}-f(m)?

References

Progress summary

Refreshed
Open · solution reported

A claimed AI-generated construction would settle the problem, but no independently verified proof has yet appeared.

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)≥cmf(m)\geq cm for every c>1/4c>1/4.
  • Erdős–Hajnal–Szemerédi (1982) proved the stronger special case f(m)=ϵmf(m)=\epsilon m for fixed ϵ>0\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.

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

Sources

Solutions 0

No solutions have been posted yet.