Van der Waerden's theorem


Van der Waerden's theorem

Van der Waerden's theorem is a theorem of the branch of mathematics called Ramsey theory. The theorem is about the basic structure of the integers. It is named for Dutch mathematician B. L. van der Waerden. [B.L. van der Waerden, "Beweis einer Baudetschen Vermutung", Nieuw. Arch. Wisk. 15 (1927), 212–216.]

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 all of the same color. The least such "N" is the Van der Waerden number "V"("r", "k").

For example, when "r" = 2, you have two colors, say red and blue. "V"(2, 3) is bigger than 8, because you 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

and no three integers of the same color form an arithmetic progression. But you can't add a ninth integer to the end without creating such a progression.

It is an open problem to determine the values of "V"("r", "k") for most values of "r" and "k". The proof of the theorem provides only an upper bound. For the case of "r"=2 and "k" = 3, for example, the argument given below shows that it is sufficient to color the integers {1, ..., 325} with two colors to guarantee there will be a single-colored arithmetic progression of length 3. But in fact, the bound of 325 is very loose; the minimum required number of integers is only 9. Any coloring of the integers {1, ..., 9} will have three evenly spaced integers of one color.

For "r" = 3 and "k" = 3, the bound given by the theorem is 7(2·37 + 1)(2·37·(2·37 + 1) + 1), or approximately 4.22·1014616. But actually, you don't need that many integers to guarantee a single-colored progression of length 3; you only need 27. (And it is possible to color {1, ..., 26} with three colors so that there is no single-colored arithmetic progression of length 3; for example, RRYYRRYBYBBRBRRYRYYBRBBYBY.)

Anyone who can reduce the general upper bound to any 'reasonable' function can win a large cash prize. Ronald Graham has offered a prize of US$1000 for showing "V"(2,"k")<2"k"2. [Ron Graham, "Some of My Favorite Problems in Ramsey Theory", INTEGERS (The Electronic Journal of Combinatorial Number Theory), [http://www.integers-ejcnt.org/vol7-2.html 7(2)] , 2007, #A2.] The current record is due to Timothy Gowers, [Timothy Gowers, "A new proof of Szemerédi's theorem", Geom. Funct. Anal., 11(3):465-588, 2001, Preprint available at http://www.dpmms.cam.ac.uk/~wtg10/papers.html.] who establishes

: V(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 best-known lower bound for V(2, k) is that V(2, k) > 2^k/k^epsilon for all positive ε. [cite book |title=Discrete Mathematics And Its Applications |editor=M. Sethumadhavan |last=Brown | first=Tom C. | pages=80 | chapter=A partition of the non-negative integers, with applications to Ramsey theory |authorlink= |coauthors= |year=2006 |publisher=Alpha Science Int'l Ltd. |location= |isbn=8173197318 ]

Proof of Van der Waerden's theorem (in a special case)

The following proof is due to Ron Graham and B.L. Rothschild. [R.L. Graham and B.L. Rothschild, "A short proof of van der Waerden's theorem on arithmetic progressions", Proc. American Math. Soc. 42(2) 1974, 385-386.]

We will prove the special case mentioned above, that "V"(2, 3) ≤ 325. Let "c"("n") be a coloring of the integers {1, ..., 325}. We will find three elements of {1, ..., 325} in arithmetic progression that are the same color.

Divide {1, ..., 325} into the 65 blocks {1, ..., 5}, {6, ..., 10}, ... {321, ..., 325}, thus each block is of the form {"b" ·5 + 1, ..., "b" ·5 + 5} for some "b" in {0, ..., 64}. Since each integer is colored either red or blue, each block is colored in one of 32 different ways. By the pigeonhole principle, there are two blocks among the first 33 blocks that are colored identically. That is, there are two integers "b"1 and "b"2, both in {0,...,32}, such that

: "c"("b"1·5 + "k") = "c"("b"2·5 + "k")

for all "k" in {1, ..., 5}. Among the three integers "b"1·5 + 1, "b"1·5 + 2, "b"1·5 + 3, there must be at least two that are the same color. (The pigeonhole principle again.) Call these "b"1·5 + "a"1 and "b"1·5 + "a"2, where the "a""i" are in {1,2,3} and "a"1 < "a"2. Suppose (without loss of generality) that these two integers are both red. (If they are both blue, just exchange 'red' and 'blue' in what follows.)

Let "a"3 = 2·"a"2 − "a"1. If "b"1·5 + "a"3 is red, then we have found our arithmetic progression: "b"1·5 + "a""i" are all red.

Otherwise, "b"1·5 + "a"3 is blue. Since "a"3 ≤ 5, "b"1·5 + "a"3 is in the "b"1 block, and since the "b"2 block is colored identically, "b"2·5 + "a"3 is also blue.

Now let "b"3 = 2·"b"2 - "b"1. Then "b"3 ≤ 64. Consider the integer "b"3·5 + "a"3, which must be ≤ 325. What color is it?

If it is red, then "b"1·5 + "a"1, "b"2·5 + "a"2, and "b"3·5 + "a"3 form a red arithmetic progression. But if it is blue, then "b"1·5 + "a"3, "b"2·5 + "a"3, and "b"3·5 + "a"3 form a blue arithmetic progression. Either way, we are done.

A similar argument can be advanced to show that "V"(3, 3) ≤ 7(2·37+1)(2·37·(2·37+1)+1). One begins by dividing the integers into 2·37·(2·37 + 1) + 1 groups of 7(2·37 + 1) integers each; of the first 37·(2·37 + 1) + 1 groups, two must be colored identically.

Divide each of these two groups into 2·37+1 subgroups of 7 integers each; of the first 37 + 1 subgroups in each group, two of the subgroups must be colored identically. Within each of these identical subgroups, two of the first four integers must be the same color, say red; this implies either a red progression or an element of a different color, say blue, in the same subgroup.

Since we have two identically-colored subgroups, there is a third subgroup, still in the same group that contains an element which, if either red or blue, would complete a red or blue progression, by a construction analogous to the one for "V"(2, 3). Suppose that this element is yellow. Since there is a group that is colored identically, it must contain copies of the red, blue, and yellow elements we have identified; we can now find a pair of red elements, a pair of blue elements, and a pair of yellow elements that 'focus' on the same integer, so that whatever color it is, it must complete a progression.

It should be noted that the proof for "V"(2, 3) depends essentially on proving that "V"(32, 2) ≤ 33. We divide the integers {1,...,325} into 65 'blocks', each of which can be colored in 32 different ways, and then show that two blocks of the first 33 must be the same color, and there is a block coloured the opposite way. Similarly, the proof for "V"(3, 3) depends on proving that

: V(3^{7(2 cdot 3^7+1)},2) leq 3^{7(2 cdot 3^7+1)}+1

By a double induction on the number of colors and the length of the progression, the theorem is proved in general.

References

External links

* [http://www.math.uga.edu/~lyall/REU/ramsey.pdf Proof of Van der Waerden's theorem]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Van der Waerden number — Van der Waerden s theorem states that for any positive integers r and k there exists a positive integer 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 …   Wikipedia

  • Satz von Van der Waerden — Der Satz von Van der Waerden (nach Bartel Leendert van der Waerden) ist ein berühmter Satz aus der Kombinatorik, genauer aus der Ramseytheorie. Er besagt, dass für alle natürlichen Zahlen r und l eine natürliche Zahl N(r,l) existiert, so dass… …   Deutsch Wikipedia

  • Bartel Leendert van der Waerden — Infobox Scientist box width = name = Bartel Leendert van der Waerden image size = caption = birth date = birth date|1903|2|2 birth place = Amsterdam, Netherlands death date = death date and age|1996|1|12|1903|2|2 death place = Zürich, Switzerland …   Wikipedia

  • Hales–Jewett theorem — In mathematics, the Hales–Jewett theorem is a fundamental combinatorial result of Ramsey theory, concerning the degree to which high dimensional objects must necessarily exhibit some combinatorial structure; it is impossible for such objects to… …   Wikipedia

  • Szemerédi's theorem — In number theory Szemerédi s theorem refers to the proof of the Erdős–Turán conjecture. In 1936 Erdős and Turan conjecturedcitation|authorlink1=Paul Erdős|first1=Paul|last1=Erdős|authorlink2=Paul Turán|first2=Paul|last2=Turán|title=On some… …   Wikipedia

  • Pythagorean theorem — See also: Pythagorean trigonometric identity The Pythagorean theorem: The sum of the areas of the two squares on the legs (a and b) equals the area of the square on the hypotenuse (c) …   Wikipedia

  • Isomorphism theorem — In mathematics, specifically abstract algebra, the isomorphism theorems are three theorems that describe the relationship between quotients, homomorphisms, and subobjects. Versions of the theorems exist for groups, rings, vector spaces, modules,… …   Wikipedia

  • Cayley–Hamilton theorem — In linear algebra, the Cayley–Hamilton theorem (named after the mathematicians Arthur Cayley and William Hamilton) states that every square matrix over the real or complex field satisfies its own characteristic equation.More precisely; if A is… …   Wikipedia

  • Théorie de Ramsey — La théorie de Ramsey, qui porte le nom de Frank Ramsey, pose typiquement une question de la forme : combien d éléments d une certaine structure doivent être considérés pour qu une propriété particulière se vérifie ? Un adage souvent… …   Wikipédia en Français

  • List of mathematics articles (V) — NOTOC Vac Vacuous truth Vague topology Valence of average numbers Valentin Vornicu Validity (statistics) Valuation (algebra) Valuation (logic) Valuation (mathematics) Valuation (measure theory) Valuation of options Valuation ring Valuative… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.