Número de van der Waerden
# Número de van der Waerden

El teorema de Van der Waerden establece que para cualesquiera enteros positivos r y k existe un entero positivo N tal que si los enteros ${1,2,...,N}$ son coloreados, cada uno con uno de r distintos colores, entonces hay al menos k números en progresión aritmética todos de un mismo color. El número más pequeño para N es el número de van der Waerden $W(r,k)$.

## Tablas de números de van der Waerden

Existen dos casos en los que el número de van der Waerden $W(r,k)$ es sencillo de calcular: primero, cuando el número de colores r es igual a 1, uno tiene $W(1,k)=k$ para cualquier entero k, ya que un solo color produce el coloreado trivial $RRRR\cdots RRR$ (para el único color denotado con R). Segundo, cuando la longitud k de la progresión aritmética forzada es 2, uno tiene $W(r,2)=r+1$ ya que es posible construir un coloreado que evite las progresiones aritméticas de longitud 2 usando cada color hasta un máximo de una vez, pero usar cualquier color dos veces creará una progresión aritmética de longitud 2. Por ejemplo, para $r=3$, el coloreado más largo que evita una progresión de longitud 2 es $RGB$. Sólo existen otros siete números de van der Waerden cuyos valores se conocen exactamente. El cuadro reproducido abajo reporta los valores exactos y límites para valores de $W(r,k)$; éstos vienen del trabajo de Rabung and Lotts, excepto donde se mencione lo contrario.

    k\r 2 colores 3 colores 4 colores 5 colores 6 colores 3 9 27  76  >170  >223  4 35 293  >1,048  >2,254  >9,778  5 178 >2,173  >17,705  >98,740  >98,748  6 1,132 >11,191  >91,331  >540,025  >816,981  7 >3,703  >48,811  >420,217  >1,381,687  >7,465,909  8 >11,495  >238,400  >2,388,317  >10,743,258  >57,445,718  9 >41,265  >932,745  >10,898,729  >79,706,009  >458,062,329 10 >103,474  >4,173,724  >76,049,218  >542,694,970 >2,615,305,384 11 >193,941  >18,603,731  >305,513,57 >2,967,283,511 >3,004,668,671

Los número de van der Waerden con $r\geq 2$ tienen un límite superior dado por

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

según la prueba de Gowers.

Para un Número primo $p$, el número de van der Waerden de dos colores tiene un límite inferior dado por

    $p\cdot 2^{p}\leq W(2,p+1),$

según la prueba de Berlekamp.

