Problem 112

Erdős Problem #112: declared status 'open'. Formalized: no. 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)$. Current best: 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}$. Prize: no. Tags: graph theory, ramsey theory.