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.

  • 1
    $\begingroup$ The definition of combinatorial square seems confusing. Do you mean to say that the row and column indices of the points of the square form arithmetic progressions, with arbitrary spacing? Must the spacing be the same in the two coordinates? $\endgroup$ – Will Sawin Feb 20 '12 at 18:58
  • $\begingroup$ The figure also shows a combinatorial $4\times4$ square filled by ones, the 4 rows and the 1st, 3rd, 5th, and 6th columns. On the other hand, it's not an $X\times X$ plane, unless one $X$ is 4 and the other $X$ is 6. I'm assuming a combinatorial square is an arbitrary selection of $k$ rows and $k$ columns. $\endgroup$ – Gerry Myerson Feb 20 '12 at 21:59
  • $\begingroup$ A variant of this problem is discussed at cstheory.stackexchange.com/questions/791/… $\endgroup$ – Gerry Myerson Feb 20 '12 at 22:11
  • 1
    $\begingroup$ It seems that you are asking about $K_{k,k}$ case of Zarankiewicz problem (if you want a square only in blue). Otherwise, you basically ask about the bipartite Ramsey number $R(K_{k,k},K_{k,k}). This should give you enough of keywords to search for. $\endgroup$ – Boris Bukh Feb 20 '12 at 23:33

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.''

  • $\begingroup$ @Bacher Excellent paper and very good result. Congrats. I am thinking a problem similar and think the general k×k cases where the square is given by S_k1 \times S_k2 where S_k1 is the subset of columns and s_k2 is the subset of subset of rows. But since finding 15 is so hard. This is an application of Gallai's Theorem, but the proofs tend to give absurdly large bounds I am finding the proof. Thank you. – WangYao 0 secs ago $\endgroup$ – WangYao Feb 21 '12 at 11:17

From http://csce.uark.edu/~dapon/thesis.pdf, 13 isn't large enough to guarantee a monochromatic square.

  • $\begingroup$ As the upper left 3x3 array shows, it is required that the squares have their edges aligned with the rows and columns of the array. Gerhard "Ask Me About Slanted Views" Paseman, 2012.02.20 $\endgroup$ – Gerhard Paseman Feb 20 '12 at 23:20
  • 1
    $\begingroup$ Yes, that is the convention in this type of problem. By the way, it's not immediately obvious that there is a sufficient size at all. This is an application of Gallai's Theorem, but the proofs tend to give absurdly large bounds. $\endgroup$ – Douglas Zare Feb 20 '12 at 23:27
  • $\begingroup$ @Douglas Zare. I am not very familiar with this field. Thanks for the "convention " explanation, my poor english is not able to manifest this clear $\endgroup$ – WangYao Feb 21 '12 at 11:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.