Problem Statement
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.
Categories:
Graph Theory Ramsey Theory
Progress
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).
Source: erdosproblems.com/637 | Last verified: January 15, 2026