Teorema de Hales–Jewett

De Wikipedia, la enciclopedia libre

En matemáticas, el teorema de Hales-Jewett es un resultado combinatorio fundamental de la teoría de Ramsey que lleva el nombre de Alfred W. Hales y Robert I. Jewett, en relación con el grado en que los objetos de alta dimensión deben exhibir necesariamente alguna estructura combinatoria; es imposible que tales objetos sean "completamente aleatorios".[1]​

Un enunciado geométrico informal del teorema es que para cualquier entero positivo n y c hay un número H tal que si las celdas de un cubo H -dimensional n × n × n ×... × n están coloreadas con c colores, existe una fila, columna o cierta diagonal (más detalles a continuación) de longitud n cuyas celdas son del mismo color. En otras palabras, la generalización de n -en-fila, multijugador y de dimensiones superiores de un juego de tic-tac-toe no puede terminar en empate, no importa cuán grande sea n, no importa cuántas personas c están jugando, y no importa qué jugador juegue cada turno, siempre que se juegue en un tablero de dimensión H suficientemente alta. Mediante un argumento de robo de estrategia estándar, se puede concluir que si dos jugadores se alternan, entonces el primer jugador tiene una estrategia ganadora cuando H es suficientemente grande, aunque no se conoce ningún algoritmo práctico para obtener esta estrategia.

Más formalmente, sea WnH el conjunto de palabras de longitud H sobre un alfabeto con n letras; es decir, el conjunto de sucesiones de {1, 2,..., n } de longitud H. Este conjunto forma el hipercubo que es el tema del teorema. Una palabra variable w (x) en WnH todavía tiene longitud H pero incluye un elemento especial x en lugar de al menos una de las letras que lo componen. Las palabras w (1), w (2),..., w ( n) obtenidas al reemplazar todas las instancias del elemento especial x con 1, 2,..., n, forman una línea combinatoria en el espacio WnH; las líneas combinatorias corresponden a filas, columnas y (algunas de las) diagonales del hipercubo. El teorema de Hales-Jewett establece que para enteros positivos n y c dados, existe un entero positivo H, que depende de n y c, tal que para cualquier partición de WnH en c partes, hay al menos una parte que contiene toda una línea combinatoria.

Por ejemplo, tome n = 3, H = 2 y c = 2. El hipercubo WnH en este caso es solo el tablero estándar de tic-tac-toe, con nueve posiciones:

11 12 13
21 22 23
31 32 33

Una línea combinatoria típica sería la palabra 2x, que corresponde a la línea 21, 22, 23; otra línea combinatoria es 'xx, que es la línea 11, 22, 33. (Tenga en cuenta que la línea 13, 22, 31, aunque es una línea válida para el tic-tac-toe, no se considera una línea combinatoria). En este caso particular, el teorema de Hales-Jewett no se aplica; es posible dividir el tablero de tic-tac-toe en dos conjuntos, por ejemplo, {11, 22, 23, 31} y {12, 13, 21, 32, 33}, ninguno de los cuales contiene una línea combinatoria (y correspondería empate en el juego de tic-tac-toe). Por otro lado, si aumentamos H a, digamos, 8 (de modo que el tablero ahora sea de ocho dimensiones, con 38 = 6561 posiciones), y dividir este tablero en dos conjuntos (los "ceros" y "cruces"), entonces uno de los dos conjuntos debe contener una línea combinatoria (es decir, no es posible empatar en esta variante de tic-tac-toe). Para una prueba, vea a continuación.

Prueba del teorema de Hales-Jewett (en un caso especial)[editar]

Ahora demostramos el teorema de Hales-Jewett en el caso especial n = 3, c = 2, H = 8 discutido anteriormente. La idea es reducir esta tarea a la de probar versiones más simples del teorema de Hales-Jewett (en este caso particular, a los casos n = 2, c = 2, H = 2 yn = 2, c = 6, H = 6). Se puede probar el caso general del teorema de Hales-Jewett por métodos similares, usando inducción matemática.

