Back to Search Start Over

On the size-Ramsey number of grid graphs

Authors :
Clemens, Dennis
Miralaei, Meysam
Reding, Damian
Schacht, Mathias
Taraz, Anusch
Source :
Combinator. Probab. Comp. 30 (2021) 670-685
Publication Year :
2019

Abstract

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)}$.<br />Comment: 21 pages, second version addresses changes arising from the referee report and comments from Thomas Lesgourgues

Subjects

Subjects :
Mathematics - Combinatorics
05D10

Details

Database :
arXiv
Journal :
Combinator. Probab. Comp. 30 (2021) 670-685
Publication Type :
Report
Accession number :
edsarx.1906.06915
Document Type :
Working Paper
Full Text :
https://doi.org/10.1017/S0963548320000322