Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
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? –  Will Sawin Feb 20 '12 at 18:58
    
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. –  Gerry Myerson Feb 20 '12 at 21:59
    
A variant of this problem is discussed at cstheory.stackexchange.com/questions/791/… –  Gerry Myerson Feb 20 '12 at 22:11
1  
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. –  Boris Bukh Feb 20 '12 at 23:33
add comment

2 Answers 2

up vote 9 down vote accepted

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

share|improve this answer
    
@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 –  WangYao Feb 21 '12 at 11:17
add comment

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
share|improve this answer
    
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 –  Gerhard Paseman Feb 20 '12 at 23:20
1  
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. –  Douglas Zare Feb 20 '12 at 23:27
    
@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 –  WangYao Feb 21 '12 at 11:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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