On the size-Ramsey number of grid graphs

Publikationstyp

Journal Article

Date Issued

2021-09

Sprache

English

Author(s)

Clemens, Dennis

Miralaei, Meysam

Schacht, Mathias

Institut

Mathematik E-10

TORE-URI

http://hdl.handle.net/11420/11074

Journal

Combinatorics, probability & computing

Volume

30

Issue

5

Start Page

670

End Page

685

Citation

Combinatorics Probability and Computing 30 (5): 670-685 (2021-09)

Publisher DOI

10.1017/S0963548320000322

Scopus ID

2-s2.0-85103840183

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 × n vertices is bounded from above by n 3+o(1).