Problem 802

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?

Source: erdosproblems.com/802

Graph theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved. The site's label is OPEN with the remark that the problem cannot be resolved by a finite computation and an empty proof-claims tab. The question is settled by one accepted full claim, on its claim page (OpenAI, 2026): Theorem 1.1 of the OpenAI release manuscript of 25 September 2026 proves the bound for every fixed $r\ge4$ , its Lean declaration was built by this corpus's verification with the three standard axioms only, and this corpus's own statement-fidelity audit, part of that formalized evidence and not an outside review, found the formal statement faithful to the question; the frontmatter standing is derived from that page and from the accepted partial claim page Ajtai, Komlós and Szemerédi, the case $r=3$ . Before the release, the bounds in hand were: Theorem 2 of [AEKS81], $\alpha(G)>c_1\frac nt\log\frac{\log t}r$ , that is $\gg_r\frac{\log\log t}tn$ for fixed $r$ ; Shearer's improvement [Sh95] to $\gg_r\frac nt\cdot\frac{\log t}{\log\log t}$ (Corollary 2 of the paper; the paper says it does not settle the $\log t$ question), the best bound in the refereed record; the case $r=3$ , proved as Theorem 2 of [AKS80] ( $\alpha(G)\ge0.01\frac nt\ln t$ for triangle-free $G$ , sharp up to the constant for $t<n^{1/3+o(1)}$ by its Remark 2, and restated as Theorem 1 of [AEKS81]); and Alon's Theorem 1.1 [Al96b], the conjectured order under the stronger hypothesis that every vertex neighborhood is $(r-2)$ -colorable. The search, whose scope the Current assessment records, found no proof, disproof or claim at any $r\ge4$ ; the release postdates it.

AEKS81: Ajtai, M., Erdős, P., Komlós, J. and Szemerédi, E., On Turán's theorem for sparse graphs. Combinatorica 1 (1981), no. 4, 313--317, doi:10.1007/BF02579451 (Crossref record; received 24 April 1981). Theorem 1, display (3) and Theorem 2, p. 314; Theorem 1 $'$ , p. 315. Library home: Ajtai 1981; paged at Ajtai 1981, Theorem 1 (p. 314), Ajtai 1981, Theorem 2 (p. 314) and Ajtai 1981, Display (3) (p. 314).
AKS80: Ajtai, M., Komlós, J. and Szemerédi, E., A note on Ramsey numbers. J. Combin. Theory Ser. A 29 (1980), no. 3, 354--360, DOI 10.1016/0097-3165(80)90030-8. Theorem 2 and its Note, p. 355; the restatement and Remarks 2--3, pp. 357--358. Theorem 1 of [AEKS81] restates its theorem, attributing it to "[2] and [3]", this paper and the same authors' paper on a dense infinite Sidon sequence (European J. Combin. 2 (1981), 1--11; this paper's [1], "A quite different proof", not held). Library home: Ajtai and Szemerédi 1980; paged at Ajtai and Szemerédi 1980, Theorem 2.
Sh95: Shearer, J. B., On the independence number of sparse graphs. Random Structures Algorithms 7 (1995), no. 3, 269--271, doi:10.1002/rsa.3240070305 (Crossref record; received 12 July 1994, accepted 13 March 1995). Corollary 2, p. 271: $\alpha\ge c'(r)\,n\ln d/(d\ln\ln d)$ for $K_r$ -free graphs ( $r\ge4$ ) on $n$ vertices with average degree $d$ and large $d$ ; the introduction, p. 269, names the 1981 bound it improves and the $\ln d/d$ question it leaves open. Library home: Shearer 1995; paged at Shearer 1995, Corollary 2 and Shearer 1995, Corollary 1.
Al96b: Alon, N., Independence numbers of locally sparse graphs and a Ramsey type problem. Random Structures Algorithms 9 (1996), no. 3, 271--278, DOI 10.1002/(SICI)1098-2418(199610)9:3<271::AID-RSA1>3.0.CO;2-U (Crossref record). Theorem 1.1 and the introduction, pp. 1--2 of the author's preprint, whose pagination is not the journal's. Library home: Alon 1996; paged at Alon 1996, Theorem 1.1.
Sh83: Shearer, J. B., A note on the independence number of triangle-free graphs. Discrete Math. 46 (1983), no. 1, 83--87, DOI 10.1016/0012-365X(83)90273-X. Theorem 1, p. 83: $\alpha\ge n(d\ln d-d+1)/(d-1)^2$ for triangle-free graphs of average degree $d$ , the $r=3$ bound with an explicit constant, which [Al96b] (p. 1) cites as a simpler proof with a better constant; Remark 4 and the closing paragraph, p. 87, ask the $K_4$ -free question. Library home: Shearer 1983; paged at Shearer 1983, Theorem 1.
DJM25: Dhawan, A., Janzer, O. and Methuku, A., Independent sets and colorings of $K_{t,t,t}$ -free graphs. arXiv:2511.17191 (v1 21 November 2025; v2 4 December 2025, 24 pages). A preprint, known here by its abstract; a lead, recorded below.
Dh24: Dhawan, A., Bounds for the independence and chromatic numbers of locally sparse graphs. arXiv:2403.03054 (v3 21 July 2025), known here by its abstract. Context on locally sparse graphs; a lead by identifier.

Problem 802

Status

Proof claims

Discussion