Revision history of
636. All highlighted changes are compared to the current version.
Current version
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?
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].
2025-10-20 00:00:00
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?
A problem of Erdős, Faudree, and S\'{o}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\'{a}s.)
This was proved by Kwan and Sudakov
[KwSu21].