También es posible denotar $w(r;k_{1},k_{2},\cdots ,k_{r})$ para referirse al menor número $w$ tal que cualquier coloración de los enteros ${1,2,\cdots ,w}$ con $r$ colores contiene una progresión de longitud $k_{i}$ de color $i$ para alguna $i$. Dichos números se llaman números de van der Waerden fuera de la diagonal (en inglés: off-diagonal van der Waerden numbers. Por lo tanto $W(r,k)=w(r;k,k,\cdots ,k)$.

A continuación se presenta una lista de algunos números de van der Waerden conocidos:

Números de van der Waerden conocidos :

| $w(r;k_1,$ $k_2,$ …, $k_r)$ | Valor | Referencia |
| - | - | - |
| w(2; 3,3) | 9 | Chvátal |
| w(2; 3,4) | 18 | Chvátal |
| w(2; 3,5) | 22 | Chvátal |
| w(2; 3,6) | 32 | Chvátal |
| w(2; 3,7) | 46 | Chvátal |
| w(2; 3,8) | 58 | Beeler and O'Neil |
| w(2; 3,9) | 77 | Beeler and O'Neil |
| w(2; 3,10) | 97 | Beeler and O'Neil |
| w(2; 3,11) | 114 | Landman, Robertson, and Culver |
| w(2; 3,12) | 135 | Landman, Robertson, y Culver |
| w(2; 3,13) | 160 | Landman, Robertson, y Culver |
| w(2; 3,14) | 186 | Kouril |
| w(2; 3,15) | 218 | Kouril |
| w(2; 3,16) | 238 | Kouril |
| w(2; 3,17) | 279 | Ahmed |
| w(2; 3,18) | 312 | Ahmed |
| w(2; 3,19) | 349 | Ahmed, Kullmann, y Snevily |
| w(2; 4,4) | 35 | Chvátal |
| w(2; 4,5) | 55 | Chvátal |
| w(2; 4,6) | 73 | Beeler y O'Neil |
| w(2; 4,7) | 109 | Beeler |
| w(2; 4,8) | 146 | Kouril |
| w(2; 4,9) | 309 | Ahmed |
| w(2; 5,5) | 178 | Stevens y Shantaram |
| w(2; 5,6) | 206 | Kouril |
| w(2; 5,7) | 260 | Ahmed |
| w(2; 6,6) | 1132 | Kouril y Paul |
| w(3; 2, 3, 3) | 14 | Brown |
| w(3; 2, 3, 4) | 21 | Brown |
| w(3; 2, 3, 5) | 32 | Brown |
| w(3; 2, 3, 6) | 40 | Brown |
| w(3; 2, 3, 7) | 55 | Landman, Robertson, y Culver |
| w(3; 2, 3, 8) | 72 | Kouril |
| w(3; 2, 3, 9) | 90 | Ahmed |
| w(3; 2, 3, 10) | 108 | Ahmed |
| w(3; 2, 3, 11) | 129 | Ahmed |
| w(3; 2, 3, 12) | 150 | Ahmed |
| w(3; 2, 3, 13) | 171 | Ahmed |
| w(3; 2, 3, 14) | 202 | Kouril |
| w(3; 2, 4, 4) | 40 | Brown |
| w(3; 2, 4, 5) | 71 | Brown |
| w(3; 2, 4, 6) | 83 | Landman, Robertson, y Culver |
| w(3; 2, 4, 7) | 119 | Kouril |
| w(3; 2, 4, 8) | 157 | Kouril |
| w(3; 2, 5, 5) | 180 | Ahmed |
| w(3; 2, 5, 6) | 246 | Kouril |
| w(3; 3, 3, 3) | 27 | Chvátal |
| w(3; 3, 3, 4) | 51 | Beeler y O'Neil |
| w(3; 3, 3, 5) | 80 | Landman, Robertson, y Culver |
| w(3; 3, 3, 6) | 107 | Ahmed |
| w(3; 3, 4, 4) | 89 | Landman, Robertson, y Culver |
| w(3; 4, 4, 4) | 293 | Kouril |
| w(4; 2, 2, 3, 3) | 17 | Brown |
| w(4; 2, 2, 3, 4) | 25 | Brown |
| w(4; 2, 2, 3, 5) | 43 | Brown |
| w(4; 2, 2, 3, 6) | 48 | Landman, Robertson, y Culver |
| w(4; 2, 2, 3, 7) | 65 | Landman, Robertson, y Culver |
| w(4; 2, 2, 3, 8) | 83 | Ahmed |
| w(4; 2, 2, 3, 9) | 99 | Ahmed |
| w(4; 2, 2, 3, 10) | 119 | Ahmed |
| w(4; 2, 2, 3, 11) | 141 | Schweitzer |
| w(4; 2, 2, 4, 4) | 53 | Brown |
| w(4; 2, 2, 4, 5) | 75 | Ahmed |
| w(4; 2, 2, 4, 6) | 93 | Ahmed |
| w(4; 2, 2, 4, 7) | 143 | Kouril |
| w(4; 2, 3, 3, 3) | 40 | Brown |
| w(4; 2, 3, 3, 4) | 60 | Landman, Robertson, y Culver |
| w(4; 2, 3, 3, 5) | 86 | Ahmed |
| w(4; 3, 3, 3, 3) | 76 | Beeler y O'Neil |
| w(5; 2, 2, 2, 3, 3) | 20 | Landman, Robertson, y Culver |
| w(5; 2, 2, 2, 3, 4) | 29 | Ahmed |
| w(5; 2, 2, 2, 3, 5) | 44 | Ahmed |
| w(5; 2, 2, 2, 3, 6) | 56 | Ahmed |
| w(5; 2, 2, 2, 3, 7) | 72 | Ahmed |
| w(5; 2, 2, 2, 3, 8) | 88 | Ahmed |
| w(5; 2, 2, 2, 3, 9) | 107 | Kouril |
| w(5; 2, 2, 2, 4, 4) | 54 | Ahmed |
| w(5; 2, 2, 2, 4, 5) | 79 | Ahmed |
| w(5; 2, 2, 2, 4, 6) | 101 | Kouril |
| w(5; 2, 2, 3, 3, 3) | 41 | Landman, Robertson, y Culver |
| w(5; 2, 2, 3, 3, 4) | 63 | Ahmed |
| w(6; 2, 2, 2, 2, 3, 3) | 21 | Ahmed |
| w(6; 2, 2, 2, 2, 3, 4) | 33 | Ahmed |
| w(6; 2, 2, 2, 2, 3, 5) | 50 | Ahmed |
| w(6; 2, 2, 2, 2, 3, 6) | 60 | Ahmed |
| w(6; 2, 2, 2, 2, 4, 4) | 56 | Ahmed |
| w(6; 2, 2, 2, 3, 3, 3) | 42 | Ahmed |
| w(7; 2, 2, 2, 2, 2, 3, 3) | 24 | Ahmed |
| w(7; 2, 2, 2, 2, 2, 3, 4) | 36 | Ahmed |
| w(7; 2, 2, 2, 2, 2, 3, 5) | 55 | Ahmed |
| w(7; 2, 2, 2, 2, 2, 3, 6) | 65 | Ahmed |
| w(7; 2, 2, 2, 2, 2, 4, 4) | 66 | Ahmed |
| w(7; 2, 2, 2, 2, 3, 3, 3) | 45 | Ahmed |
| w(8; 2, 2, 2, 2, 2, 2, 3, 3) | 25 | Ahmed |
| w(8; 2, 2, 2, 2, 2, 2, 3, 4) | 40 | Ahmed |
| w(8; 2, 2, 2, 2, 2, 2, 3, 5) | 61 | Ahmed |
| w(8; 2, 2, 2, 2, 2, 2, 3, 6) | 71 | Ahmed |
| w(8; 2, 2, 2, 2, 2, 2, 4, 4) | 67 | Ahmed |
| w(8; 2, 2, 2, 2, 2, 3, 3, 3) | 49 | Ahmed |
| w(9; 2, 2, 2, 2, 2, 2, 2, 3, 3) | 28 | Ahmed |
| w(9; 2, 2, 2, 2, 2, 2, 2, 3, 4) | 42 | Ahmed |
| w(9; 2, 2, 2, 2, 2, 2, 2, 3, 5) | 65 | Ahmed |
| w(9; 2, 2, 2, 2, 2, 2, 3, 3, 3) | 52 | Ahmed |
| w(10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) | 31 | Ahmed |
| w(10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 4) | 45 | Ahmed |
| w(10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 5) | 70 | Ahmed |
| w(11; 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) | 33 | Ahmed |
| w(11; 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4) | 48 | Ahmed |
| w(12; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) | 35 | Ahmed |
| w(12; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4) | 52 | Ahmed |
| w(13; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) | 37 | Ahmed |
| w(13; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4) | 55 | Ahmed |
| w(14; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) | 39 | Ahmed |
| w(15; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) | 42 | Ahmed |
| w(16; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) | 44 | Ahmed |
| w(17; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) | 46 | Ahmed |
| w(18; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) | 48 | Ahmed |
| w(19; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) | 50 | Ahmed |
| w(20; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) | 51 | Ahmed |

Los números de van der Waerden son primitivo recursivos, según la prueba de Shelah; en la que probó que están (cuando más) en el quinto nivel ${\mathcal {E}}^{5}$ de la jerarquía de Grzegorczyk.

