Distinct degrees in induced subgraphs

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 l o g N

. A theorem of Bukh and Sudakov, solving a conjecture of ErdH{o}s, Faudree and S'os, shows that any

C

-Ramsey

N

-vertex graph contains an induced subgraph with

O m e g a_{C} (N^{1 / 2})

distinct degrees. We improve this to

O m e g a_{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 g e q n_{0} (k) = O m e g a (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'an graph, and confirms a conjecture of Narayanan and Tomon.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: Distinct degrees in induced subgraphs