## Abstract

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 C logN. 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}(N^{1/2}) distinct degrees. We improve this to Ω_{C}(N^{2/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 ≥ n_{0}(k) = Ω(k^{9}) 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.

Original language | English |
---|---|

Pages (from-to) | 3835-3846 |

Number of pages | 12 |

Journal | Proceedings of the American Mathematical Society |

Volume | 148 |

Issue number | 9 |

Early online date | 22 May 2020 |

DOIs | |

Publication status | Published - Sept 2020 |

## Keywords

- Ramsey theory
- Probabilistic methods
- Induced subgraphs

## ASJC Scopus subject areas

- Applied Mathematics
- Mathematics(all)