On the size-Ramsey number of grid graphs. (6th September 2021)

• Record Type: Journal Article
• Authors: Clemens, Dennis; Miralaei, Meysam; Reding, Damian; Schacht, Mathias; Taraz, Anusch
• Is Part Of: Combinatorics, probability and computing. Volume 30:Number 5(2021)
• Page Start: 670
• Page End: 685
• Publication Date: 2021-09-06
• Subjects: 05D10; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548320000322
• Languages: English
• ISSNs: 0963-5483

Abstract

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