Teorema de Kruskal–Katona y sistemas de conjuntos

Sombras de conjuntos: el problema central

Sea $[n] = \{1, 2, \ldots, n\}$ y sea $\binom{[n]}{k}$ la familia de todos los subconjuntos de $[n]$ de tamaño $k$. Dado un sistema de conjuntos $\mathcal{A} \subseteq \binom{[n]}{k}$ (una familia de subconjuntos $k$-uniformes), definimos la sombra $\partial \mathcal{A}$ como la familia de todos los subconjuntos de tamaño $k-1$ que están contenidos en al menos un miembro de $\mathcal{A}$:

$\partial \mathcal{A} = \{ B \in \binom{[n]}{k-1} : \exists A \in \mathcal{A},\, B \subset A \}$.

La sombra aparece naturalmente en problemas de conteo: cuántas $(k-1)$-caras tiene un complejo simplicial cuyas $k$-caras forman $\mathcal{A}$, cuántos $(k-1)$-conjuntos están "cubiertos" por $\mathcal{A}$, etc.

La pregunta central: dado $|\mathcal{A}| = m$, ¿cuál es el menor tamaño posible de $|\partial \mathcal{A}|$? En otras palabras: ¿qué familia $\mathcal{A}$ de $m$ conjuntos $k$-uniformes tiene la sombra más pequeña posible?

La respuesta, dada independientemente por Kruskal (1963) y Katona (1968), es: el segmento inicial en orden coléxico (colex). Antes de enunciar el teorema precisamente, introducimos este orden.

El orden coléxico: la herramienta clave

El orden coléxico (o colex) sobre $\binom{[n]}{k}$ se define de la siguiente manera: dados dos $k$-conjuntos $A$ y $B$, se dice que $A <_{\text{colex}} B$ si el mayor elemento en el que difieren es mayor en $B$ que en $A$. Formalmente: si $m = \max(A \triangle B)$ (el mayor elemento en la diferencia simétrica), entonces $A < B$ si $m \in B$.

Ejemplos en $\binom{[5]}{3}$: el orden colex comienza $123 < 124 < 134 < 234 < 125 < 135 < 235 < 145 < 245 < 345$ (hay $\binom{5}{3}=10$ conjuntos). En este orden, el "segmento inicial de tamaño $m$" consiste en los primeros $m$ conjuntos de $\binom{[n]}{3}$ en orden colex.

Propiedad crucial del orden colex. Los segmentos iniciales en colex son "comprimidos": si $A$ está en el segmento inicial y $B$ se obtiene de $A$ reemplazando un elemento por uno más pequeño (sin crear repeticiones), entonces $B$ también está en el segmento inicial. Esta propiedad de compresión es la razón por la que el colex minimiza sombras.

Representación colex. Todo entero $m \ge 0$ tiene una única representación en "cascada": $m = \binom{c_k}{k} + \binom{c_{k-1}}{k-1} + \cdots + \binom{c_1}{1}$ con $c_k > c_{k-1} > \cdots > c_1 \ge 0$. Esta representación corresponde al $(m+1)$-ésimo conjunto de $\binom{\mathbb{N}}{k}$ en orden colex: $\{c_1+1, c_2+1, \ldots, c_k+1\}$.

Enunciado del Teorema de Kruskal–Katona

Teorema de Kruskal–Katona. Sea $\mathcal{A} \subseteq \binom{[n]}{k}$ una familia de $m$ subconjuntos $k$-uniformes. Sea $\mathcal{C}$ el segmento inicial de tamaño $m$ de $\binom{[\infty]}{k}$ en orden colex. Entonces

$|\partial \mathcal{A}| \ge |\partial \mathcal{C}|$.

En palabras: entre todas las familias de exactamente $m$ conjuntos $k$-uniformes, el segmento inicial en colex tiene la sombra más pequeña.

**Corolario: fórmula para $|\partial \mathcal{C}|$.** Si $m = \binom{c_k}{k} + \binom{c_{k-1}}{k-1} + \cdots + \binom{c_1}{1}$ es la representación en cascada de $m$, entonces

$|\partial \mathcal{C}| = \binom{c_k}{k-1} + \binom{c_{k-1}}{k-2} + \cdots + \binom{c_1}{0}$.

Esta fórmula se obtiene observando que la sombra de los primeros $\binom{c_k}{k}$ conjuntos colex de $\binom{[n]}{k}$ es exactamente los primeros $\binom{c_k}{k-1}$ conjuntos colex de $\binom{[n]}{k-1}$, y la representación en cascada actúa "dígito a dígito".

Ejemplo. Para $k=3$ y $m = 7 = \binom{4}{3} + \binom{2}{2} + \binom{1}{1} = 4+1+1$... ajustemos: $7 = \binom{4}{3} + \binom{3}{2} = 4 + 3$. Entonces la sombra mínima es $\binom{4}{2} + \binom{3}{1} = 6 + 3 = 9$. Verificación directa: los 7 primeros 3-conjuntos en colex son $123, 124, 134, 234, 125, 135, 235$, y su sombra son todos los 2-subconjuntos de ellos: $12, 13, 23, 14, 24, 34, 15, 25, 35$ —exactamente 9 conjuntos.

Prueba por compresión

Presentamos la idea central de la prueba de Katona por el método de compresión, que es el enfoque más transparente para olimpiadas.

