2019/10/03 by Matthew Jenssen, Jenssen, Matthew, Peter Keevash +5
Mathematics · #05C69 #05D10 #05D40 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C69 #msc:05D10 #msc:05D40
paper · pdf · doi:10.48550/arxiv.1910.01361
13 pages
arxiv created 2019/10/03 · arxiv updated 2019/10/04
An important theme of recent research in Ramsey theory has been establishing pseudorandomness properties of Ramsey graphs. An N-vertex graph is called C-Ramsey if it has no homogeneous set of size Clog N. A theorem of Bukh and Sudakov, solving a conjecture of Erdős, Faudree and Sós, shows that any C-Ramsey N-vertex graph contains an induced subgraph with ΩC(N1/2) distinct degrees. We improve this to ΩC(N2/3), which is tight up to the constant factor. We also show that any N-vertex graph with N > (k-1)(n-1) and n≥ n0(k) = Ω(k9) either contains a homogeneous set of order n or an induced subgraph with k distinct degrees. The lower bound on N here is sharp, as shown by an appropriate Turán graph, and confirms a conjecture of Narayanan and Tomon.