Authors: Milićević, Luka 
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: An improved upper bound for the grid Ramsey problem
Journal: Journal of Graph Theory
Volume: 94
Issue: 4
First page: 509
Last page: 517
Issue Date: 1-Jan-2020
Rank: M22
ISSN: 0364-9024
DOI: 10.1002/jgt.22540
For a positive integer r, let G (r) be the smallest N such that, whenever the edges of the Cartesian product KN × KN are r-colored, then there is a rectangle in which both pairs of opposite edges receive the same color. In this paper, we improve the upper bounds on G (r) by proving (Formula presented.), for r large enough. Unlike the previous improvements, which were based on bounds for the size of set systems with restricted intersection sizes, our proof is a form of quasirandomness argument.
Keywords: graph Cartesian product | grid Ramsey problem | quasirandomness | Ramsey theory
Publisher: Wiley
Project: Representations of logical structures and formal languages and their application in computing 

Show full item record


checked on Jun 23, 2024

Page view(s)

checked on May 10, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.