Combinatorics Seminar

When: Sunday, April 25, 10am Where: Schreiber 309 Speaker: Ido Ben-Eliezer, Tel Aviv U. Title: On the size Ramsey number of a directed path

Abstract:

Given a graph $H$ and a number $q$, the size Ramsey number $r_e(H,q)$ is the minimal number $m$ for which there is a graph $G$ with $m$ edges such that every $q$-coloring of $E(G)$ contains a monochromatic copy of H.

We study the size Ramsey number of a 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. For q=2 we show \frac{c_1 n^2 * log(n)}{\log^3(\log(n))} \leq r_e(P_n,2) \leq c_2 n^2 \log^2(n)

Our approach also generalizes previous results for general directed graphs with arbitrary number of colors.

Joint work with Michael Krivelevich and Benny Sudakov.