Distinct degrees and homogeneous sets (Q2680569)

For a graph \(G\), by \(\mathrm{hom}(G)\) we mean the size of the largest homogenous set, i.e., a subset of vertices that induces either a clique or an independent set in \(G\). The well-known results from Ramsey's theory inform us that any graph \(G\) on \(n\) vertices admits a homogenous set of size \(\Omega(\log n)\) and that this is best possible up to constants. Since it has been a heuristic that graphs that achieve the Ramsey bound show strong random-like properties, one of the lines of investigation to affirm this heuristic is the following: If \(G\) has \(n\) vertices and has \(\mathrm{hom}(G)= O(\log n)\) then it has an induced subgraph with `many' distinct degrees. If \(f(G)\) denotes the maximum number of distinct degrees possible in some induced subgraph, then a result of \textit{B. Bukh} and \textit{B. Sudakov} [ibid. B 97, No. 4, 612--619 (2007; Zbl 1120.05057)] shows that \(f(G)=\Omega(n^{1/2})\), and conjectured that \(\mathrm{hom}(G)=n^{o(1)}\) already implies \(f(G)\ge n^{1/2-o(1)}\) and this was later proved by \textit{B. Narayanan} and \textit{I. Tomon} [Comb. Probab. Comput. 27, No. 1, 110--123 (2018; Zbl 1378.05127)]. They in turn conjectured that if \(G\) is an \(n\) vertex graph with \(\mathrm{hom}(G)\ge n^{1/2}\) then \(f(G)=\Omega\left(\frac{n}{\mathrm{hom}(G)}\right)\). The current paper under review establishes this up to a logarithmic loss; the authors prove that for \(m\ge n^{1/2}\), if \(\mathrm{hom}(G)\le m\) then \(f(G)=\Omega\left(\frac{n/m}{\log^{7/2}(n/m)}\right)\). The authors also establish sharp bounds for \(f(G(n,p))\) for all \(p\le 1/2\). Interestingly, there is a difference in the asymptotic description for this parameter, depending on whether \(p\ge n^{-1/2}\) or not. One of the main interesting ideas in the proofs is in their recasting of the problem to include a more general model of random subgraphs of a given graph \(G\). A probability vector \(\mathfrak{p}\in[0.1,0.9]^{V(G)}\) picks the random subgraph where vertex \(v\) is picked independently with probability \(\mathfrak{p}(v)\) -- we shall denote this (following the paper) \(G(\mathfrak{p})\). The new idea(s) in this paper, arise from the following two (not very difficult, but interesting) observations: \begin{itemize} \item If for some probability vector \(\mathfrak{p}\) and distinct vertices \(u,v\in V(G)\) we have \(|\mathbb{E}(d_{G(\mathfrak{p})}(u)-\mathbb{E}(d_{G(\mathfrak{p})}(v)|\ge D\) then \(\mathbb{P}(d_{G(\mathfrak{p})}(u)=d_{G(\mathfrak{p})}(v))\le O(\sqrt{\log D}/D)\). In words, if for some distribution \(\mathfrak{p}\) and vertices \(u\ne v\), the expected degrees of \(u\) and \(v\) in \(G(\mathfrak{p})\) are somewhat far apart, then whp their degrees are distinct in \(G(\mathfrak{p})\). \item Set \(f_{\mathfrak{p}}(G)\) to be the maximum size of a subset \(U\) such that for any two vertices in \(U\), their expected degrees are pairwise distinct in \(G(\mathfrak{p})\). Then if \(f_{\mathfrak{p}}(G)\ge 2\) then \(f(G)=\Omega\left(\frac{f_{\mathfrak{p}}(G)}{\log^{3/2}(f_{\mathfrak{p}}(G)}\right)\). \end{itemize} This then sets the problem into a different domain: Look for distribution \(\mathfrak{p}\in[0.1,0.9]^{V(G)}\) for which \(f_{\mathfrak{p}}(G)\) is maximized. The authors build such a suitable \(\mathfrak{p}\) in a series of steps that need several other ideas which are handled with care and subtlety. The authors manage this and still keep the paper very readable and comprehensible.