OPEN
Let $k=k(n,m)$ be minimal such that any directed graph on $k$ vertices must contain either an independent set of size $n$ or a transitive tournament of size $m$. Determine $k(n,m)$.
A problem of Erdős and Rado
[ErRa67], who showed $k(n,m) \ll_m n^{m-1}$, or more precisely,
\[k(n,m) \leq \frac{2^{m-1}(n-1)^m+n-2}{2n-3}.\]
Larson and Mitchell
[LaMi97] improved the dependence on $m$, establishing in particular that $k(n,3)\leq n^{2}$. Zach Hunter has observed that
\[R(n,m) \leq k(n,m)\leq R(n,m,m),\]
which in particular proves the upper bound $k(n,m)\leq 3^{n+2m}$.
See also the entry in the graphs problem collection - on this site the problem replaces transitive tournament with directed path, but Zach Hunter and Raphael Steiner have a simple argument that proves, for this alternative definition, that $k(n,m)=(n-1)(m-1)$.
