Número de van der Waerden

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

editar

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.[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   tienen un límite superior dado por

 

según la prueba de Gowers.[8]

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.[9]

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 (en inglés: off-diagonal van der Waerden numbers. 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 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   de la jerarquía de Grzegorczyk.

Véase también

editar

Referencias

editar
  1. Rabung, John; Lotts, Mark (2012). «Improving the use of cyclic zippers in finding lower bounds for van der Waerden numbers». Electron. J. Combin. 19 (2). MR 2928650. 
  2. a b c d e f g h i j k Chvátal, Vašek (1970). «Some unknown van der Waerden numbers». En Guy, Richard; Hanani, Haim; Sauer, Norbert et al., eds. Combinatorial Structures and Their Applications. New York: Gordon and Breach. pp. 31-33. MR 0266891. 
  3. a b c d e f g Beeler, Michael D.; O'Neil, Patrick E. (1979). «Some new van der Waerden numbers». Discrete Math. 28 (2): 135-146. MR 0546646. doi:10.1016/0012-365x(79)90090-6. 
  4. a b c d e f g h Kouril, Michal (2012). «Computing the van der Waerden number W(3,4)=293». Integers 12: A46. MR 3083419. 
  5. a b Stevens, Richard S.; Shantaram, R. (1978). «Computer-generated van der Waerden partitions». Math. Comp. 32: 635-636. MR 0491468. doi:10.1090/s0025-5718-1978-0491468-x. 
  6. a b Kouril, Michal; Paul, Jerome L. (2008). «The Van der Waerden Number W(2,6) is 1132». Experimental Mathematics 17 (1): 53-61. MR 2410115. doi:10.1080/10586458.2008.10129025. 
  7. a b c d e f «Daniel Monroe, Van Der Waerden Numbers». vdwnumbers.org. Archivado desde el original el 16 de septiembre de 2015. Consultado el 19 de septiembre de 2015. 
  8. Gowers, Timothy (2001). «A new proof of Szemerédi's theorem». Geom. Funct. Anal. 11 (3): 465-588. MR 1844079. doi:10.1007/s00039-001-0332-9. 
  9. Berlekamp, E. (1968). «A construction for partitions which avoid long arithmetic progressions». Canadian Mathematical Bulletin 11: 409-414. MR 0232743. doi:10.4153/CMB-1968-047-7. 
  10. a b c d e f g h i j k l Landman, Bruce; Robertson, Aaron; Culver, Clay (2005). «Some New Exact van der Waerden Numbers». Integers 5 (2): A10. MR 2192088. Archivado desde el original el 4 de marzo de 2016. Consultado el 8 de marzo de 2019. 
  11. a b c d e f g Kouril, Michal (2006). A Backtracking Framework for Beowulf Clusters with an Extension to Multi-Cluster Computation and Sat Benchmark Problem Implementation (Tesis de Ph.D.). University of Cincinnati. 
  12. a b Ahmed, Tanbir (2010). «Two new van der Waerden numbers w(2;3,17) and w(2;3,18)». Integers 10: 369-377. MR 2684128. doi:10.1515/integ.2010.032. 
  13. Ahmed, Tanbir; Kullmann, Oliver; Snevily, Hunter. «On the van der Waerden numbers w(2;3,t)». Discrete Appl. Math. 174 (2014): 27-51. MR 3215454. arXiv:1102.5433. doi:10.1016/j.dam.2014.05.007. 
  14. Beeler, Michael D. (1983). «A new van der Waerden number». Discrete Applied Mathematics 6 (2): 207. MR 0707027. doi:10.1016/0166-218x(83)90073-2. 
  15. a b c d Ahmed, Tanbir (2012). «On computation of exact van der Waerden numbers». Integers 12 (3): 417-425. MR 2955523. doi:10.1515/integ.2011.112. 
  16. a b c d e f g h i j k l m n ñ o p q r s t u v w x y z Ahmed, Tanbir (2013). «Some More Van der Waerden numbers». Journal of Integer Sequences 16 (4): 13.4.4. MR 3056628. 
  17. a b c d e f g h i j k Brown, T. C. (1974). «Some new van der Waerden numbers (preliminary report)». Notices of the American Mathematical Society 21: A-432. 
  18. a b c d e f g h i j k l m n ñ o p q r s t u v w x y z aa ab ac Ahmed, Tanbir (2009). «Some new van der Waerden numbers and some van der Waerden-type numbers». Integers 9: A6. MR 2506138. doi:10.1515/integ.2009.007. 
  19. Schweitzer, Pascal (2009). Problems of Unknown Complexity, Graph isomorphism and Ramsey theoretic numbers (Tesis de Ph.D.). U. des Saarlandes. 
  20. Shelah, Saharon (1988). «Primitive recursive bounds for van der Waerden numbers». J. Amer. Math. Soc. 1 (3): 683-697. MR 929498. doi:10.2307/1990952. 

Lecturas adicionales

editar

Enlaces externos

editar