Cada elemento del hipercubo W38 es una sucesión de ocho números del 1 al 3, por ejemplo, 13211321 es un elemento del hipercubo. Estamos asumiendo que este hipercubo está completamente lleno de "ceros" y "cruces". Usaremos una prueba por contradicción y asumiremos que ni el conjunto de ceros ni el conjunto de cruces contienen una línea combinatoria. Si fijamos los primeros seis elementos de dicha sucesión y dejamos que los dos últimos varíen, obtenemos una tablero de tic-tac-toe ordinario, por ejemplo 132113 ?? da tal tablero. Para cada uno de estos tableros abcdef ??, consideramos las posiciones abcdef11, abcdef12, abcdef22. Cada uno de estos debe ser llenado con una "cero" o una "cruz", por el principio de casillero dos de ellos deben llenarse con el mismo símbolo. Dado que dos de estas posiciones son parte de una línea combinatoria, el tercer elemento de esa línea debe estar ocupado por el símbolo opuesto (ya que asumimos que ninguna línea combinatoria tiene los tres elementos llenos con el mismo símbolo). En otras palabras, para cada elección de abcdef (que se puede considerar como un elemento del hipercubo de seis dimensiones W36), hay seis posibilidades (superpuestas):

  1. abcdef11 y abcdef12 son ceros; abcdef13 es una cruz.
  2. abcdef11 y abcdef22 son ceros; abcdef33 es una cruz.
  3. abcdef12 y abcdef22 son ceros; abcdef32 es una cruz.
  4. abcdef11 y abcdef12 son cruces; abcdef13 no es nada.
  5. abcdef11 y abcdef22 son cruces; abcdef33 no es nada.
  6. abcdef12 y abcdef22 son cruces; abcdef32 no es nada.

Por lo tanto, podemos dividir el hipercubo de seis dimensiones W36 en seis clases, correspondientes a cada una de las seis posibilidades anteriores. (Si un elemento abcdef obedece a múltiples posibilidades, podemos elegir una arbitrariamente, por ejemplo, eligiendo la más alta de la lista anterior).

Ahora considere los siete elementos 111111, 111112, 111122, 111222, 112222, 122222, 222222 en W36. Según el principio del casillero, dos de estos elementos deben pertenecer a la misma clase. Supongamos, por ejemplo, que 111112 y 112222 pertenecen a la clase (5), por lo que 11111211, 11111222, 11222211, 11222222 son cruces y 11111233, 11222233 son ceros. Pero ahora considere la posición 11333233, que debe llenarse con una cruz o con un cero. Si se llena con una cruz, entonces la línea combinatoria 11xxx2xx se llena completamente con cruces, contradiciendo nuestra hipótesis. Si, en cambio, se llena con un cero, entonces la línea combinatoria 11xxx233 se llena completamente con ceros, contradiciendo nuevamente nuestra hipótesis. Del mismo modo, si otros dos de los siete elementos anteriores de W36 entran en la misma clase. Dado que tenemos una contradicción en todos los casos, la hipótesis original debe ser falsa; por tanto, debe existir al menos una línea combinatoria que consista enteramente en ceros o enteramente en cruces.

El argumento anterior fue algo inútil; de hecho, el mismo teorema es válido para H = 4.[2]​ Si se extiende el argumento anterior a los valores generales de n y c, entonces H crecerá muy rápido; incluso cuando c = 2 (que corresponde al tic-tac-toe de dos jugadores), la H dada por el argumento anterior crece tan rápido como la función de Ackermann. La primera cota recursiva primitiva se debe a Saharon Shelah,[3]​ y sigue siendo la mejor cota en general para el número de Hales-Jewett H = H(n, c).

Conexiones con otros teoremas[editar]

