Teorema de Graham-Rothschild

En matemáticas, el teorema de Graham-Rothschild es un teorema que aplica la teoría de Ramsey a la combinatoria de palabras y cubos combinatorios . Lleva el nombre de Ronald Graham y Bruce Lee Rothschild , quienes publicaron su prueba en 1971. ^[1] A través del trabajo de Graham, Rothschild y Klaus Leeb  [de] en 1972, se convirtió en parte de los fundamentos de la teoría estructural de Ramsey . ^[2] Un caso especial del teorema de Graham-Rothschild motiva la definición del número de Graham , un número que fue popularizado por Martin Gardner en Scientific American ^[3] y que figura en el Libro Guinness de los Récords Mundiales como el número más grande jamás aparecido en un prueba matemática. ^[4]

Fondo

El teorema involucra conjuntos de cadenas , todas con la misma longitud , sobre un alfabeto finito , junto con un grupo que actúa sobre el alfabeto. Un cubo combinatorio es un subconjunto de cadenas determinado restringiendo algunas posiciones de la cadena para que contengan una letra fija del alfabeto y restringiendo otros pares de posiciones para que sean iguales entre sí o estén relacionadas entre sí mediante la acción del grupo. Esta determinación se puede especificar de manera más formal mediante una palabra de parámetro etiquetada , una cadena con caracteres comodín en las posiciones que no están obligadas a contener una letra fija y con etiquetas adicionales que describen qué caracteres comodín deben ser iguales o relacionados por la acción del grupo. La dimensión del cubo combinatorio es el número de elecciones libres que se pueden realizar para estos caracteres comodín. Un cubo combinatorio de dimensión uno se llama línea combinatoria. ^[4] ${\displaystyle n}$

Por ejemplo, en el juego de tres en raya , las nueve celdas de un tablero de tres en raya se pueden especificar mediante cadenas de longitud dos sobre el alfabeto de tres símbolos {1,2,3} (las coordenadas cartesianas de las celdas), y las líneas ganadoras de tres celdas forman líneas combinatorias. Las líneas horizontales se obtienen fijando la coordenada (la segunda posición de la cadena de longitud dos) y dejando que la coordenada se elija libremente, y las líneas verticales se obtienen fijando la coordenada y dejando que la coordenada se elija libremente. Las dos líneas diagonales del tablero de tres en raya se pueden especificar mediante una palabra de parámetro con dos caracteres comodín que están obligados a ser iguales (para la diagonal principal ) o a estar relacionados mediante una acción de grupo que intercambia el 1 y 3 caracteres (para la antidiagonal ). ^[5] ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle y}$

Se denota el conjunto de todos los cubos combinatorios de dimensión , para cadenas de longitud sobre un alfabeto con acción grupal . Un subcubo de un cubo combinatorio es otro cubo combinatorio de dimensión más pequeña que forma un subconjunto del conjunto de cadenas en el cubo combinatorio más grande. Los subcubos de un cubo combinatorio también pueden describirse mediante una acción de composición natural sobre palabras de parámetro, obtenida sustituyendo los símbolos de una palabra de parámetro por los comodines de otra. ^[4] ${\displaystyle d}$ ${\displaystyle n}$ ${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle [A,G]{\tbinom {n}{d}}}$

Declaración

Con la notación anterior, el teorema de Graham-Rothschild toma como parámetros un alfabeto , una acción grupal , un número finito de colores y dos dimensiones de cubos combinatorios y con . Afirma que, para cada combinación de , , , y , existe una longitud de cadena tal que, si a cada cubo combinatorio se le asigna uno de los colores, entonces existe un cubo combinatorio en todos cuyos subcubos dimensionales se asigna el mismo color. ^[5] ${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle r}$ ${\displaystyle m}$ ${\displaystyle k}$ ${\displaystyle m>k}$ ${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle r}$ ${\displaystyle m}$ ${\displaystyle k}$ ${\displaystyle n\geq m}$ ${\displaystyle [A,G]{\tbinom {n}{k}}}$ ${\displaystyle r}$ ${\displaystyle [A,G]{\tbinom {n}{m}}}$ ${\displaystyle k}$

