stringtranslate.com

Número de Van der Waerden

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

Tablas de números de Van der Waerden

Hay dos casos en los que el número de van der Waerden W ( r , k ) es fácil de calcular: primero, cuando el número de colores r es igual a 1, se tiene W (1, k ) = k para cualquier entero k , ya que un color produce solo coloraciones triviales RRRRR...RRR (para el color único denotado R). Segundo, cuando la longitud k de la progresión aritmética forzada es 2, se tiene W ( r , 2) = r + 1, ya que se puede construir una coloración que evite progresiones aritméticas de longitud 2 usando cada color como máximo una vez, pero usar cualquier color dos veces crea una progresión aritmética de longitud 2. (Por ejemplo, para r = 3, la coloración más larga que evita una progresión aritmética de longitud 2 es RGB). Solo hay otros siete números de van der Waerden que se conocen exactamente. La siguiente tabla proporciona valores exactos y límites para los valores de W ( r , k ); Los valores se toman de Rabung y Lotts, salvo que se indique lo contrario. [1]

Algunas coloraciones de límite inferior calculadas utilizando el enfoque SAT por Marijn JH Heule [6] se pueden encontrar en la página del proyecto github.

Los números de Van der Waerden con r ≥ 2 están acotados arriba por

como lo demostró Gowers . [9]

Para un número primo p , el número de van der Waerden de 2 colores está acotado inferiormente por

como lo demostró Berlekamp . [10]

En ocasiones también se escribe w(r; k1 , k2 , ... , kr ) para indicar el número más pequeño w tal que cualquier coloración de los enteros {1, 2, ..., w } con r colores contiene una progresión de longitud k i de color i , para algún i . Tales números se denominan números de van der Waerden fuera de la diagonal . Por lo tanto, W ( r , k ) = w (r; k , k , ..., k ). A continuación se muestra una lista de algunos números de van der Waerden conocidos:

Los números de Van der Waerden son recursivos primitivos , como lo demostró Shelah ; [22] de hecho, demostró que están (como máximo) en el quinto nivel de la jerarquía de Grzegorczyk .

Véase también

Referencias

  1. ^ Rabung, John; Lotts, Mark (2012). "Mejora del uso de cremalleras cíclicas para hallar límites inferiores para números de van der Waerden". Electron. J. Combin. 19 (2). doi : 10.37236/2363 . MR  2928650.
  2. ^ abcdefghijk Chvátal, Vašek (1970). "Algunos números de van der Waerden desconocidos". En Guy, Richard; Hanani, Haim; Sauer, Norbert; et al. (eds.). Estructuras combinatorias y sus aplicaciones . Nueva York: Gordon and Breach. págs. 31–33. MR  0266891.
  3. ^ abcdefg Beeler, Michael D.; O'Neil, Patrick E. (1979). "Algunos nuevos números de van der Waerden". Matemáticas discretas . 28 (2): 135–146. doi : 10.1016/0012-365x(79)90090-6 . MR  0546646.
  4. ^ abcdefgh Kouril, Michal (2012). "Cálculo del número de van der Waerden W(3,4)=293". Enteros . 12 : A46. MR  3083419.
  5. ^ ab Stevens, Richard S.; Shantaram, R. (1978). "Particiones de van der Waerden generadas por computadora". Matemáticas de la computación . 32 (142): 635–636. doi : 10.1090/s0025-5718-1978-0491468-x . MR  0491468.
  6. ^ ab Heule, MarijnJ (2017). "Cómo evitar los triples en la progresión aritmética" (PDF) . Journal of Combinatorics . 8 : 391–422.
  7. ^ ab Kouril, Michal; Paul, Jerome L. (2008). "El número de Van der Waerden W(2,6) es 1132". Matemáticas experimentales . 17 (1): 53–61. doi :10.1080/10586458.2008.10129025. MR  2410115. S2CID  1696473.
  8. ^ abcdefghijklmnopqr Monroe, Daniel (2019). "Nuevos límites inferiores para números de van der Waerden utilizando computación distribuida". arXiv : 1603.03301 [math.CO].
  9. ^ Gowers, Timothy (2001). "Una nueva prueba del teorema de Szemerédi" (PDF) . Geom. Funct. Anal. 11 (3): 465–588. doi :10.1007/s00039-001-0332-9. MR  1844079. S2CID  124324198.
  10. ^ Berlekamp, ​​E. (1968). "Una construcción para particiones que evitan progresiones aritméticas largas". Canadian Mathematical Bulletin . 11 (3): 409–414. doi : 10.4153/CMB-1968-047-7 . MR  0232743.
  11. ^ abcdefghijkl Landman, Bruce; Robertson, Aarón; Culver, arcilla (2005). "Algunos nuevos números exactos de van der Waerden" (PDF) . Enteros . 5 (2): A10. SEÑOR  2192088.
  12. ^ abcdefg Kouril, Michal (2006). Un marco de trabajo de seguimiento hacia atrás para clústeres Beowulf con una extensión a la computación de múltiples clústeres y la implementación del problema de referencia Sat (tesis doctoral). Universidad de Cincinnati.
  13. ^ ab Ahmed, Tanbir (2010). "Dos nuevos números de van der Waerden w(2;3,17) y w(2;3,18)". Enteros . 10 (4): 369–377. doi :10.1515/integ.2010.032. MR  2684128. S2CID  124272560.
  14. ^ ab Ahmed, Tanbir; Kullmann, Oliver; Snevily, Hunter (2014). "Sobre los números de van der Waerden w(2;3,t)". Matemáticas Aplicadas Discretas . 174 (2014): 27–51. arXiv : 1102.5433 . doi : 10.1016/j.dam.2014.05.007 . MR  3215454.
  15. ^ abcd Kouril, Michal (2015). "Aprovechamiento de clústeres FPGA para cálculos SAT". Computación paralela: en el camino hacia la exaescala : 525–532.
  16. ^ Beeler, Michael D. (1983). "Un nuevo número de van der Waerden". Matemáticas Aplicadas Discretas . 6 (2): 207. doi : 10.1016/0166-218x(83)90073-2 . ​​MR  0707027.
  17. ^ abcd Ahmed, Tanbir (2012). "Sobre el cálculo de números de van der Waerden exactos". Enteros . 12 (3): 417–425. doi :10.1515/integ.2011.112. MR  2955523. S2CID  11811448.
  18. ^ abcdefghijklmnopqrstu vwxyz aa Ahmed, Tanbir (2013). "Algunos números más de Van der Waerden". Revista de secuencias de enteros . 16 (4): 13.4.4. MR  3056628.
  19. ^ abcdefghijk Brown, TC (1974). "Algunos nuevos números de van der Waerden (informe preliminar)". Avisos de la American Mathematical Society . 21 : A-432.
  20. ^ abcdefghijklmnopqrstu vwxyz aa ab ac ad Ahmed, Tanbir (2009). "Algunos números de van der Waerden nuevos y algunos números de tipo van der Waerden". Enteros . 9 : A6. doi :10.1515/integ.2009.007. MR  2506138. S2CID  122129059.
  21. ^ Schweitzer, Pascal (2009). Problemas de complejidad desconocida, isomorfismo de grafos y números teóricos de Ramsey (tesis doctoral). Universidad de Sarre.
  22. ^ Shelah, Saharon (1988). "Límites recursivos primitivos para números de van der Waerden". Revista de la Sociedad Matemática Americana . 1 (3): 683–697. doi : 10.2307/1990952 . JSTOR  1990952. MR  0929498.

Lectura adicional

Enlaces externos