## Abstract

In this paper we investigate the extremal relationship between two well-studied graph parameters: the order of the largest homogeneous set in a graph G and the maximal number of distinct degrees appearing in an induced subgraph of G, denoted respectively by hom(G) and f(G).

Our main theorem improves estimates due to several earlier researchers and shows that if G is an n-vertex graph with hom(G) ≥ n

The above relationship between hom(G) and f(G) breaks down in the regime where hom(G) < n

Our approach to lower bounding f(G) proceeds via a translation into an (almost) equivalent probabilistic problem, and it can be shown to be effective for arbitrary graphs. It may be of independent interest.

Our main theorem improves estimates due to several earlier researchers and shows that if G is an n-vertex graph with hom(G) ≥ n

^{1/2}then f(G) ≥ (n/hom(G))^{1-o(1)}. The bound here is sharp up to the o(1)-term, and asymptotically solves a conjecture of Narayanan and Tomon. In particular, this implies that max{hom(G), f(G)} ≥ n^{1/2-o(1)}for any n-vertex graph G, which is also sharp.The above relationship between hom(G) and f(G) breaks down in the regime where hom(G) < n

^{1/2}. Our second result provides a sharp bound for distinct degrees in biased random graphs, i.e. on f(G(n, p)). We believe that the behaviour here determines the extremal relationship between hom(G) and f(G) in this second regime.Our approach to lower bounding f(G) proceeds via a translation into an (almost) equivalent probabilistic problem, and it can be shown to be effective for arbitrary graphs. It may be of independent interest.

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

Pages (from-to) | 61-100 |

Number of pages | 40 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 159 |

Early online date | 13 Dec 2022 |

DOIs | |

Publication status | Published - Mar 2023 |

## Keywords

- Distinct degrees
- Homogeneous number
- Ramsey
- Probabilistic method