Independent-set bounds in clique-free graphs
Follow the latest progress by email.
For fixed r≥4, must every finite K_r-free graph on n vertices with average degree d≥2 contain an independent set of size at least c_r n log(d)/d, with c_r>0 independent of n and d?
Why it matters and what counts as progress
Why it matters: Removing the log-log denominator would extend the triangle-free logarithmic independence scale to every fixed forbidden clique.
What counts as progress: Remove the log-log loss in the general average-degree bound, improve constants or prove a constructive version under stated assumptions.
How the problem developed
- 1981 · Partial result [1]
Ajtai, Erdős, Komlós and Szemerédi Their sparse-graph theorem improved the Turán bound for graphs containing no large cliques; the strongest logarithmic conclusion concerned triangle-free graphs, not all fixed clique sizes.
- 25 Sept 2026 · Reported claim [2]
OpenAI The preprint claims that for every fixed r≥4, a K_r-free graph with n vertices and average degree d≥2 has an independent set of size at least c_r n log(d)/d.
AI contribution
A logarithmic independence bound for clique-free graphs
Theorem 1.1 claims that for every fixed integer r ≥ 4, each finite K_r-free graph on n vertices with average degree d ≥ 2 has an independent set of size at least c_r n log(d)/d, with c_r > 0 independent of n and d. It removes a log-log denominator in the fixed-clique-size average-degree bound; the paper does not optimize c_r or give an efficient algorithm.
Sources
- Ajtai, Erdős, Komlós and Szemerédi, On Turán’s theorem for sparse graphs
- OpenAI: logarithmic independence bound for clique-free graphs
- A logarithmic independence bound for clique-free graphs
- Lean scope for the independence bound
- Erdős Problems: independent Lean claim audit
- OpenAI mathematics release account
Website timeline
Publication dates and editorial changes.