6
$\begingroup$

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.

$\endgroup$

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Vor
    Oct 8, 2011 at 11:13
  • $\begingroup$ Check out the addition... $\endgroup$
    – Igor Rivin
    Oct 8, 2011 at 15:07
  • $\begingroup$ 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). $\endgroup$
    – Vor
    Oct 8, 2011 at 16:26
  • $\begingroup$ 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) $\endgroup$
    – Vor
    Oct 8, 2011 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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