Premium
An improved upper bound for the grid Ramsey problem
Author(s) -
Milićević Luka
Publication year - 2020
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22540
Subject(s) - cartesian product , mathematics , combinatorics , rectangle , intersection (aeronautics) , upper and lower bounds , integer (computer science) , colored , product (mathematics) , set (abstract data type) , grid , discrete mathematics , geometry , computer science , mathematical analysis , materials science , engineering , composite material , programming language , aerospace engineering
For a positive integer r , let G ( r ) be the smallest N such that, whenever the edges of the Cartesian product K N × K N 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 G ( r ) ≤ ( 1 − 1 128 r − 2( 1 − o ( 1 ) ) ) r ( r + 1 2 ), 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.