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 ${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\cdots 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\geq 2$ tienen un límite superior dado por

W(r,k)\leq 2^{2^{r^{2^{2^{k+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\cdot 2^{p}\leq W(2,p+1),

según la prueba de Berlekamp.^[9]

También es posible denotar $w(r;k_{1},k_{2},\cdots ,k_{r})$ para referirse al menor número $w$ tal que cualquier coloración de los enteros ${1,2,\cdots ,w}$ con $r$ colores contiene una progresión de longitud $k_{i}$ de color $i$ para alguna $i$ . 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 $W(r,k)=w(r;k,k,\cdots ,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;k₁, k₂, …, k_r)	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 ${\mathcal {E}}^{5}$ de la jerarquía de Grzegorczyk.

Véase también

Referencias

↑ 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.
↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^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.
↑ ^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.
↑ ^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.
↑ ^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.
↑ ^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.
↑ ^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.
↑ 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.
↑ 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.
↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^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.
↑ ^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.
↑ ^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.
↑ 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.
↑ 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.
↑ ^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.
↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m ⁿ ^ñ ^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.
↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k Brown, T. C. (1974). «Some new van der Waerden numbers (preliminary report)». Notices of the American Mathematical Society 21: A-432.
↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m ⁿ ^ñ ^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.
↑ Schweitzer, Pascal (2009). Problems of Unknown Complexity, Graph isomorphism and Ramsey theoretic numbers (Tesis de Ph.D.). U. des Saarlandes.
↑ 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

Landman, Bruce M.; Robertson, Aaron (2014). Ramsey Theory on the Integers. Student Mathematical Library 73 (Second edición). Providence, RI: American Mathematical Society. ISBN 978-0-8218-9867-3. MR 3243507. doi:10.1090/stml/073.
Herwig, P. R.; Heule, M. J. H.; van Lambalgen, P. M.; van Maaren, H. (2007). «A New Method to Construct Lower Bounds for Van der Waerden Numbers». The Electronic Journal of Combinatorics 14 (1). MR 2285810.

Enlaces externos

O'Bryant, Kevin and Weisstein, Eric W. «Van der Waerden Number». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
Ahmed, Tanbir. «Known van der Waerden Number». Archivado desde el original el 6 de septiembre de 2012. Consultado el 8 de marzo de 2019.

Datos: Q7913892

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

[chvatal1970-2] ↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^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.

[beeleroneil1979-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.

[kouril2012-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.

[ss1978-5] 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.

[kp2006-6] 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.

[:0-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.

[lrc2005-10] ↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^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.

[kouril2006-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.

[ahmed2010-12] 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.

[aks2011-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.

[beeler1983-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.

[ahmed2011-15] Ahmed, Tanbir (2012). «On computation of exact van der Waerden numbers». Integers 12 (3): 417-425. MR 2955523. doi:10.1515/integ.2011.112.

[ahmedJIS-16] ↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m ⁿ ^ñ ^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.

[brown1974-17] ↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k Brown, T. C. (1974). «Some new van der Waerden numbers (preliminary report)». Notices of the American Mathematical Society 21: A-432.

[ahmed2009-18] ↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m ⁿ ^ñ ^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.

[sch2009-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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]