Forcing large directed paths or independent sets
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
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^{m1}(n1)^m+n2]/(2n3)\).
Larson and Mitchell [2] give a recurrence relation and obtain a bound of \( n^2\) for \( m=3\) and, more generally, of \( n^{m1}\) 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), 624633.

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