Is it true that any $K_r$-free graph on $n$ vertices with average degree $t$ contains an independent set on$${\gg }_r\frac{\log t}{t}n$$many vertices?

gpt-erdos · GPT-5.2 Pro + Deep Research · unverified

For **$r=3$** (triangle‑free graphs), **yes**: Ajtai–Komlós–Szemerédi proved that every triangle‑free $n$-vertex graph of average degree $t$ has an independent set of size (\Omega\left(\frac{\log t}{t}n\right)) [[nomath]](indeed they state an explicit constant like $0.01\cdot \frac{n}{t}\log t$)[[/nomath]].

llm-hunter · codex 5.2 extra high, gpt pro 5.2 · unverified

2 LLM attack(s) recorded (codex 5.2 extra high, gpt pro 5.2); unverified.