The size Ramsey number of a directed path - Mathematics > CombinatoricsReport as inadecuate




The size Ramsey number of a directed path - Mathematics > Combinatorics - Download this document for free, or read online. Document in PDF available to download.

Abstract: Given a graph $H$, the size Ramsey number $r eH,q$ is the minimal number$m$ for which there is a graph $G$ with $m$ edges such that every $q$-coloringof $G$ contains a monochromatic copy of $H$. We study the size Ramsey number ofthe directed path of length $n$ in oriented graphs, where no antiparallel edgesare allowed. We give nearly tight bounds for every fixed number of colors,showing that for every $q\geq 1 $ there are constants $c 1 = c 1q,c 2$ suchthat $$\frac{c 1q n^{2q}\log n^{1-q}}{\log\log n^{q+2-q}} \leqr e\overrightarrow{P n},q+1 \leq c 2 n^{2q}\log {n}^2.$$Our results show that the path size Ramsey number in oriented graphs isasymptotically larger than the path size Ramsey number in general directedgraphs. Moreover, the size Ramsey number of a directed path is polynomiallydependent in the number of colors, as opposed to the undirected case.Our approach also gives tight bounds on $r e\overrightarrow{P n},q$ forgeneral directed graphs with $q \geq 3$, extending previous results.



Author: Ido Ben-Eliezer, Michael Krivelevich, Benny Sudakov

Source: https://arxiv.org/







Related documents