Distinct degrees and homogeneous sets II

Given an n-vertex graph G, let 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 hom (G) = O(log n).

Our main result here proves that any n-vertex graph G with hom (G) <= n^{1/2} satisfies

f(G) >= ( n^2 / hom (G) ) ^{1/3} . n^{-o(1)}.

This confirms a conjecture of the authors from a previous work, in which we addressed the hom (G) >= n^{1/2} regime. Together, these provide the complete extremal relationship between these parameters (asymptotically), showing that any n-vertex graph G satisfies

max ( f(G) . hom (G), ( f(G) ^3 . hom (G) )^{1/2} ) >= n^{1-o(1)}.

This relationship is tight (up to the n^{-o(1)} term) for all possible values of hom (G), from Ω( log n ) to n, as demonstrated by appropriately generated Erdős - Renyi random graphs.