2010/05/20 by Stephen Fenner, William Gasarch, Fenner, Stephen +5
Mathematics · #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1005.3750
openalex publication_date 2010/05/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A two-dimensional grid is a set \Gnm = [n]×[m]. A grid \Gnm is c-colorable if there is a function χn,m: \Gnm → [c] such that there are no rectangles with all four corners the same color. We address the following question: for which values of n and m is \Gnm c-colorable? This problem can be viewed as a bipartite Ramsey problem and is related to a the Gallai-Witt theorem (also called the multidimensioanl Van Der Waerden's Theorem). We determine (1) exactly which grids are 2-colorable, (2) exactly which grids are 3-colorable, and (3) exactly which grids are 4-colorable. We use combinatorics, finite fields, and tournament graphs.