También se conoce una versión infinitaria del teorema de Graham-Rothschild. ^[6]

Aplicaciones

El caso especial del teorema de Graham-Rothschild con , y la acción grupal trivial es el teorema de Hales-Jewett , que establece que si todas las cadenas suficientemente largas de un alfabeto determinado están coloreadas, entonces existe una línea combinatoria monocromática. ^[5] ${\displaystyle m=1}$ ${\displaystyle k=0}$

Una coloración bicolor de las líneas combinatorias de un cubo binario tridimensional y un plano combinatorio monocromático en este cubo coloreado.

El número de Graham es un límite para el teorema de Graham-Rothschild con , , , y una acción de grupo no trivial. Para estos parámetros, el conjunto de cadenas de longitud sobre un alfabeto binario describe los vértices de un hipercubo bidimensional , cada dos de los cuales forman una línea combinatoria. El conjunto de todas las líneas combinatorias se puede describir como las aristas de un gráfico completo en los vértices. El teorema establece que, para una dimensión suficientemente alta , siempre que a este conjunto de aristas del gráfico completo se le asignan dos colores, existe un plano combinatorio monocromático: un conjunto de cuatro vértices de hipercubo que pertenecen a un plano geométrico común y tienen los seis bordes asignados del mismo color. El número de Graham es un límite superior para este número , calculado mediante exponenciación repetida; se cree que es significativamente mayor que el más pequeño para el cual es verdadero el enunciado del teorema de Graham-Rothschild. ^[4] ${\displaystyle |A|=2}$ ${\displaystyle r=2}$ ${\displaystyle m=2}$ ${\displaystyle k=1}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

Referencias

1. Graham, RL ; Rothschild, BL (1971), "Teorema de Ramsey para conjuntos de parámetros", Transactions of the American Mathematical Society , 159 : 257–292, doi : 10.2307/1996010, MR  0284352 ${\displaystyle n}$
2. Graham, RL ; Leeb, K.; Rothschild, BL (1972), "Teorema de Ramsey para una clase de categorías", Actas de la Academia Nacional de Ciencias de los Estados Unidos de América , 69 : 119–120, doi : 10.1073/pnas.69.1.119 , MR  0306009, PMC 427557 ; versión completa en Graham, RL ; Leeb, K.; Rothschild, BL (1972), "Teorema de Ramsey para una clase de categorías", Avances en Matemáticas , 8 (3): 417–433, doi :10.1016/0001-8708(72)90005-9
3. Gardner, Martin (noviembre de 1977), "En el que unir conjuntos de puntos mediante líneas conduce a caminos diversos (y desviados)", Juegos matemáticos , Scientific American , 237 (5): 18–28, doi :10.1038/scientificamerican1177-18; revisado y reimpreso en El libro colosal de las matemáticas: acertijos, paradojas y problemas clásicos (2001)
4. Prömel, Hans Jürgen (2002), "Grandes números, notación de flechas de Knuth y teoría de Ramsey", Synthese , 133 (1–2): 87–105, doi :10.1023/A:1020879709125, JSTOR  20117296, MR  1950045
5. Prömel, Hans Jürgen (2013), Teoría de Ramsey para estructuras discretas , Springer International Publishing, págs. 41–51, doi :10.1007/978-3-319-01315-2; consulte en particular el capítulo 3 "Definiciones y ejemplos básicos" (págs. 33–39, doi :10.1007/978-3-319-01315-2_3) para las definiciones de palabras de parámetros y cubos combinatorios, capítulo 4 "Teorema de Hales-Jewett" (págs. 41–51, doi :10.1007/978-3-319-01315-2_4) para el ejemplo del tres en raya, y el capítulo 5 "Teorema de Graham-Rothschild" (págs. 53–59, doi :10.1007/ 978-3-319-01315-2_5) para el propio teorema de Graham-Rothschild
6. Carlson, Timothy J.; Hindman, Neil ; Strauss, Dona (2006), "Una extensión infinita del teorema de conjuntos de parámetros de Graham-Rothschild", Transactions of the American Mathematical Society , 358 (7): 3239–3262, doi : 10.1090/S0002-9947-06-03899-2 , hdl : 1811/48782 , señor  2216266