Logo
All Random Solved Random Open
SOLVED
If $G$ is a graph on $n$ vertices which contains no complete graph or independent set on $\gg \log n$ vertices then $G$ contains an induced subgraph on $\gg n$ vertices which contains $\gg n^{1/2}$ distinct degrees.
A problem of Erdős, Faudree, and Sós.

This was proved by Bukh and Sudakov [BuSu07].

Jenssen, Keevash, Long, and Yepremyan [JKLY20] have proved that there must exist an induced subgraph which contains $\gg n^{2/3}$ distinct degrees (with no restriction on the number of vertices).

Additional thanks to: Zach Hunter