Talk:Van der Waerden's theorem

Dummy header for very old comments

In the statement of the theorem, we use {1,...,N}, but in the proof we use {0,...,N-1}. Should we use the same convention throughout? AxelBoldt 03:59 Jan 13, 2003 (UTC)

I've incremented the numbers in the proof by 1 to make it consistent. Terry 17:58, 6 Sep 2004 (UTC)

You cannot just increment all the numbers in a proof with no understanding of what is going on; the "consistent" proof was completely wrong. For example, you had

That is, there are two integers b₁ and b₂, both in {1,...,33}, such that c(b₁·5 + k) = c(b₂·5 + k) for all k in {1,...,5}.

which makes no sense, because if b₁ is 33 then later on b₃ will be larger than 325.

I have reverted the page. Please feel free to add back the remarks you put in about upper bounds, or to revert the page again and then correct the damage you did to the proof. -- Dominus 13:40, 7 Sep 2004 (UTC)

Sorry about that. I went through the proof again; the error you pointed out was the only error I made in the proof, as far as I can tell. I'm pretty sure it's correct now. Terry 05:59, 8 Sep 2004 (UTC)

Yes, you're right. I'm sorry I said you had no understanding of what was going on; it looked to me like you had just done a global replace of each number n with n-1. Thanks for correcting the proof and adding back your remarks about the upper bounds. -- Dominus 13:39, 8 Sep 2004 (UTC)

Proof

A very simple way to prove the Van der Wareden's theorem is to derive it as a corollary of Gallai's Theorem which in turn is a corollary of the Hales–Jewett theorem. The proof runs like this:

Apply Gallai's Theorem for V = {0,...k}. Now {b, b+c,...b+kc} is monochromatic. Q.E.D.

Note->Here we were looking for an AP of length k. c and b are the positive integers existing by Gallai's so that cV + b is monochromatic.

This should be included in the article. Any comments?--Shahab 10:16, 17 May 2007 (UTC)

While that does seem to work (although I'm not entirely familiar with Gallai's Theorem), I would say that it doesn't make sense to prove things "backwards" - although these generalized versions of each can be proven subsequently and independently, I think it makes more sense to prove them from the ground-up, as opposed to using the most general theorem at any given time to plainly and uninsightfully assert the more specific cases. Cheeser1 15:20, 17 May 2007 (UTC)

I am only talking about adding the fact that Van der Waerden's theorem is a corollary of Gallai's theorem (or of the Hales-Jewett Theorem) because it is a point worth realizing that all these theorems are a part of general geometric picture. You are right Cheeser1 when you say that it makes sense to give an insightful picture but there is no reason why the Hales Jewett bit can't be included in the article. Adding some info won't hurt the insight. BTW although the Hales Jewett Theorem is a generalization, it and the Van der Waerden's theorem have very similar colour focussing proofs, so HJ is really not that far advanced then VDW. Cheers--Shahab 13:01, 18 May 2007 (UTC)

I'm not sure when it was added, but I just noticed there is mention of both Szemeredi's theorem and Hales-Jewett as stronger theorems. I also noticed that this article's a bit of a mess, I think. Maybe I'll tidy it up. --Cheeser1 22:21, 17 June 2007 (UTC)

importan nitpicking

Is there anyone who can look at the expression

$V(r,k)\leq 2^{2^{r^{2^{2^{k+9}}}}}$,

without instantly see why the comma really needs to be INSIDE the "displayed" TeX? On the browser I'm using, it is positioned ridiculously. Michael Hardy 01:43, 21 June 2007 (UTC)

request explanation of bound

What is the point in the sentence "The best-known lower bound for V(2,k) is that V(2,k) > 2k / kε for all positive ε.[4]"? It seems to mean that V(2,k) is at least equal to 2k. —Preceding unsigned comment added by 193.50.42.4 (talk) 09:31, 22 May 2008 (UTC)

The statement is that $V(2,k)>2^{k}/k^{\epsilon }$ for all positive ε. This means that although $V(2,k)$ is not known to exceed $2^{k}$ in general, it is known to come very, very close: it exceeds $2^{k}/k^{0.000001}$ and other quantities that are just a hair smaller than $2^{k}$. -- Dominus (talk) 17:10, 22 May 2008 (UTC)

In the reference, the statement is exactly " given ε>0 $V(2,k)>2^{k}/k^{\epsilon }$ for all sufficiently large k" which I personally find more illuminating. I was disappointed to find that the reference does not provide a proof of this statement though. If someone knows a source which provides a proof, I think that would be a better thing to reference.76.193.189.206 (talk) 17:33, 8 May 2011 (UTC)

After a bit of googling, it appears that this bound is due to Z. Szabo in "An application of Lov´asz Local Lemma— a new lower bound on the van der Waerden numbers". Random Structures and Algorithms, 1, 1990. Personally I think that this is a better citation. 76.193.189.206 (talk) 17:37, 8 May 2011 (UTC)

proof overly complicated

The proof that W(2, 3) ≤ 325 seems unnecessary complicated to me.

Consider the following proof that W(2, 3) ≤ 13:

In 5 consecutive two-colored integers two have the same color and have an odd number of integers between them (call them a and b a<b). Consider the integer in the middle of these two. If it has the same color we are done. Now consider the two integers to the left of a and the right of b each of which forms an arithmetic progression of length three with a and b. If one of these shares the color of a and b we are done. If this is not the case the three considered integers to the right, left and in the middle of a and b suffice. For this proof 4 additional integers to the right and left of the 5 integer are needes which sums up to 13. —Preceding unsigned comment added by 160.45.6.96 (talk) 12:58, 21 April 2010 (UTC)

