2024/09/21 by Eoin Long, Long, Eoin, Laurentiu Ploscaru +1
Mathematics · #05C07 (Primary) #05C69 #05C80 (Secondary) #05D10 #05D40 #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2409.14134
openalex publication_date 2024/09/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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) ≤ n1/2 satisfies f(G) ≥ √[3]\frac n2\hom (G) ⋅ n-o(1). This confirms a conjecture of the authors from a previous work, in which we addressed the \hom (G) ≥ n1/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) ) ≥ n1-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.