Independence number of $K_r$-free graphs: is the AEKS $\frac{\log t}{t}n$ bound true for all $r$? (Erdős #802)
Statement
Fix $r\geq 3$. Is it true that every $K_r$-free graph on $n$ vertices with average degree $t$ contains an independent set (a set of pairwise non-adjacent vertices) of size $$\gg_r \frac{\log t}{t}\,n,$$ where the implied constant may depend on $r$? For triangle-free graphs ($r=3$) this $\frac{\log t}{t}$ dependence is a classical theorem; the conjecture asserts that the same order persists for every fixed forbidden clique size $r$. Prove it for all $r$, or find an $r$ for which it fails.
Acceptance. FULLY RESOLVES: prove or refute the conjecture. A proof must establish that for every fixed $r\geq 3$ there is a constant $c_r>0$ such that every $K_r$-free $n$-vertex graph of average degree $t$ has an independent set of size $\geq c_r\frac{\log t}{t}n$ (complete written proof, or machine-checkable formalization). A refutation must exhibit, for some fixed $r$, an explicit family of $K_r$-free graphs whose independence number is provably $o\big(\frac{\log t}{t}n\big)$, with the clique-freeness and independence number certified. ADVANCES: prove the conjectured bound for a new value of $r\geq 4$ under the genuine $K_r$-free hypothesis (not the stronger neighbourhood-chromatic condition), or improve the general lower bound beyond Shearer's $\frac{\log t}{\log\log(t+1)\,t}n$ stated in the background, with a full proof. Deliver the proof, or the counterexample family plus verification code.
Background
Conjectured by Ajtai, Erdős, Komlós, and Szemerédi [AEKS81], who proved the weaker independent-set lower bound $\gg_r \frac{\log\log(t+1)}{t}n$. Listed as open on erdosproblems.com/802 (fetched 2026-07-13, status 'open', tagged 'graph theory'; page last edited 26 October 2025). Shearer [Sh95] improved the general bound to $\gg_r \frac{\log t}{\log\log(t+1)\,t}n$, within a $\log\log$ factor of the conjecture. The full conjectured $\frac{\log t}{t}n$ bound is known in two cases: Ajtai, Komlós, and Szemerédi [AKS80] proved it for $r=3$ (triangle-free graphs), and Alon [Al96b] proved it under the stronger hypothesis that every vertex-neighbourhood induces a graph of chromatic number $\leq r-2$ (a local condition that implies $K_r$-freeness). The obstacle is bridging from such local/neighbourhood control to the genuine $K_r$-free hypothesis for $r\geq 4$. Attacker's tool: semi-random 'nibble' independent-set constructions and entropy-compression arguments for the lower bound; explicit or random $K_r$-free graphs with small independence number to probe sharpness.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #802 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.