{"id":"openai-math/A-Logarithmic-Independence-Bound-for-Clique-Free-Graphs","pdf":"https://github.com/openai/math/blob/main/preprints/A-Logarithmic-Independence-Bound-for-Clique-Free-Graphs-September-25-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/A-Logarithmic-Independence-Bound-for-Clique-Free-Graphs-September-25-2026","tags":["graph-theory","independence-number","combinatorics"],"score":0,"title":"A logarithmic independence bound for clique-free graphs","domain":"Combinatorics","family":"184","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"math.CO","summary":"For every fixed integer r ≥ 4, every 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`$, where $`c_r\\gt 0`$ depends only on r . This proves the fixed-clique-size independence conjecture of Ajtai, Erdős, Komlós and Szemerédi.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-25","reactions":{},"formalized":true,"family_title":"Correspondence coloring with a fixed forbidden subgraph"}