Claims

../

1980_11_01_ajtai_komlos_szemeredi: Theorem 2 of Ajtai, Komlós and Szemerédi (J. Combin. Theory Ser. A 1980): a triangle-free graph on n vertices with average degree t has an independent set of at least 0.01 (n/t) ln t vertices, the case r = 3 of the question.

2026_09_25_openai: Theorem 1.1 of the OpenAI release manuscript of 25 September 2026: for every fixed r at least 4, a K_r-free graph on n vertices with average degree d at least 2 has an independent set of at least c_r n log d / d vertices.

---