Simple proof that W(3,3)=27?

Question

I was wondering that if there exists a simple proof that the van der Warden's number W(3,3) (the smallest positive integer $n$ such that any 3-coloring of the set $\{1, 2, ..., n\}$ has a monochromatic 3-AP) equals 27. Also, it would be great if someone can present me a counterexample for $n=26$.

score 2 · Accepted Answer · answered Jan 14 '13 at 17:16

2

The complete list of length-26 examples is:

    AABBAABCBCCACAABABBCACCBCB
    AABBCAACACBBCCBBCACAACBBAA
    AABCBAACACBBCCBBCACAABCBAA
    AACBCAABABCCBBCCBABAACBCAA
    AACCAACBCBBABAACACCBABBCBC
    AACCBAABABCCBBCCBABAABCCAA
    ABAABABCCBBCCBABAABCCAACAC
    ABABBAACBBCBCAACCAACBCBBCA

not counting relabeling of the colors. (So there are 48 examples in all.)

I don't know of any proof that 27 is exact, other than a suitably-pruned exhaustive search.

I have source code that I wrote about 25 years ago that does the search, plus some discussion, on my blog. The code took a couple of days to run when I first wrote it, but to run it now is very quick.

answered Jan 14 '13 at 17:16

MJD

65,394
39
298
580

That is very interesting! Thank you very much. – a12345 Jan 14 '13 at 17:27
I don't think you should be so quick to accept the answer, particularly since it's incomplete. What if there is a simple proof that 27 is exact, and I don't know it, and the person who does know it skips over this question because you accepted an answer already? If I were you, I'd un-accept the answer, and wait a couple of days to see what else turns up. – MJD Jan 14 '13 at 17:33
This can't be the correct list of examples, since there shouldn't be any strings that begin with AAC. (I should have exchanged the labels B and C.) Also if you reverse the first string AABBAABCBCCACAABABBCACCBCB, and then relabel B→A, C→B, A→C, you get ABABBCBAACACCBCBBABACCAACC, which should be on the list but is not. I will try to fix this soon. – MJD Aug 10 '21 at 13:02

Simple proof that W(3,3)=27?

1 Answers1