The size-Ramsey number of 3-uniform tight paths

Abstract

Given a hypergraph $H$, the size-Ramsey number ${\hat{r}}_2(H)$ is the smallest integer $m$ such that there exists a graph $G$ with $m$ edges with the property that in any colouring of the edges of $G$ with two colours there is a monochromatic copy of $H$. We prove that the size-Ramsey number of the $3$-uniform tight path on $n$ vertices $P_n^{(3)}$ is linear in $n$, i.e., ${\hat{r}}_2(P_n^{(3)})=O(n)$. This answers a question by Dudek, Fleur, Mubayi, and Rödl for $3$-uniform hypergraphs [On the size-Ramsey number of hypergraphs, J. Graph Theory 86 (2016), 417-434], who proved ${\hat{r}}_2(P_n^{(3)})=O(n^{3/2}{\log }^{3/2}n)$.

12 pages,1 figure