Contents Online

# Journal of Combinatorics

## Volume 1 (2010)

### Number 1

### Extremal binary matrices without constant 2-squares

Pages: 77 – 100

DOI: http://dx.doi.org/10.4310/JOC.2010.v1.n1.a6

#### Authors

#### Abstract

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