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 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 .
Tablas de números de van der Waerden
Existen dos casos en los que el número de van der Waerden es sencillo de calcular: primero, cuando el número de colores r es igual a 1, uno tiene para cualquier entero k, ya que un solo color produce el coloreado trivial (para el único color denotado con R). Segundo, cuando la longitud k de la progresión aritmética forzada es 2, uno tiene 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 , el coloreado más largo que evita una progresión de longitud 2 es . 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 ; éstos vienen del trabajo de Rabung and Lotts, excepto donde se mencione lo contrario.
{| class="wikitable" ! k\r ! 2 colores ! 3 colores ! 4 colores ! 5 colores ! 6 colores |- | 3 | style="text-align:right;"| 9 | style="text-align:right;"| 27 | style="text-align:right;"| 76 | style="text-align:right;"| >170 | style="text-align:right;"| >223 |- | 4 | style="text-align:right;" | 35 | style="text-align:right;"| 293 | style="text-align:right;"| >1,048 | style="text-align:right;"| >2,254 | style="text-align:right;"| >9,778 |- | 5 | style="text-align:right;"| 178 | style="text-align:right;"| >2,173 | style="text-align:right;"| >17,705 | style="text-align:right;"| >98,740 | style="text-align:right;"| >98,748 |- | 6 | style="text-align:right;"| 1,132 | style="text-align:right;"| >11,191 | style="text-align:right;"| >91,331 | style="text-align:right;"| >540,025 | style="text-align:right;"| >816,981 |- | 7 | style="text-align:right;"| >3,703 | style="text-align:right;"| >48,811 | style="text-align:right;"| >420,217 | style="text-align:right;"| >1,381,687 | style="text-align:right;"| >7,465,909 |- | 8 | style="text-align:right;"| >11,495 | style="text-align:right;"| >238,400 | style="text-align:right;"| >2,388,317 | style="text-align:right;"| >10,743,258 | style="text-align:right;"| >57,445,718 |- | 9 | style="text-align:right;"| >41,265 | style="text-align:right;"| >932,745 | style="text-align:right;"| >10,898,729 | style="text-align:right;"| >79,706,009 | style="text-align:right;"| >458,062,329 |- | 10 | style="text-align:right;"|>103,474 | style="text-align:right;"|>4,173,724 | style="text-align:right;"| >76,049,218 | style="text-align:right;"| >542,694,970 | style="text-align:right;"| >2,615,305,384 |- | 11 | style="text-align:right;"|>193,941 | style="text-align:right;"|>18,603,731 | style="text-align:right;"| >305,513,57 | style="text-align:right;"| >2,967,283,511 | style="text-align:right;"| >3,004,668,671
Los número de van der Waerden con tienen un límite superior dado por
según la prueba de Gowers.
Para un Número primo , el número de van der Waerden de dos colores tiene un límite inferior dado por
según la prueba de Berlekamp.
También es posible denotar para referirse al menor número tal que cualquier coloración de los enteros con colores contiene una progresión de longitud de color para alguna . Dichos números se llaman números de van der Waerden fuera de la diagonal (. Por lo tanto .
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;k1, k2, …, kr) Valor Referenciaw(2; 3,3)9Chvá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 de la jerarquía de Grzegorczyk.
Véase también Teorema de Ramsey Coloración de grafos
Referencias
Lecturas adicionales
Enlaces externos
Categoría:Teoría de Ramsey