Problem Statement
Suppose $G$ is a graph on $n$ vertices which contains no complete graph or independent set on $\gg \log n$ many vertices. Must $G$ contain $\gg n^{5/2}$ induced subgraphs which pairwise differ in either the number of vertices or the number of edges?
Categories:
Graph Theory Ramsey Theory
Progress
A problem of Erdős, Faudree, and Sós, who proved there exist $\gg n^{3/2}$ many such subgraphs, and note that $n^{5/2}$ would be best possible. (Although in [Er93] Erdős credits this question to Alon and Bollobás.)This was proved by Kwan and Sudakov [KwSu21].
Source: erdosproblems.com/636 | Last verified: January 15, 2026