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 $R R R R \dots R R R$ (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 $R G B$ . 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}, \dots, k_{r})$ para referirse al menor número $w$ tal que cualquier coloración de los enteros $1, 2, \dots, 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 (Plantilla:Lang-en. Por lo tanto $W (r, k) = w (r; k, k, \dots, 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 $ℰ^{5}$ de la jerarquía de Grzegorczyk.

Véase también

Referencias

Plantilla:Listaref

Lecturas adicionales

Enlaces externos

Plantilla:Control de autoridades

↑ Plantilla:Cita publicación
↑ ^2,00 ^2,01 ^2,02 ^2,03 ^2,04 ^2,05 ^2,06 ^2,07 ^2,08 ^2,09 ^2,10 Plantilla:Cite encyclopedia
↑ ^3,0 ^3,1 ^3,2 ^3,3 ^3,4 ^3,5 ^3,6 Plantilla:Cite journal
↑ ^4,0 ^4,1 ^4,2 ^4,3 ^4,4 ^4,5 ^4,6 ^4,7 Plantilla:Cite journal
↑ ^5,0 ^5,1 Plantilla:Cite journal
↑ ^6,0 ^6,1 Plantilla:Cite journal
↑ ^7,0 ^7,1 ^7,2 ^7,3 ^7,4 ^7,5 Plantilla:Cite web
↑ Plantilla:Cite journal
↑ Plantilla:Cite journal
↑ ^10,00 ^10,01 ^10,02 ^10,03 ^10,04 ^10,05 ^10,06 ^10,07 ^10,08 ^10,09 ^10,10 ^10,11 Plantilla:Cite journal
↑ ^11,0 ^11,1 ^11,2 ^11,3 ^11,4 ^11,5 ^11,6 Plantilla:Cite thesis
↑ ^12,0 ^12,1 Plantilla:Cite journal
↑ Plantilla:Cite journal
↑ Plantilla:Cite journal
↑ ^15,0 ^15,1 ^15,2 ^15,3 Plantilla:Cite journal
↑ ^16,00 ^16,01 ^16,02 ^16,03 ^16,04 ^16,05 ^16,06 ^16,07 ^16,08 ^16,09 ^16,10 ^16,11 ^16,12 ^16,13 ^16,14 ^16,15 ^16,16 ^16,17 ^16,18 ^16,19 ^16,20 ^16,21 ^16,22 ^16,23 ^16,24 ^16,25 ^16,26 Plantilla:Cite journal
↑ ^17,00 ^17,01 ^17,02 ^17,03 ^17,04 ^17,05 ^17,06 ^17,07 ^17,08 ^17,09 ^17,10 Plantilla:Cite journal
↑ ^18,00 ^18,01 ^18,02 ^18,03 ^18,04 ^18,05 ^18,06 ^18,07 ^18,08 ^18,09 ^18,10 ^18,11 ^18,12 ^18,13 ^18,14 ^18,15 ^18,16 ^18,17 ^18,18 ^18,19 ^18,20 ^18,21 ^18,22 ^18,23 ^18,24 ^18,25 ^18,26 ^18,27 ^18,28 ^18,29 Plantilla:Cite journal
↑ Plantilla:Cite thesis
↑ Plantilla:Cite journal

[1] Plantilla:Cita publicación

[chvatal1970-2] 2,00 ^2,01 ^2,02 ^2,03 ^2,04 ^2,05 ^2,06 ^2,07 ^2,08 ^2,09 ^2,10 Plantilla:Cite encyclopedia

[beeleroneil1979-3] 3,0 ^3,1 ^3,2 ^3,3 ^3,4 ^3,5 ^3,6 Plantilla:Cite journal

[kouril2012-4] 4,0 ^4,1 ^4,2 ^4,3 ^4,4 ^4,5 ^4,6 ^4,7 Plantilla:Cite journal

[ss1978-5] 5,0 ^5,1 Plantilla:Cite journal

[kp2006-6] 6,0 ^6,1 Plantilla:Cite journal

[:0-7] 7,0 ^7,1 ^7,2 ^7,3 ^7,4 ^7,5 Plantilla:Cite web

[8] Plantilla:Cite journal

[9] Plantilla:Cite journal

[lrc2005-10] 10,00 ^10,01 ^10,02 ^10,03 ^10,04 ^10,05 ^10,06 ^10,07 ^10,08 ^10,09 ^10,10 ^10,11 Plantilla:Cite journal

[kouril2006-11] 11,0 ^11,1 ^11,2 ^11,3 ^11,4 ^11,5 ^11,6 Plantilla:Cite thesis

[ahmed2010-12] 12,0 ^12,1 Plantilla:Cite journal

[aks2011-13] Plantilla:Cite journal

[beeler1983-14] Plantilla:Cite journal

[ahmed2011-15] 15,0 ^15,1 ^15,2 ^15,3 Plantilla:Cite journal

[ahmedJIS-16] 16,00 ^16,01 ^16,02 ^16,03 ^16,04 ^16,05 ^16,06 ^16,07 ^16,08 ^16,09 ^16,10 ^16,11 ^16,12 ^16,13 ^16,14 ^16,15 ^16,16 ^16,17 ^16,18 ^16,19 ^16,20 ^16,21 ^16,22 ^16,23 ^16,24 ^16,25 ^16,26 Plantilla:Cite journal

[brown1974-17] 17,00 ^17,01 ^17,02 ^17,03 ^17,04 ^17,05 ^17,06 ^17,07 ^17,08 ^17,09 ^17,10 Plantilla:Cite journal

[ahmed2009-18] 18,00 ^18,01 ^18,02 ^18,03 ^18,04 ^18,05 ^18,06 ^18,07 ^18,08 ^18,09 ^18,10 ^18,11 ^18,12 ^18,13 ^18,14 ^18,15 ^18,16 ^18,17 ^18,18 ^18,19 ^18,20 ^18,21 ^18,22 ^18,23 ^18,24 ^18,25 ^18,26 ^18,27 ^18,28 ^18,29 Plantilla:Cite journal

[sch2009-19] Plantilla:Cite thesis

[20] Plantilla:Cite journal

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

Número de van der Waerden

Sumario

Tablas de números de van der Waerden

Véase también

Referencias

Lecturas adicionales

Enlaces externos

Menú de navegación

Número de van der Waerden

Tablas de números de van der Waerden

Véase también

Referencias

Lecturas adicionales

Enlaces externos

Menú de navegación

Buscar