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(\omega m,n)=\omega r(I_m,L_n)$, where $\omega$ is the lowest transfinite ordinal number, and $r(\kappa m,n)=\kappa r(I_m,L_n)$ for all initial ordinals $\kappa$. 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\ge 3$. In particular, we show that $r(I_m,L_3)\in \Theta (m^2/\log m)$.

20 pages, incorporated many reviewer's comments