Problem 801

If $G$ is a graph on $n$ vertices containing no independent set on $>n^{1/2}$ vertices then there is a set of $\leq n^{1/2}$ vertices containing $\gg n^{1/2}\log n$ edges.

Source: erdosproblems.com/801

Graph theory
Ramsey theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

The site labels the problem PROVED and its curator credits Alon [Al96b]. Alon's Theorem 1.2: if $\alpha(G)<\lfloor\sqrt n\rfloor$ for a graph $G$ on $n$ vertices, some set of $\lfloor\sqrt n\rfloor$ vertices spans $\Omega(\sqrt n\log n)$ edges; "This is tight and settles a problem of Erdös [4]", the tightness being Proposition 3.1 (for every $1<m\le n$ a graph with $\alpha(G)<m$ in which every $m$ -set spans at most $cm\ln(en/m)$ edges). Published in Random Structures Algorithms 9 (1996), 271--278 (refereed); the pages cited are the author's preprint's, which lacks the journal pagination and was not compared with the journal text. Read depth: claims checked for Theorem 1.2 and Proposition 3.1; the proof of Theorem 1.2 was read for its structure and not reviewed. The frontmatter standing is derived from the claim pages: Alon's theorem is an accepted full claim on the site curator's acceptance and its refereed publication (claim page (Alon, 1996)).

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. Theorem 1.2, p. 2 of the author's preprint; the proof, pp. 5--6; Proposition 3.1, p. 6; the $f(m,n)$ paragraph, p. 7. Library home: Alon 1996.
Er79g: Erdős, P., Some old and new problems in various branches of combinatorics. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Boca Raton, 1979), Congressus Numerantium 23 (1979), 19--37. Library home: Erdős 1979, the author's typescript in the Rényi Institute Erdős archive (18 pages; the passage is on the page headed 15, the typescript's fourteenth page, recorded on its Erdős 1979, Problem (p. 15) page; the journal pagination is not in the typescript).
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, printed p. 355 (p. 2 of the publisher's open-archive PDF): $\alpha(G)\ge0.01(n/t)\ln t$ for a triangle-free graph with $n$ vertices and average degree $t$ ; used inside Alon's proof. Library home: Ajtai and Szemerédi 1980; paged at Ajtai and Szemerédi 1980, Theorem 2.
Va: Valtr, P., in preparation (Alon's reference [9]); Theorem 3.3 of [Al96b], $f(m,n)=\Omega(m\log(n/m))$ for $\log n\le m\le n/2$ , is attributed to it. An announcement in the source, not a citable result here.

Problem 801

Status

Proof claims

Discussion