Extremal binary matrices without constant 2-squares

In this paper we solve, by computational means, an open problem ofErickson: denoting $[n]= \{1,\ldots,n\}$, what is the smallest integer$n_0$ such that, for every $n \ge n_0$ and every 2-coloring of the grid$[n]\times [n]$, there is a constant 2-square, i.e. a $2\times 2$subgrid $S = \{i,i+t\}\times \{j,j+t\}$ whose four points are coloredthe same? It has been shown recently that $13 \le n_0 \le \min(W(2,8),5\cdot 2^{2^{40}})$, where $W(2,8)$ is the still unknown 8th classicalvan der Waerden number. We obtain here the exact value $n_0 = 15$. Inthe process we display 2-colorings of $[13] \times \Z$ and $[14] \times[14]$ without constant 2-squares, and show that this is best possible.

2010 Mathematics Subject Classification

05D10, 11B75

Full Text (PDF format)

Published 1 January 2010