2016/09/06 by Bhargav Narayanan, Narayanan, Bhargav, István Tomon +1
Mathematics · #05C07 (Secondary) #05D10 (Primary) #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C07 #msc:05D10
paper · pdf · doi:10.48550/arxiv.1609.01677
17 pages, Combinatorics, Probability and Computing
arxiv created 2017/06/28 · arxiv updated 2017/06/29
Let \hom(G) denote the size of the largest clique or independent set of a graph G. In 2007, Bukh and Sudakov proved that every n-vertex graph G with \hom(G) = O(log n) contains an induced subgraph with Ω(n1/2) distinct degrees, and raised the question of deciding whether an analogous result holds for every n-vertex graph G with \hom(G) = O(nε), where ε> 0 is a fixed constant. Here, we answer their question in the affirmative and show that every graph G on n vertices contains an induced subgraph with Ω((n/\hom(G))1/2) distinct degrees. We also prove a stronger result for graphs with large cliques or independent sets and show, for any fixed k ∈ ℕ, that if an n-vertex graph G contains no induced subgraph with k distinct degrees, then \hom(G) ≥ n/(k-1)-o(n); this bound is essentially best-possible.