MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I decided to cross-post the question here from 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.

share|cite|improve this question
up vote 7 down vote accepted

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.

share|cite|improve this answer
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 (…) 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

Your Answer


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.