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 mínimo k enteros en progresión aritmética , todos del mismo color. El N más pequeño 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 sólo coloraciones triviales RRRRR...RRR (para el color único denominado R). En segundo lugar, 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 usando 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.) Sólo hay otros siete números de van der Waerden que se conocen con exactitud. La siguiente tabla proporciona valores y límites exactos 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 de 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 demuestra Gowers . [9]

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

como lo demuestra Berlekamp . [10]

A veces también se escribe w (r; k 1 , k 2 , ..., k r ) para significar el número más pequeño w tal que cualquier coloración de los números enteros {1, 2, ..., w } con r colores contiene un progresión de longitud k i de color i , para algunos i . Estos números se denominan números de van der Waerden fuera de la diagonal . Así 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 demuestra Shelah ; [22] de hecho demostró que están (como máximo) en el quinto nivel de la jerarquía de Grzegorczyk .

Ver también

Referencias

  1. ^ Rabung, Juan; Lotts, Mark (2012). "Mejorar el uso de cremalleras cíclicas para encontrar límites inferiores para los números de van der Waerden". Electrón. J. Combinar. 19 (2). doi : 10.37236/2363 . SEÑOR  2928650.
  2. ^ abcdefghijk Chvátal, Vašek (1970). "Algunos números desconocidos de van der Waerden". En Guy, Richard; Hanani, Haim; Sauer, Norberto; et al. (eds.). Estructuras combinatorias y sus aplicaciones . Nueva York: Gordon y Breach. págs. 31–33. SEÑOR  0266891.
  3. ^ abcdefg Beeler, Michael D.; O'Neil, Patrick E. (1979). "Algunos números nuevos de van der Waerden". Matemáticas discretas . 28 (2): 135-146. doi : 10.1016/0012-365x(79)90090-6 . SEÑOR  0546646.
  4. ^ abcdefgh Kouril, Michal (2012). "Calcular el número de van der Waerden W (3,4) = 293". Enteros . 12 : A46. SEÑOR  3083419.
  5. ^ ab Stevens, Richard S.; Shantaram, R. (1978). "Particiones van der Waerden generadas por computadora". Matemáticas de la Computación . 32 (142): 635–636. doi : 10.1090/s0025-5718-1978-0491468-x . SEÑOR  0491468.
  6. ^ ab Heule, MarijnJ (2017). «Evitar ternas en progresión aritmética» (PDF) . Revista de combinatoria . 8 : 391–422.
  7. ^ ab Kouril, Michal; Pablo, 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. SEÑOR  2410115. S2CID  1696473.
  8. ^ abcdefghijklmnopqr Monroe, Daniel (2019). "Nuevos límites inferiores para los números de van der Waerden mediante informática distribuida". arXiv : 1603.03301 [matemáticas.CO].
  9. ^ Gowers, Timoteo (2001). "Una nueva prueba del teorema de Szemerédi". Geom. Función. Anal. 11 (3): 465–588. doi :10.1007/s00039-001-0332-9. SEÑOR  1844079. S2CID  124324198.
  10. ^ Berlekamp, ​​E. (1968). "Una construcción para particiones que evita largas progresiones aritméticas". Boletín de Matemáticas Canadiense . 11 (3): 409–414. doi : 10.4153/CMB-1968-047-7 . SEÑOR  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 retroceso para clústeres de Beowulf con una extensión a la computación de múltiples clústeres y la implementación de problemas 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. SEÑOR  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ática Aplicada Discreta . 174 (2014): 27–51. arXiv : 1102.5433 . doi : 10.1016/j.dam.2014.05.007 . SEÑOR  3215454.
  15. ^ abcd Kouril, Michal (2015). "Aprovechando los 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ática Aplicada Discreta . 6 (2): 207. doi : 10.1016/0166-218x(83)90073-2 . SEÑOR  0707027.
  17. ^ abcd Ahmed, Tanbir (2012). "Sobre el cálculo de los números exactos de van der Waerden". Enteros . 12 (3): 417–425. doi :10.1515/integ.2011.112. SEÑOR  2955523. S2CID  11811448.
  18. ^ abcdefghijklmnopqrstu vwxyz aa Ahmed, Tanbir (2013). "Algunos números más de Van der Waerden". Diario de secuencias enteras . 16 (4): 13.4.4. SEÑOR  3056628.
  19. ^ abcdefghijk Brown, TC (1974). "Algunas cifras nuevas de van der Waerden (informe preliminar)". Avisos de la Sociedad Matemática Estadounidense . 21 : A-432.
  20. ^ abcdefghijklmnopqrstu vwxyz aa ab ac ad Ahmed, Tanbir (2009). "Algunos números nuevos de van der Waerden y algunos números tipo van der Waerden". Enteros . 9 : A6. doi :10.1515/integ.2009.007. SEÑOR  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. ^ Sela, Saharon (1988). "Límites recursivos primitivos para números de van der Waerden". Revista de la Sociedad Matemática Estadounidense . 1 (3): 683–697. doi : 10.2307/1990952 . JSTOR  1990952. SEÑOR  0929498.

Otras lecturas

enlaces externos