**Operación de compresión $C_{ij}$.** Para $i < j$, define la operación $C_{ij}$ sobre una familia $\mathcal{A}$ de $k$-conjuntos: para cada $A \in \mathcal{A}$ con $j \in A$ y $i \notin A$, si $(A \setminus \{j\}) \cup \{i\} \notin \mathcal{A}$, reemplaza $A$ por $(A \setminus \{j\}) \cup \{i\}$ (sustituye el elemento mayor $j$ por el menor $i$); de lo contrario, deja $A$ igual. La familia resultante se llama $C_{ij}(\mathcal{A})$.

Lema 1. $|C_{ij}(\mathcal{A})| = |\mathcal{A}|$: la compresión no cambia el tamaño de la familia.

Lema 2. $|\partial C_{ij}(\mathcal{A})| \le |\partial \mathcal{A}|$: la compresión no incrementa la sombra.

El Lema 2 es la pieza central. La demostración verifica que cada conjunto de la sombra de $C_{ij}(\mathcal{A})$ corresponde a un conjunto de la sombra de $\mathcal{A}$, con la posible excepción de casos que se cancelan.

Familia comprimida. Una familia $\mathcal{A}$ es comprimida si $C_{ij}(\mathcal{A}) = \mathcal{A}$ para todo $i < j$. Es decir, $\mathcal{A}$ es invariante bajo todas las comprensiones.

Teorema de Kruskal–Katona (vía compresión). Toda familia $\mathcal{A}$ puede comprimirse iterativamente hasta obtener una familia comprimida $\mathcal{A}^*$ con $|\mathcal{A}^*| = |\mathcal{A}|$ y $|\partial \mathcal{A}^*| \le |\partial \mathcal{A}|$. Las familias comprimidas de tamaño $m$ son exactamente los segmentos iniciales en colex. Luego el segmento inicial en colex minimiza la sombra entre todas las familias de tamaño $m$.

Aplicaciones a problemas olímpicos y de intersección

Aplicación 1: Acotar sombras en complejos simpliciales. En un complejo simplicial (familia de conjuntos cerrada hacia abajo), el Teorema de Kruskal–Katona da la cota óptima para el número de $(k-1)$-caras en función del número de $k$-caras. Esto permite demostrar resultados del tipo "si un complejo tiene $m$ triángulos, tiene al menos $f(m)$ aristas".

Aplicación 2: Teorema de Erdős-Ko-Rado revisitado. Sea $\mathcal{A} \subseteq \binom{[n]}{k}$ una familia intersectante (todo par de conjuntos en $\mathcal{A}$ tiene intersección no vacía). Para $n \ge 2k$, el Teorema de Erdős-Ko-Rado da $|\mathcal{A}| \le \binom{n-1}{k-1}$. Una demostración elegante usa Kruskal–Katona: si $|\mathcal{A}| > \binom{n-1}{k-1}$, la sombra de $\mathcal{A}$ tiene tamaño mayor que $\binom{n-1}{k-2}$, y un argumento de complementación fuerza que dos conjuntos de $\mathcal{A}$ sean complementarios (disjuntos), contradiciendo la intersectancia.

Aplicación 3: Isoperimetría discreta. El Teorema de Kruskal–Katona es el análogo discreto del isoperímetro continuo: "entre todos los cuerpos de volumen fijo, la bola tiene el menor área superficial". En el hipercubo $\{0,1\}^n$, entre todos los conjuntos de $m$ vértices, el que tiene el menor borde (número de aristas hacia fuera) es el segmento inicial en colex. Esta versión del "problema isoperimétrico del hipercubo" tiene la misma respuesta que Kruskal–Katona.

Señal en olimpiadas: cuando el problema dice "dado un sistema de conjuntos de cierto tamaño uniforme, acota el número de subconjuntos de un tamaño menor que aparecen", o "minimiza la sombra", o "en una familia intersectante de $k$-conjuntos de $[n]$, acota el tamaño", Kruskal–Katona (o Erdős-Ko-Rado, que se prueba con él) es la herramienta apropiada.

Iteración de sombras y la cascada de Kruskal

El Teorema de Kruskal–Katona no solo aplica a la primera sombra. Iterando, se obtiene una cota para $|\partial^j \mathcal{A}|$, la $j$-ésima sombra de $\mathcal{A}$ (aplicar $\partial$ exactamente $j$ veces).

Para el segmento inicial colex de tamaño $m$ en $\binom{[n]}{k}$, con $m = \binom{c_k}{k} + \cdots + \binom{c_1}{1}$, la $j$-ésima sombra tiene tamaño $\binom{c_k}{k-j} + \binom{c_{k-1}}{k-j-1} + \cdots$, donde los índices se desplazan $j$ posiciones. Esto permite calcular con exactitud la cascada completa de sombras para cualquier familia dada su representación en colex.

Este resultado tiene aplicaciones en la teoría de $f$-vectores de complejos simpliciales: el $f$-vector $(f_0, f_1, \ldots, f_d)$ de un complejo simplicial puro $d$-dimensional satisface las condiciones de Kruskal–Katona (condición necesaria y suficiente para ser el $f$-vector de un complejo simplicial). Determinar qué secuencias enteras son $f$-vectores de complejos simpliciales es un problema central de combinatoria topológica.

Para olimpiadas avanzadas (tipo ISL C o IMO día 2-3): los problemas que involucran $f$-vectores o "caracterizar todas las familias con ciertos parámetros fijos" pueden requerir las condiciones de Kruskal–Katona. Reconocer cuándo el problema tiene estructura de sombra iterada es la habilidad clave.