New bounds on the Ramsey number r ( I_m , L_n )

Abstract: We investigate the Ramsey numbers

r (I_{m}, L_{n})

which is the minimal natural number

k

such that every oriented graph on

k

vertices contains either an independent set of size

m

or a transitive tournament on

n

vertices. Apart from the finitary combinatorial interest, these Ramsey numbers are of interest to set theorists since it is known that

r (o m e g a m, n) = o m e g a r (I_{m}, L_{n})

, where

o m e g a

is the lowest transfinite ordinal number, and

r (k a p p a m, n) = k a p p a r (I_{m}, L_{n})

for all initial ordinals

k a p p a

. Continuing the research by Bermond from 1974 who did show

r (I_{3}, L_{3}) = 9

, we prove

r (I_{4}, L_{3}) = 15

and

r (I_{5}, L_{3}) = 23

. The upper bounds for both the estimates above are obtained by improving the upper bound of

m^{2}

on

r (I_{m}, L_{3})

due to Larson and Mitchell (1997) to

m^{2} - m + 3

. Additionally, we provide asymptotic upper bounds on

r (I_{m}, L_{n})

for all

n g e q 3

. In particular, we show that

r (I_{m}, L_{3}) i n T h e t a (m^{2} / l o g m)

.

Recommendations

Cites Work

Cited In (2)

This page was built for publication: New bounds on the Ramsey number \(r ( I_m , L_n )\)