ACO The ACO Seminar (2010-2011)

Feb. 3, 3:30pm, Wean 8220
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).


Back to the ACO home page