Problem 637

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.

Source: erdosproblems.com/637

Graph theory
Ramsey theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved. Bukh and Sudakov's Theorem 1.1 [BuSu07] is the statement, published in J. Combin. Theory Ser. B 97 (2007), 612--619 (refereed). Jenssen, Keevash, Long and Yepremyan's Theorem 1 [JKLY20] strengthens the count from $\Omega_C(n^{1/2})$ to $\Omega_C(n^{2/3})$ for an induced subgraph of unrestricted size, in Proc. Amer. Math. Soc. 148 (2020), 3835--3846 (refereed; the edition cited is the arXiv v1); the order $n^{2/3}$ is the largest possible by Bukh and Sudakov's Proposition 2.4 (the random graph $G(n,1/2)$ ), so it is tight, for Ramsey graphs and for $G(n,1/2)$ , on those two published results. The site labels the problem PROVED and its curator credits the proof to Bukh and Sudakov. Read depth: claims checked for both theorems, and Section 2 of [JKLY20] for the observation under "The exponent and the strengthening"; no proof is reviewed here. The claim page Bukh and Sudakov 2006 records the result, its postings and the acceptance evidence; the frontmatter standing derives from it.

BuSu07: Bukh, B. and Sudakov, B., Induced subgraphs of Ramsey graphs with many distinct degrees. J. Combin. Theory Ser. B 97 (2007), no. 4, 612--619, DOI 10.1016/j.jctb.2006.09.006. Theorem 1.1, p. 613; the remark on the exponent and Proposition 2.4, p. 616. Library home: Bukh and Sudakov 2007.
JKLY20: Jenssen, M., Keevash, P., Long, E. and Yepremyan, L., Distinct degrees in induced subgraphs. Proc. Amer. Math. Soc. 148 (2020), no. 9, 3835--3846, DOI 10.1090/proc/15060; arXiv:1910.01361v1 (3 October 2019), the edition cited. Theorem 1 and the definition of $f(G)$ , p. 2 of the preprint. Library home: Jenssen et al. 2020.
Er92b: Erdős, P., Some of my favourite problems in various branches of combinatorics. Matematiche (Catania) 47 (1992), 231--240; Problem 13, p. 234. Library home: Erdős 1992.
Er97d: Erdős, P., Some recent problems and results in graph theory. Discrete Math. 164 (1997), 81--85; item 7, p. 83; the site's source key, and Bukh and Sudakov's [9]. Library home: Erdős 1997.
LoPl22: Long, E. and Ploscaru, L., Distinct degrees and homogeneous sets. J. Combin. Theory Ser. B 159 (2023), 61--100, DOI 10.1016/j.jctb.2022.11.004; arXiv:2204.05932 (v2 30 November 2022); abstract only; paper not held. Context: the relation between $\hom(G)$ and $f(G)$ when $\hom(G)\ge n^{1/2}$ .
LoPl24: Long, E. and Ploscaru, L., Distinct degrees and homogeneous sets II. arXiv:2409.14134 (v1 21 September 2024); abstract only; paper not held. Context: the range $\hom(G)\le n^{1/2}$ .
CMSS: Conlon, D., Morris, R., Samotij, W. and Saxton, D., The number of distinct degrees in an induced subgraph of a random graph. Unpublished, as [JKLY20] cites it (its reference [4]); an earlier proof of the random-graph lower bound $f(G_{N,1/2})=\Omega(N^{2/3})$ , which [JKLY20]'s published Theorem 1 also gives.

Problem 637

Status

Proof claims

Discussion