Tags
Prizes
More
FAQ
Problem Lists
Definitions
Links
How to help
Go
Go
All
Random Solved
Random Open
SOLVED
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.
#801
:
[Er79g]
graph theory
,
ramsey theory
Proved by Alon
[Al96b]
.
Previous
Next