The size Ramsey number of a directed path
The size Ramsey number of a directed path
-
Ido Ben-Eliezer, Tel Aviv University
Fine Hall 224
Given a graph $H$, 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 $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. For the case of two colors we show that there are constants $c_1,c_2$ such that $\frac{c_1 n^{2} \log n}{(\log\log n)^3} \leq r_e(P_n,2) \leq c_2 n^{2}(\log n)^2$.Joint work with Michael Krivelevich and Benny Sudakov.