Logo
All Random Solved Random Open
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 directed path of size $m$. Determine $k(n,m)$.
A problem of Erdős and Rado [ErRa67], who showed \[k(n,m) \leq \frac{2^{m-1}(n-1)^m+n-2}{2n-3}.\] Larson and Mitchell [LaMi97] prove that $k(n,m)\leq n^{m-1}$ for $m\geq 3$.

See also the entry in the graphs problem collection.