***********************************
* Princeton Discrete Math Seminar *
***********************************
Speaker: Yuval Wigderson (Stanford U.)
Thursday 4th March, 3:00 via Zoom.
Title: Ramsey numbers of sparse digraphs
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.
----------------------------------
Next week: David Conlon
Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)