Lección 1.3: Ramsey multidimensional: hipergrafos y versiones generales — Espinoza Olimpiadas

Números de Ramsey para hipergrafos

Un $r$ -hipergrafo sobre un conjunto $V$ es una colección $\mathcal{H}$ de subconjuntos de tamaño $r$ de $V$ (llamados hipearistas o $r$ -aristas). Un grafo ordinario es un $2$ -hipergrafo. El $r$ -hipergrafo completo sobre $n$ vértices, denotado $K_n^{(r)}$ , contiene todas las $\binom{n}{r}$ posibles $r$ -aristas.

El número de Ramsey para hipergrafos $R^{(r)}(s,t)$ se define como el menor $n$ tal que toda 2-coloración de las $r$ -aristas de $K_n^{(r)}$ contiene un $K_s^{(r)}$ completamente en el primer color o un $K_t^{(r)}$ completamente en el segundo color. Para $r=2$ recuperamos los números de Ramsey ordinarios.

La existencia de $R^{(r)}(s,t)$ para todo $r,s,t$ se demuestra por una inducción sobre $r$ : para $r=1$ , $R^{(1)}(s,t) = s+t-1$ (principio de paloma). Para $r \ge 2$ , la recurrencia análoga $R^{(r)}(s,t) \le R^{(r-1)}\bigl(R^{(r)}(s-1,t),\, R^{(r)}(s,t-1)\bigr) + 1$ proporciona la inducción. La demostración es una generalización directa del argumento estándar: fijamos una $r$ -arista y particionamos las demás según su color.

Para $r=3$ : $R^{(3)}(4,4)$ es conocido ser al menos $13$ y a lo sumo $\ \text{(valor no exactamente determinado al momento de esta lección)}$ . Los números de Ramsey para hipergrafos de orden $r \ge 3$ crecen aún más rápido que los de grafos. La demostración de la cota superior para $r=3$ sigue el mismo esquema inductivo pero involucra una "torre" de números de Ramsey de orden $r=2$ en los exponents.

Consecuencia notable: el Teorema de Ramsey para 3-hipergrafos ya implica la finitud de los números de Van der Waerden. Esta conexión, aunque no directa, muestra que los hipergrafos son el entorno "natural" para la teoría de Ramsey en su máxima generalidad.

R^{(r)}(s,t) \le R^{(r-1)}\!\bigl(R^{(r)}(s-1,\,t),\; R^{(r)}(s,\,t-1)\bigr) + 1

El Teorema de Ramsey infinito

El Teorema de Ramsey finito que conocemos dice que $R(s,t)$ es finito para todo $s,t$ . Existe una versión más poderosa que habla de conjuntos infinitos.

Teorema de Ramsey infinito. Sea $r \ge 1$ un entero. En toda $2$ -coloración de las $r$ -aristas del $r$ -hipergrafo completo sobre $\mathbb{N}$ (el conjunto de los naturales), existe un subconjunto infinito $H \subseteq \mathbb{N}$ tal que todas las $r$ -aristas de $H$ tienen el mismo color. Un tal $H$ se llama subconjunto homogéneo o monocromático infinito.

La demostración para $r=1$ es trivial: en toda 2-coloración de $\mathbb{N}$ , uno de los dos colores aparece infinitas veces. Para $r=2$ : construimos $H$ inductivamente. Elige cualquier $n_1 \in \mathbb{N}$ . Los vecinos de $n_1$ en el primer color forman $A_1$ , los del segundo color forman $B_1$ ; uno de estos dos conjuntos es infinito, digamos $A_1$ . Ahora elige $n_2 \in A_1$ : dentro de $A_1$ , los vecinos de $n_2$ en el primer color forman $A_2 \subseteq A_1$ (o $B_2$ ). Continuando, obtenemos una sucesión $n_1 < n_2 < \cdots$ tal que todas las aristas $\{n_i, n_j\}$ con $i < j$ tienen el mismo color (el color mayoritario en el proceso), más una corrección al final por el principio de paloma infinito (el Lema de König o el axioma de elección dependiente).

