Número de van der Waerden

De testwiki
Ir a la navegación Ir a la búsqueda

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⋯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.[1]

k\r 2 colores 3 colores 4 colores 5 colores 6 colores
3 9[2] 27[2]   76[3]   >170   >223  
4 35[2] 293[4]   >1,048   >2,254   >9,778  
5 178[5] >2,173   >17,705   >98,740   >98,748  
6 1,132[6] >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[7]
10 >103,474   >4,173,724   >76,049,218   >542,694,970[7] >2,615,305,384[7]
11 >193,941   >18,603,731   >305,513,57[7] >2,967,283,511[7] >3,004,668,671[7]

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

W(r,k)≤22r22k+9

según la prueba de Gowers.[8]

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

p⋅2p≤W(2,p+1),

según la prueba de Berlekamp.[9]

También es posible denotar w(r;k1,k2,⋯,kr) para referirse al menor número w tal que cualquier coloración de los enteros 1,2,⋯,w con r colores contiene una progresión de longitud ki de color i para alguna i. Dichos números se llaman números de van der Waerden fuera de la diagonal (Plantilla:Lang-en. Por lo tanto W(r,k)=w(r;k,k,⋯,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;k1, k2, …, kr) Valor Referencia

w(2; 3,3)

9

Chvátal[2]

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

Los números de van der Waerden son primitivo recursivos, según la prueba de Shelah;[20] en la que probó que están (cuando más) en el quinto nivel ℰ5 de la jerarquía de Grzegorczyk.

Véase también

Referencias

Plantilla:Listaref

Lecturas adicionales

Enlaces externos

Plantilla:Control de autoridades

  1. ↑ Plantilla:Cita publicación
  2. ↑ 2,00 2,01 2,02 2,03 2,04 2,05 2,06 2,07 2,08 2,09 2,10 Plantilla:Cite encyclopedia
  3. ↑ 3,0 3,1 3,2 3,3 3,4 3,5 3,6 Plantilla:Cite journal
  4. ↑ 4,0 4,1 4,2 4,3 4,4 4,5 4,6 4,7 Plantilla:Cite journal
  5. ↑ 5,0 5,1 Plantilla:Cite journal
  6. ↑ 6,0 6,1 Plantilla:Cite journal
  7. ↑ 7,0 7,1 7,2 7,3 7,4 7,5 Plantilla:Cite web
  8. ↑ Plantilla:Cite journal
  9. ↑ Plantilla:Cite journal
  10. ↑ 10,00 10,01 10,02 10,03 10,04 10,05 10,06 10,07 10,08 10,09 10,10 10,11 Plantilla:Cite journal
  11. ↑ 11,0 11,1 11,2 11,3 11,4 11,5 11,6 Plantilla:Cite thesis
  12. ↑ 12,0 12,1 Plantilla:Cite journal
  13. ↑ Plantilla:Cite journal
  14. ↑ Plantilla:Cite journal
  15. ↑ 15,0 15,1 15,2 15,3 Plantilla:Cite journal
  16. ↑ 16,00 16,01 16,02 16,03 16,04 16,05 16,06 16,07 16,08 16,09 16,10 16,11 16,12 16,13 16,14 16,15 16,16 16,17 16,18 16,19 16,20 16,21 16,22 16,23 16,24 16,25 16,26 Plantilla:Cite journal
  17. ↑ 17,00 17,01 17,02 17,03 17,04 17,05 17,06 17,07 17,08 17,09 17,10 Plantilla:Cite journal
  18. ↑ 18,00 18,01 18,02 18,03 18,04 18,05 18,06 18,07 18,08 18,09 18,10 18,11 18,12 18,13 18,14 18,15 18,16 18,17 18,18 18,19 18,20 18,21 18,22 18,23 18,24 18,25 18,26 18,27 18,28 18,29 Plantilla:Cite journal
  19. ↑ Plantilla:Cite thesis
  20. ↑ Plantilla:Cite journal
Obtenido de «https://es.wiki.beta.math.wmflabs.org/w/index.php?title=Número_de_van_der_Waerden&oldid=10829»