3x3 submatrix with only $0$ or $1$ entries

I decided to cross-post the question here from math.stackexchange.com because I got no answer from there.

It is a quick question on bipartite Ramsey numbers (I'm not an expert on the subject, so perhaps the question is trivial).

What is the least positive integer $r$ such that, any $r \times r$ 0-1 matrix contains at least one $3 \times 3$ submatrix filled with only 0 or only 1 entries ?

I found some articles with upper/lower bounds, but not a clear chart with the particular values I need.

-

1 Answer

According to this: MR1622032 (99c:05139) Hattingh, Johannes H.(SA-RAND); Henning, Michael A.(SA-NTL2) Bipartite Ramsey theory. (English summary) Util. Math. 53 (1998), 217–230. the answer is $17$, not $15.$

Addition A proof is contained in Irving's paper "A bipartite Ramsey problem and the Zarankiewicz numbers" (available on line). In the later paper with an almost identical title:

Bipartite Ramsey Numbers and Zarankiewicz Numbers (by Goddard et al) they seem to indicate that the Irving paper is slightly buggy, but that the result holds anyhow.

-
In Henning's article the b(3,3)=17 result is from L.W. Beineke and A.J. Schwenk, On a bipartite form of the Ramsey problem. Proc.5th British Combin. Conf. 1975, Congressus Numer. XV (1975), 17-22. I would like to see his proof, but I didn't find that article online. – Vor Oct 8 '11 at 11:13
Check out the addition... – Igor Rivin Oct 8 '11 at 15:07
Thank you! In the abstract of Irvin's paper available online (journals.cambridge.org/action/…) he says that the result b(3,3)=17 is from [1] and I suppose that [1] refers to Beineke's paper. Have you read the whole Irvin's paper and found the proof of the equality? (if yes I'll buy it). – Vor Oct 8 '11 at 16:26
Ok, I found Irving's paper. I probably made an error in the symmetry breaking rules (and removed the update). Thank you, again. (you can remove the "not 15" part) – Vor Oct 8 '11 at 16:46