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
![{\displaystyle W(r,k)\leq 2^{2^{r^{2^{2^{k+9}}}}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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
![{\displaystyle p\cdot 2^{p}\leq W(2,p+1),}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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 .![{\displaystyle {\mathcal {E}}^{5}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Ver también
Referencias
- ^ 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.
- ^ 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.
- ^ 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.
- ^ abcdefgh Kouril, Michal (2012). "Calcular el número de van der Waerden W (3,4) = 293". Enteros . 12 : A46. SEÑOR 3083419.
- ^ 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.
- ^ ab Heule, MarijnJ (2017). «Evitar ternas en progresión aritmética» (PDF) . Revista de combinatoria . 8 : 391–422.
- ^ 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.
- ^ 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].
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ abcd Kouril, Michal (2015). "Aprovechando los clústeres FPGA para cálculos SAT". Computación paralela: en el camino hacia la exaescala : 525–532.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ abcdefghijk Brown, TC (1974). "Algunas cifras nuevas de van der Waerden (informe preliminar)". Avisos de la Sociedad Matemática Estadounidense . 21 : A-432.
- ^ 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.
- ^ Schweitzer, Pascal (2009). Problemas de complejidad desconocida, isomorfismo de grafos y números teóricos de Ramsey (tesis doctoral). Universidad de Sarre.
- ^ 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
- Landman, Bruce M.; Robertson, Aarón (2014). Teoría de Ramsey sobre los números enteros . Biblioteca de Matemáticas para Estudiantes. vol. 73 (Segunda ed.). Providence, RI: Sociedad Estadounidense de Matemáticas. doi :10.1090/stml/073. ISBN 978-0-8218-9867-3. SEÑOR 3243507.
- Herwig, PR; Heule, MJH; van Lambalgen, PM; van Maaren, H. (2007). "Un nuevo método para construir límites inferiores para números de Van der Waerden". La Revista Electrónica de Combinatoria . 14 (1). doi : 10.37236/925 . SEÑOR 2285810.
enlaces externos