Distinct degrees and homogeneous sets II

Abstract

Given an $n$-vertex graph $G$, let $\mathrm{hom}(G)$ denote the size of a largest homogeneous set in $G$ and let $f(G)$ denote the maximal number of distinct degrees appearing in an induced subgraph of $G$. The relationship between these parameters has been well studied by several researchers over the last 40 years, beginning with Erdős, Faudree and Sós in the Ramsey regime when $\mathrm{hom}(G)=O(\log n)$. Our main result here proves that any $n$-vertex graph $G$ with $\mathrm{hom}(G)\le n^{1/2}$ satisfies \begin{align*} f(G) \geq \sqrt[3]{\frac {n^2}{\hom (G)} } \cdot n^{-o(1)}. \end{align*} This confirms a conjecture of the authors from a previous work, in which we addressed the $\mathrm{hom}(G)\ge n^{1/2}$ regime. Together, these provide the complete extremal relationship between these parameters (asymptotically), showing that any $n$-vertex graph $G$ satisfies \begin{align*} \max \Big ( f(G) \cdot \hom (G), \sqrt {f(G) ^3 \cdot \hom (G) } \Big ) \geq n^{1-o(1)}. \end{align*} This relationship is tight (up to the $n^{-o(1)}$ term) for all possible values of $\mathrm{hom}(G)$, from $\hat{I}\text{c◯}(\log n)$ to $n$, as demonstrated by appropriately generated Erdős $-$ Renyi random graphs.

26 pages