Sarah Peluse
Tic-tac-toe and Additive Combinatorics
June 10, 2024
Source: Rutgers Current Trends in Mathematics
For any positive integers $ r $ and $ k $, there exists a positive integer $ n $ such that if the $ n $-dimensional grid $ [k]^n $ is $ r $-colored, then there is a monochromatic combinatorial line.
For any positive integers $ r $ and $ k $, there exists a positive integer $ N $ such that if the $ d $-dimensional grid $ [N]^d $ is $ r $-colored, then there is a monochromatic $ k $-dimensional arithmetic progression.
For any positive integer $ r $, there exists a positive integer $ n $ such that if $ [n] $ is $ r $-colored, there is a monochromatic set $ A $ with $ \max(A) - \min(A) \leq n - |A| $.