HUJI Combinatorics Seminar 


When: Monday May 31st, 2021, at 5:30PM


Zoom link: https://huji.zoom.us/j/86289409452?pwd=bWRXRVJvNHNFdlVhY0NTaW40dGZMZz09



Speaker: Yuval Wigderson (Stanford)
Title:  Ramsey numbers of sparse digraphs

Abstract: 

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”.