The size Ramsey number of a directed path (Q414648): Difference between revisions

For a graph (resp. oriented graph) \(G\) let \(r_e(G,q)\) be the smallest number of edges in a graph (resp. oriented graph) \(H\) such that every \(q\)-edge-coloring of \(H\) contains a monochromatic copy of \(G\). \textit{J. Beck} [``On size Ramsey number of paths, trees, and circuits. I,'' J. Graph Theory 7, 115--129 (1983; Zbl 0508.05047)] proved that for the \(n\)-vertex path \(r_e(P_n,q)\leq c_q n\). In this paper it is shown that \[ \frac{c_1 n^{2q}(\log n)^{1/q}}{(\log \log n)^{(q+2)/q}} \leq r_e(\vec{P}_n,q+1)\leq c_2 n^{2q}(\log n)^2. \] Interestingly, in the category of directed graphs, i.e., graphs with antiparallel edges, the answer is different. Generalizing the works of \textit{H. Raynaud} [``Sur le circuit hamiltonien bi-colore dans les graphes orientes,'' Period. Math. Hung. 3, 289--297 (1973; Zbl 0267.05114)] and \textit{D. Reimer} [``The Ramsey size number of dipaths,'' Discrete Math. 257, No.\,1, 173--175 (2002; Zbl 1012.05116)] for \(q=1\), it is proved that \(r_e(\vec{P}_n,q+1)=\Theta(n^{2q})\) for digraphs.