Eoin Long

Distinct degrees and homogeneous sets

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). In this talk I hope to discuss a recent theorem which provides the complete extremal relationship between these parameters (asymptotically), showing that any n-vertex graph G satisfies

max ( f(G) ⋅ hom (G), f(G)^{3/2} ⋅ 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 order log n to n, as demonstrated by appropriately generated Erdős-Rényi random graphs. Joint work with Laurenţiu Ploscaru.