Welcome to MathOverflow

Question

5

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.

edited Oct 8 2011 at 16:43

asked Oct 8 2011 at 10:25

Vor
207●1●7

Igor Rivin · Accepted Answer · 2011-10-08 15:07:38Z UTC

6

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.

edited Oct 8 2011 at 15:07

answered Oct 8 2011 at 10:41

Igor Rivin
31.3k●3●37●71

	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 2011 at 11:13
	Check out the addition... – Igor Rivin Oct 8 2011 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 2011 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 2011 at 16:46

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.