Observe que el argumento anterior también da el siguiente corolario: si dejamos que A sea el conjunto de todos los números de ocho dígitos cuyos dígitos son todos 1, 2, 3 (por lo tanto, A contiene números como 11333233), y coloreamos A con dos colores, entonces A contiene al menos una progresión aritmética de longitud tres, todos cuyos elementos son del mismo color. Esto se debe simplemente a que todas las líneas combinatorias que aparecen en la demostración anterior del teorema de Hales-Jewett también forman progresiones aritméticas en notación decimal. Se puede utilizar una formulación más general de este argumento para demostrar que el teorema de Hales-Jewett generaliza el teorema de van der Waerden. De hecho, el teorema de Hales-Jewett es sustancialmente un teorema más fuerte.

Así como el teorema de van der Waerden tiene una versión de densidad más fuerte en el teorema de Szemerédi, el teorema de Hales-Jewett también tiene una versión de densidad. En esta versión reforzada del teorema de Hales-Jewett, en lugar de colorear todo el hipercubo WnH en c colores, se le da un subconjunto arbitrario A del hipercubo WnH con una densidad dada 0 < δ < 1. El teorema establece que si H es suficientemente grande dependiendo de n y δ, entonces el conjunto A debe contener necesariamente una línea combinatoria completa.

El teorema de densidad de Hales-Jewett fue probado originalmente por Furstenberg y Katznelson usando la teoría ergódica.[4]​ En 2009, el Proyecto Polymath desarrolló una nueva prueba[5]​[6]​ del teorema de densidad Hales-Jewett basada en ideas a partir de la prueba del teorema de las esquinas.[7]​ Dodos, Kanellopoulos y Tyros dieron una versión simplificada de la prueba de Polymath.[8]​

El teorema de Graham-Rothschild generaliza el teorema de Hales-Jewett en cubos combinatorios de dimensiones superiores.

Véase también[editar]

Referencias[editar]

  1. ↑ Hales, A. W.; Jewett, R. I. (1963). «Regularity and positional games». Transactions of the American Mathematical Society (en inglés) 106 (2): 222-229. ISSN 0002-9947. doi:10.1090/S0002-9947-1963-0143712-1. Consultado el 15 de febrero de 2021. 
  2. ↑ Hindman, Neil; Tressler, Eric (2014). «The first nontrivial Hales-Jewett number is four». Ars Combinatoria 113: 385-390. MR 3186481. 
  3. ↑ Shelah, Saharon (1988). «Primitive recursive bounds for van der Waerden numbers». Journal of the American Mathematical Society (en inglés) 1 (3): 683-697. ISSN 0894-0347. doi:10.1090/S0894-0347-1988-0929498-X. Consultado el 15 de febrero de 2021. 
  4. ↑ Furstenberg, H.; Katznelson, Y. (1 de diciembre de 1991). «A density version of the Hales-Jewett theorem». Journal d’Analyse Mathématique (en inglés) 57 (1): 64-119. ISSN 1565-8538. doi:10.1007/BF03041066. Consultado el 15 de febrero de 2021. 
  5. ↑ «A new proof of the density Hales-Jewett theorem» (en inglés). 
  6. ↑ Gowers, W. T. (2010). Bárány, Imre, ed. An Irregular Mind: Szemerédi is 70. Bolyai Society Mathematical Studies (en inglés). Springer. pp. 659-687. ISBN 978-3-642-14444-8. doi:10.1007/978-3-642-14444-8_21. Consultado el 15 de febrero de 2021. 
  7. ↑ Ajtai, Miklós; Szemerédi, Endre (1974). «Sets of lattice points that form no squares». Stud. Sci. Math. Hungar. 9: 9-11. MR 0369299. 
  8. ↑ Dodos, Pandelis; Kanellopoulos, Vassilis; Tyros, Konstantinos (2014). «A simple proof of the density Hales–Jewett theorem». Int. Math. Res. Not. IMRN 2014 (12): 3340-3352. MR 3217664. arXiv:1209.4986. doi:10.1093/imrn/rnt041. 

Enlaces externos[editar]

En inglés:

Obtenido de «https://es.wikipedia.org/w/index.php?title=Teorema_de_Hales–Jewett&oldid=149088778»