An improved upper bound for the grid Ramsey problem

DOI10.1002/JGT.22540MaRDI QIDQ5066901zbMATH OpenOpenAlexFDO

Authors Luka Milićević

Publication date 31 March 2022

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

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

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)

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.

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

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)