Monochromatic boxes in colored grids

2008/10/16 by Joshua Cooper, Cooper, Joshua, Stephen Fenner +3
Computer Science · Mathematics · #05D10 #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO #msc:05D10

paper · pdf · doi:10.48550/arxiv.0810.3019

17 pages, 1 figure

arxiv created 2008/10/16 · openalex publication_date 2008/10/16 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A d-dimensional grid is a set of the form R = [a₁] × ... × [a_d]. A d-dimensional box is a set of the form \b₁,c₁\ × ... × \b_d,c_d\. When a grid is c-colored, must it admit a monochromatic box? If so, we say that R is c-guaranteed. This question is a relaxation of one attack on bounding the van der Waerden numbers, and also arises as a natural hypergraph Ramsey problem (viz. the Ramsey numbers of hyperoctahedra). We give conditions on the a_i for R to be c-guaranteed that are asymptotically tight, and analyze the set of minimally c-guaranteed grids.

Related

• Ramsey Theory on the Integer Grid: The "L" Problem
• Canonical theorems in geometric Ramsey theory
• On SAT Solvers and Ramsey-type Numbers
• Rectangle Free Coloring of Grids
• All rectangles exhibit canonical Ramsey property