|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||Abstract:||
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 Dec 6, 2023
checked on Dec 7, 2023
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.