Problem 636

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?

Source: erdosproblems.com/636

Graph theory
Ramsey theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved. The site labels the problem PROVED and its curator credits the proof to Kwan and Sudakov [KwSu21]. The status-defining source is Theorem 1.1 of Kwan and Sudakov [KwSu21], published in Trans. Amer. Math. Soc. 372 (2019), 5571--5594 (refereed; the editions cited are the authors' corrected arXiv v4 of 2021 and the published journal text): for fixed $C>0$ and $n$ large in terms of $C$ , every graph on $n$ vertices with no clique or independent set of $C\log n$ vertices has $\Omega_C(n^{5/2})$ induced subgraphs that pairwise differ in vertex count or edge count, the exponent the question asks for. Read depth: statement and application checked; no proof is reviewed in this corpus. The claim page Kwan and Sudakov 2017 records the result, its postings and the acceptance evidence; the frontmatter standing derives from it.

Er93: Erdős, Paul, Some of my favorite solved and unsolved problems in graph theory. Quaestiones Math. 16 (1993), 333--350. Chapter V, problem 14, printed p. 346: "Noga Alon and Bollobás asked: Assume $G(n)$ does not contain a trivial subgraph of size $c\log n$ . Does it then contain $cn^2$ induced subgraphs no two of which have the same number of edges and vertices. V.T. Sós and I proved this with $n^{3/2}$ , the truth is probably $n^{5/2}$ ", the question above as Erdős's guess. Library home: Erdős 1993.
Er97d: Erdős, P., Some recent problems and results in graph theory. Discrete Math. 164 (1997), 81--85; item 7, p. 83: Erdős writes that Sós, Faudree and he conjectured $cn^{5/2}$ induced subgraphs pairwise differing in vertex or edge count for a graph with no trivial subgraph of size $c\log n$ , that they proved $cn^{3/2}$ , and that $cn^{5/2}$ would be best possible; the site's attribution to the three authors follows this item. Library home: Erdős 1997.
KwSu21: M. Kwan and B. Sudakov, Proof of a conjecture on induced subgraphs of Ramsey graphs. Selected manuscript: arXiv:1712.05656v4 (2021). Published in Transactions of the American Mathematical Society 372 (2019), 5571--5594, DOI 10.1090/tran/7729.

Problem 636

Status

Proof claims

Discussion