On generalized Ramsey numbers of Erdős and Rogers

Abstract: Extending the concept of Ramsey numbers, Erd{H o}s and Rogers introduced the following function. For given integers

2 l e s < t

let

f_{s,t}(n)=min {max {|W| : Wsubseteq V(G) {and} G[W] {contains no} K_s} },

where the minimum is taken over all

K_{t}

-free graphs

G

of order

n

. In this paper, we show that for every

s g e 3

there exist constants

c_{1} = c_{1} (s)

and

c_{2} = c_{2} (s)

such that

f_{s, s + 1} (n) l e c_{1} (l o g n)^{c_{2}} s q r t n

. This result is best possible up to a polylogarithmic factor. We also show for all

t - 2 g e q s g e q 4

, there exists a constant

c_{3}

such that

f_{s, t} (n) l e c_{3} s q r t n

. In doing so, we partially answer a question of ErdH{o}s by showing that

l i m_{n o i n f t y} f r a c f_{s + 1, s + 2} (n) f_{s, s + 2} (n) = i n f t y

for any

s g e 4

.

Recommendations

Cites Work

Cited In (15)

This page was built for publication: On generalized Ramsey numbers of Erdős and Rogers