Feb. 3, 3:30pm, Wean 8220

Michael Krivelevich, Tel-Aviv University

The size Ramsey number of a directed path

Michael Krivelevich, Tel-Aviv University

The size Ramsey number of a directed path

Abstract:

Given a (di)graph H and an integer q at least 2, the size Ramsey number r_e(H,q)
is the minimal number m for which there is a (di)graph G with m edges such
that every q-coloring of G contains a monochromatic copy of H. We study
the size Ramsey number of the directed path of length n in oriented graphs, where no antiparallel edges are allowed. We give nearly tight bounds for
every fixed number of colors, showing that for every q at least 2,
the corresponding number r_e(H,q) has asymptotic order of magnitude
n^{2q-2+o(1)}.

A joint work with Ido Ben-Eliezer (Tel Aviv U.) and Benny Sudakov (UCLA).