On the size-Ramsey number of grid graphs

Dennis Clemens, Meysam Miralaei, Damian Reding, Mathias Schacht, Anusch Taraz

Published 2019-06-17Version 1

The size-Ramsey number of a graph $F$ is the smallest number of edges in a graph $G$ with the Ramsey property for $F$, that is, with the property that any 2-colouring of the edges of $G$ contains a monochromatic copy of $F$. We prove that the size-Ramsey number of the grid graph on $n\times n$ vertices is bounded from above by $n^{3+o(1)}$.