El Teorema de Ramsey infinito implica el finito como corolario. Además, es el fundamento de numerosos resultados en teoría de conjuntos descriptiva y topología. En combinatoria, la versión infinita permite deducir resultados de finitud por argumentos de compacidad: si para todo $n$ existiese una coloración de $K_n^{(r)}$ sin clique monocromático de tamaño $k$ , por compacidad (o el Lema de König para árboles finitos pero de ramificación no acotada) existiría una coloración de $K_\mathbb{N}^{(r)}$ sin clique monocromático infinito, contradiciendo el Ramsey infinito.

El Ramsey infinito tiene también una formulación en términos de sucesiones: toda sucesión de reales $(a_n)$ tiene una subsucesión monótona. Este resultado elemental es una forma encubierta del Ramsey infinito para $r=2$ con la 2-coloración " $(a_i, a_j)$ rojo si $a_i < a_j$ , azul si $a_i \ge a_j$ ".

\forall\, c: \binom{\mathbb{N}}{r} \to [2],\quad \exists\, H \subseteq \mathbb{N}\text{ infinito, }c\text{ constante en }\binom{H}{r}

El Teorema de Hales–Jewett: el metateorema

El Teorema de Hales–Jewett (1963) es el resultado más general de la teoría de Ramsey combinatoria. Opera en el espacio combinatorio $[k]^n = \{1, 2, \ldots, k\}^n$ (el conjunto de todas las $n$ -tuplas con entradas en $\{1,\ldots,k\}$ ), que puede pensarse como las casillas de un hipercubo $k$ -dimensional de dimensión $n$ .

Una línea combinatoria en $[k]^n$ es un conjunto de $k$ puntos de la forma $\{(x_1, \ldots, x_n) : x_i = j \text{ para } i \in I, x_i = c_i \text{ para } i \notin I\}$ donde $I \subseteq [n]$ es un conjunto de coordenadas activas, $c_i$ son constantes para $i \notin I$ , y $j$ varía de $1$ a $k$ . En otras palabras, las coordenadas activas varían juntas, tomando todos los valores de $1$ a $k$ simultáneamente.

Teorema de Hales–Jewett. Para todo $k \ge 1$ y $r \ge 1$ , existe $HJ(k,r)$ tal que para todo $n \ge HJ(k,r)$ , toda $r$ -coloración de $[k]^n$ contiene una línea combinatoria monocromática.

La demostración es por inducción doble sobre $(k,r)$ . El caso $k=2$ es equivalente al principio de paloma iterado. El paso inductivo en $k$ es el argumento más delicado: se usa el truco de "comprimir" dos colores en uno y aplicar la hipótesis inductiva varias veces, un argumento que Hales y Jewett llamaron "el truco de la estrategia robada" en el contexto de juegos.

La importancia del Teorema de Hales–Jewett radica en sus corolarios: el Teorema de Van der Waerden (identificando $[k]^n$ con progresiones aritméticas), el Teorema de Ramsey (identificando las $r$ -aristas de $K_n$ con configuraciones en cierto hipercubo), y el Teorema de Gallai–Witt (la versión afín del Van der Waerden). La frase atribuida a Hales–Jewett es que "todos los teoremas de Ramsey en dimensiones suficientemente altas son consecuencias de este único resultado".

HJ(k,r) < \infty \quad \Rightarrow \quad W(r,k) < \infty

De Hales–Jewett a Van der Waerden

El Teorema de Van der Waerden afirma que $W(r,k)$ es finito: toda $r$ -coloración de $\mathbb{Z}$ (o de un intervalo suficientemente largo) contiene una progresión aritmética monocromática de longitud $k$ . Veamos cómo deducirlo de Hales–Jewett.

Identificamos cada punto de $[k]^n$ con el entero $\sum_{i=1}^n x_i \cdot k^{i-1} \in \{0, 1, \ldots, k^n - 1\}$ (representación en base $k$ ). Esta identificación es una biyección. Una línea combinatoria con coordenadas activas $I$ y constantes $c_i$ para $i \notin I$ corresponde al conjunto de enteros $\left\{\sum_{i \notin I} c_i k^{i-1} + j \sum_{i \in I} k^{i-1} : j = 0, 1, \ldots, k-1\right\}$ , que es una progresión aritmética de razón $d = \sum_{i \in I} k^{i-1}$ y longitud $k$ .

