Ramsey numbers of sparse digraphs

Ramsey numbers of sparse digraphs

-
Yuval Wigderson, Stanford University

In 1934, Rédei proved that every tournament contains a Hamiltonian path. Equivalently, if P_n denotes a directed path on n vertices, then every tournament on n vertices contains a copy of P_n.  Which other n-vertex digraphs must appear in any tournament on O(n) vertices? Formally, the Ramsey number r(H) of a digraph H is defined as the minimum N such that every N-vertex tournament contains a copy of H. This is only well-defined for digraphs with no directed cycle, and the basic question is which conditions on the n-vertex acyclic digraph H ensure that r(H) = O(n).  If H has many edges, then a random construction shows that r(H) will be substantially larger than linear in n. In the analogous undirected setting, this turns out to be the only obstruction: a famous result of Lee, proving a conjecture of Burr and Erdős, says that any sparse undirected graph has Ramsey number that is linear in n. Surprisingly, this is emphatically not the case for digraphs: we construct, for any C > 1, a bounded-degree n-vertex digraph H with r(H) > n^C. In the other direction, we prove linear and nearly-linear upper bounds for several natural families of bounded-degree digraphs, including random digraphs, digraphs of bounded height, and digraphs of "low multiscale complexity".

Joint work with Jacob Fox and Xiaoyu He.