typesetting in the proof

The proof is a bit awkward to read. If MinN is to be a function, it should be coded as \operatorname{MinN} or \mathop{\rm MinN} or at least {\rm MinN} ^{[I removed the < math > tags on purpose in a subsequent edit]}. I don't understand why a central star $*$ appears in various places. (I did not read the text in detail but don't think any convolution is involved, and it probably just means multiplication which is traditionally denoted by \times or \cdot.) Also the line breaking and the u=1,...,L(?) in the line after the equation, rather than directly at the end of (but inside) the equation, is confusing. All in all, it gives the impression that a person not very familiar with mathematical writing was at work here, which make the whole section lose a lot its credibility. — MFH:Talk 20:53, 31 March 2013 (UTC)

Opening sentences describing the statement of vdW

The 2nd sentence reads at the moment as follows: Van der Waerden's theorem states that for any given positive integers r and k, there is some number N such that if the integers {1, 2, ..., N} are colored, each with one of r different colors, then there are at least k integers in arithmetic progression whose elements are of the same color.

The opening of the article would a little more clear and make the connection to Ramsey Theory more clear if it read as follows: Van der Waerden's theorem states that for any given positive integers r and k, there is some number N such that if the integers {1, 2, ..., N} are colored in an arbitrary manner using r different colors, then there exist at least k integers of {1, 2, ..., N} in an arithmetic progression whose elements are of the same color. Odahviing (talk) 08:07, 31 August 2019 (UTC)

Example and Open problem sections

In order to link the first example given of the statement of vdW properly with the fact that there are an infinite number of van der Waerden numbers yet to be given reasonable bounds for, it would make more sense if the heading read 'First example' instead of just 'Example'. Further, the writing in the sections 'Example' and 'Open Problem', altough they contain a lot of useful information that is certainly valuable, is a little rough and could use some polishing.

I propose that the Example and Open problem sections should read:

First example

The first non-trivial example to consider from van der Waerden's theorem is when r = 2, say red and blue. The van der Waerden number W(2, 3) is bigger than 8, since one can color the integers from {1, ..., 8} like this:

1	2	3	4	5	6	7	8
B	R	R	B	B	R	R	B

No three integers of the same color form an arithmetic progression in the segment {1, ..., 8}. However, it is impossible to add either a blue 9 or a red 9 without forming a monochromatic arithmetic progression of length three: If you add a red 9, then the red 3, 6, and 9 are in arithmetic progression. Alternatively, if you add a blue 9, then the blue 1, 5, and 9 are in arithmetic progression.

Using an exhaustive search of all possible two color assignments of the first nine integers, which would run through 2⁹ = 512 examples, one can show that it is unavoidable to create monochromatic arithmetic progression of length three in the first nine integers. By the above example of colors assigned to {1, ..., 8}, we then conclude that nine is the least integer that guarantees the existence of length three progressions in two colors, hence, we have proved that W(2,3) = 9.

Open Problem

The following table summarizes the known values or lower estimates of the first few van der Waerden numbers.

k/r	2 colors	3 colors	4 colors
3	9	27	76
4	35	293	> 1048
5	178	> 2173	> 17705
6	1132	> 11191	> 91331

Indeed, the explicit value of the van der Waerden number W(r,k) is not known for almost all ordered pairs (r,k). The standard combinatorial proof of van der Waerden's theorem only employs the establishment of upper bounds to van der Waerden numbers, and in most cases, these upper bounds are exceedingly weak. For the case r = 2 and k = 3 considered above, a combinatorial argument given below shows that it is sufficient to color the integers {1, ..., 325} with two colors to guarantee there will be a monochromatic arithmetic progression of length three.

For r = 3 and k = 3, the bound given by the standard combinatorial approach is is 7(2·3⁷ + 1)(2·3^{7·(2·37 + 1)} + 1), or approximately 4.22·10¹⁴⁶¹⁶. Employing exhuastive search on 3²⁷ = 7.62·10¹² candidates, in principle, one could show that any coloring the first twenty seven integers with the colors red, blue and yellow will inevitably lead to at least one monochromatic arithmetic progression of length three. Additionally, it is possible to color {1, ..., 26} with three colors so that there is no monochromatic arithmetic progression of length three arises; for example:

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26
R	R	Y	Y	R	R	Y	B	Y	B	B	R	B	R	R	Y	R	Y	Y	B	R	B	B	Y	B	Y

This proves that W(3,3) =27.

The best upper bound currently known is due to Timothy Gowers, who establishes

$W(r,k)\leq 2^{2^{r^{2^{2^{k+9}}}}},$

by first establishing a similar result for Szemerédi's theorem, which is a stronger version of Van der Waerden's theorem. The previously best-known bound was due to Saharon Shelah and proceeded via first proving a result for the Hales–Jewett theorem, which is another strengthening of Van der Waerden's theorem.

The American mathematician Ronald Graham has offered a prize of US$1000 for a proof of the specific upper bound

$W(2,k)\leq 2^{k^{2}}.$

The best lower bound currently known for $W(2,k)$ is that for all positive $\varepsilon$ we have $W(2,k)>2^{k}/k^{\varepsilon }$, for all sufficiently large $k$.Odahviing (talk) 10:02, 31 August 2019 (UTC)