Por lo tanto: si coloreamos $\{0, 1, \ldots, k^n - 1\}$ con $r$ colores (la coloración inducida por la de $[k]^n$ ), la línea combinatoria monocromática que garantiza Hales–Jewett se traduce en una progresión aritmética monocromática de longitud $k$ en $\{0, \ldots, k^n - 1\}$ . Con $n = HJ(k, r)$ , obtenemos $W(r,k) \le k^{HJ(k,r)}$ .

La deducción inversa también es posible (aunque más elaborada): Van der Waerden implica Hales–Jewett en cierto sentido dimensional. Esto establece una equivalencia entre los dos teoremas que hace de Hales–Jewett una "forma dimensional de Van der Waerden".

Para la olimpiada, la clave no es conocer la prueba de Hales–Jewett, sino reconocer que los teoremas de Ramsey, Schur, Van der Waerden y sus variantes comparten la misma "alma": la inevitabilidad del orden en coloraciones de estructuras grandes. Un problema que pide demostrar que en cualquier coloración de $\{1,\ldots,N\}$ aparece cierta configuración aritmética o algebraica es casi siempre una consecuencia (directa o indirecta) de alguno de estos metateoremas.

W(r,k) \le k^{HJ(k,r)}

Ramsey para más de dos colores: la recurrencia general

Para $r$ colores, definimos $R(n_1, n_2, \ldots, n_r)$ como el menor $N$ tal que toda $r$ -coloración de las aristas de $K_N$ contiene un $K_{n_i}$ completamente en el color $i$ para algún $i$ . La recurrencia general es $R(n_1, \ldots, n_r) \le R(n_1, \ldots, n_{r-2}, R(n_{r-1}, n_r))$ , reduciendo el número de colores en uno en cada paso.

Aplicando esta recurrencia iteradamente: $R(n_1, \ldots, n_r) \le R(n_1, \ldots, n_{r-3}, R(n_{r-2}, R(n_{r-1}, n_r)))$ . La cota resultante es una composición de funciones de tipo $R(\cdot, \cdot)$ , que crece como una torre de exponenciales de altura $r-1$ . Para el caso simétrico $n_1 = \cdots = n_r = k$ : $R_r(k) \le \underbrace{f(f(\cdots f(k) \cdots ))}_{r-1 \text{ veces}}$ donde $f(m) = R(k, m) \le \binom{k+m-2}{k-1}$ .

Cota inferior para $r$ colores: por el método probabilístico con $r$ colores, coloreamos cada arista de $K_n$ uniformemente en $\{1,\ldots,r\}$ . La probabilidad de que un $k$ -clique fijo sea monocromático es $r \cdot r^{-\binom{k}{2}} = r^{1-\binom{k}{2}}$ . La condición de Erdős se convierte en $\binom{n}{k} \cdot r^{1-\binom{k}{2}} < 1$ , dando $R_r(k) > n$ para $n$ apropiado. Numéricamente: $R_r(k) > r^{(k-1)/2}$ asintóticamente, una cota que crece como $r^{k/2}$ .

En el IMO Shortlist C5 de 2014 y en la Olimpiada de Rusia 2018 aparecen problemas que requieren conocer el valor $R(3,3,3) = 17$ y usar la coloración extremal de $K_{16}$ (construida sobre el plano proyectivo de Fano). La construcción: los vértices son los $7$ puntos del plano de Fano más $9$ extras organizados en un cuadrado latino $3 \times 3$ , con los colores determinados por la geometría del plano. Esta construcción es un ejemplo perfecto de cómo la geometría finita y la combinatoria extremal se entrelazan.

Para el concursante, el mensaje práctico es: cuando un problema de olimpiada menciona tres colores y pide evitar o garantizar estructuras en $\{1,\ldots,n\}$ o en $K_n$ , el umbral $n=17$ (o $16$ para la contraparte) es la frontera natural donde la garantía entra en juego. Conocer $R(3,3,3)=17$ exacto no se exige, pero saber que existe y que la construcción extremal proviene de la geometría finita es una ventaja cultural.

R(\underbrace{k,k,\ldots,k}_{r}) \ge r^{(k-1)/2}

Ramsey multidimensional: hipergrafos y versiones generales

Objetivo de la lección

Números de Ramsey para hipergrafos

El Teorema de Ramsey infinito

El Teorema de Hales–Jewett: el metateorema

De Hales–Jewett a Van der Waerden

Ramsey para más de dos colores: la recurrencia general

Problemas del Capítulo 1 — con solución