An improved upper bound for the grid Ramsey problem

DOI10.1002/JGT.22540zbMATH Open1485.05111arXiv1809.09458OpenAlexW3004479720MaRDI QIDQ5066901FDOQ5066901

Authors: Luka Milićević 

Publication date: 31 March 2022

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: For a positive integer $r$, let $G(r)$ be the smallest $N$ such that, whenever the edges of the Cartesian product $K_{N}imes{K}_N$ are $r$-coloured, then there is a rectangle in which both pairs of opposite edges receive the same colour. In this paper, we improve the upper bounds on $G(r)$ by proving $$, 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 a quasirandomness argument.

Full work available at URL: https://arxiv.org/abs/1809.09458

Recommendations

• Grid Ramsey problem
• On the grid Ramsey problem and related questions
• On the size-Ramsey number of grid graphs
• Improved upper and lower bounds on a geometric Ramsey problem
• Upper bounds for Ramsey numbers

zbMATH Keywords

Ramsey theoryquasirandomnessgraph Cartesian productgrid Ramsey problem

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Graph operations (line graphs, products, etc.) (05C76) Ramsey theory (05D10)

Cited In (6)

• An improved upper bound for Leo Moser's worm problem
• Improved upper and lower bounds on a geometric Ramsey problem
• On the size-Ramsey number of grids
• Monochromatic rectangles in grid colorings
• Grid Ramsey problem
• On the grid Ramsey problem and related questions

This page was built for publication: An improved upper bound for the grid Ramsey problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5066901)