6
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 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
    Commented Feb 20, 2012 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
    Commented Feb 20, 2012 at 21:59
  • $\begingroup$ A variant of this problem is discussed at cstheory.stackexchange.com/questions/791/… $\endgroup$
    – Gerry Myerson
    Commented Feb 20, 2012 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
    Commented Feb 20, 2012 at 23:33

2 Answers 2

Reset to default
9
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\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
    Commented Feb 21, 2012 at 11:17
4
$\begingroup$

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

0000001001111
0101100101010
0011001111001
1110100010011
1011111001000
0110010011110
1101001010100
1000011110010
1011000100111
0001110010101
0101011000011
1100010101001
0110111100100
Improve this answer
$\endgroup$
3
  • $\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
    Commented Feb 20, 2012 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
    Commented Feb 20, 2012 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
    Commented Feb 21, 2012 at 11:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .