5.2 Van der Waerden numbers and their properties

Van der Waerden numbers are crucial in Ramsey theory, guaranteeing monochromatic arithmetic progressions in colored sets. They're denoted as w(k,r), where k is the progression length and r is the number of colors used.

Calculating these numbers is tough, with exact values known only for small k and r. They grow rapidly, bounded by complex formulas. Properties like monotonicity and subadditivity help understand their behavior, but many mysteries remain unsolved.

Van der Waerden Numbers: Definition and Basic Properties

Definition of Van der Waerden numbers

Top images from around the web for Definition of Van der Waerden numbers

• 

  ArithmeticProgression | Wolfram Function Repository View original

  Is this image relevant?

• 

  Frontiers | Exact Values for Some Size Ramsey Numbers of Paths and Cycles View original

  Is this image relevant?

• 

  Ramsey class - Wikipedia, the free encyclopedia View original

  Is this image relevant?

• 

  ArithmeticProgression | Wolfram Function Repository View original

  Is this image relevant?

• 

  Frontiers | Exact Values for Some Size Ramsey Numbers of Paths and Cycles View original

  Is this image relevant?

1 of 3

Top images from around the web for Definition of Van der Waerden numbers

• 

  ArithmeticProgression | Wolfram Function Repository View original

  Is this image relevant?

• 

  Frontiers | Exact Values for Some Size Ramsey Numbers of Paths and Cycles View original

  Is this image relevant?

• 

  Ramsey class - Wikipedia, the free encyclopedia View original

  Is this image relevant?

• 

  ArithmeticProgression | Wolfram Function Repository View original

  Is this image relevant?

• 

  Frontiers | Exact Values for Some Size Ramsey Numbers of Paths and Cycles View original

  Is this image relevant?

1 of 3

• Van der Waerden numbers denoted as $[w(k, r)](https://www.fiveableKeyTerm:w(k,_r))$ represent smallest positive integer $n$ guaranteeing monochromatic arithmetic progression of length $k$ for any $r$-coloring of $\{1, 2, ..., n\}$

• Parameters $k$ (length of arithmetic progression) and $r$ (number of colors) determine specific Van der Waerden number

• Significance in Ramsey theory guarantees existence of certain structures in colored sets and relates to van der Waerden's theorem on arithmetic progressions

Calculation of Van der Waerden numbers

• Small Van der Waerden numbers include $[w(3, 2)](https://www.fiveableKeyTerm:w(3,_2)) = 9$, $[w(4, 2)](https://www.fiveableKeyTerm:w(4,_2)) = 35$, and $[w(5, 2)](https://www.fiveableKeyTerm:w(5,_2)) = 178$

• Growth rate increases rapidly with $k$ and $r$, bounded above by $w(k, r) \leq 2^{2^{2^{2^{(k-1)}}}}\cdot r$ and below by $w(k, r) \geq r^{k-1}$

• Computational challenges arise as exact values known only for small $k$ and $r$, becoming increasingly difficult to calculate for larger parameters (NP-hard problem)

Properties of Van der Waerden numbers

• Monotonicity states if $k_1 \leq k_2$ and $r_1 \leq r_2$, then $w(k_1, r_1) \leq w(k_2, r_2)$, as larger parameters require more elements to guarantee desired structure

• Subadditivity property $w(k, r_1 + r_2) \leq w(k, r_1) + w(k, r_2) - 1$ proved by combining separate colorings and applying pigeonhole principle

• Symmetry $w(k, r) = w(r, k)$ holds for $k = 2$, relating to Ramsey numbers through inequality $w(k, r) \leq R(k, k, ..., k)$ ($r$ times)

Bounds for Van der Waerden numbers

• Upper bounds include Graham-Rothschild theorem $w(k, r) \leq 2^{2^{2^{2^{(k-1)}}}}\cdot r$ and Gowers' bound $w(k, 2) \leq 2^{2^{2^{2^{k+9}}}}$

• Lower bounds derived from Berlekamp's construction $w(p + 1, 2) \geq p \cdot 2^p$ for prime $p$ and exponential lower bound $w(k, r) \geq r^{k-1}$

• Large discrepancy between upper and lower bounds highlights gaps in knowledge, with exact values unknown for most $k$ and $r$

• Recent developments improve bounds for specific cases and establish connections to other areas of mathematics (additive combinatorics) and computer science (complexity theory)