Forcing large directed paths or independent sets

A problem of Erdös and Rado [1]

What is the least number \( k=k(n,m)\) so that for every directed graph on \(k\) vertices, either there is an independent set of size \( n\) or the graph includes a directed path of size m (not necessarily induced)?

Erdös and Rado [1] give an upper bound for \( k(n,m)\) of \( [2^{m-1}(n-1)^m+n-2]/(2n-3)\).

Larson and Mitchell [2] give a recurrence relation and obtain a bound of \( n^2\) for \( m=3\) and, more generally, of \( n^{m-1}\) for \( m>3\).


Bibliography
1 P. Erdös and R. Rado, Partition relations and transitivity domains of binary relations, J. London Math. Soc. 42 (1967), 624-633.

2 J. A. Larson and W. J. Mitchell, On a problem of Erdös and Rado, Annals of Combinatorics, 1 (1997), no. 3, 245252