Suppose we color a $X \times X$ finite plane by red and blue arbitrarily. How large does X need to be to guarantee a monochromatic combinatorial square $k \times k$ 


1 0 1 0 1 1


1 1 1 1 1 1 


1 0 1 0 1 1


1 1 1 1 1 1


The above figure shows a combinatorial $2 \times 2$ filled square filled by zeros.



The Problem about 2-coloring finite plane
The exact answer, $15$, to this question is the content of my paper with Shalom Eliahou:
Here a copy of the corresponding entry of Math-Review:


Bacher, Roland; Eliahou, Shalom
Extremal binary matrices without constant 2-squares
J. Comb. 1 (2010), no. 1, [ISSN 1097-959X on cover], 77–100.
05D10 (11B75)


Summary: "In this paper we solve, by computational means, an open problem of Erickson: Let $[n]=\{1,…,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\times2$ subgrid $S=\{i,i+t\}\times\{j,j+t\}$ whose four points are colored the same? It has been shown recently that $13\le n\_0\le\min(W(2,8),5\cdot2240)$, where $W(2,8)$ is the still unknown eighth classical van der Waerden number. We obtain here the exact value $n\_0=15$. In the process, we display 2-colorings of $[13]\times{\bf Z}$ and $[14]\times[14]$ without constant 2-squares, and show that this is best possible.'' 


