Sistemas de conjuntos: teoremas de Frankl y Sauer

El Teorema de Frankl-Wilson: familias con intersecciones mod $p$

Teorema de Frankl-Wilson (1981). Sea $p$ primo y $L = \{l_1, \ldots, l_s\} \subseteq \{0, 1, \ldots, p-1\}$ un conjunto de $s$ residuos. Sea $\mathcal{F}$ una familia de subconjuntos de $[n]$, todos de tamaño $r \not\equiv l_i \pmod{p}$ para ningún $i$, y tales que $|A \cap B| \equiv l_j \pmod{p}$ para algún $j$ cuando $A \ne B$. Entonces:

$|\mathcal{F}| \le \binom{n}{s}$.

La prueba es un tour de force del método polinomial. A cada conjunto $A \in \mathcal{F}$ se le asigna un polinomio $f_A(x) = \prod_{i=1}^{s} \left(\sum_{j \in A} x_j - l_i\right)$ sobre $\mathbb{F}_p$, donde $x = (x_1,\ldots,x_n) \in \{0,1\}^n$. Se verifica: (1) $f_A(\mathbf{v}_A) \ne 0$ (pues $|A| \not\equiv l_i$); (2) $f_A(\mathbf{v}_B) = 0$ para $B \ne B, B \in \mathcal{F}$ (pues $|A \cap B| \equiv l_j$ para algún $j$). Luego los polinomios $\{f_A : A \in \mathcal{F}\}$ son linealmente independientes en el espacio de funciones $\{0,1\}^n \to \mathbb{F}_p$. Después de reducir mod los ideales $x_i^2 - x_i$ (para que $x_i^2 = x_i$), cada $f_A$ tiene grado $\le s$ y puede expresarse como combinación de los $\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{s}$ monomios libres de cuadrados de grado $\le s$. Independencia lineal en este espacio de dimensión $\binom{n}{\le s}$ da $|\mathcal{F}| \le \binom{n}{s}$ (para $s$ fijo con la cota correcta).

Aplicación: la conjetura de Borsuk via Frankl-Wilson

Una de las aplicaciones más sorprendentes del Teorema de Frankl-Wilson es la refutación de la Conjetura de Borsuk (Kahn-Kalai, 1993). La conjetura decía que todo conjunto de diámetro 1 en $\mathbb{R}^d$ puede partirse en $d+1$ partes de diámetro estrictamente menor que 1.

La refutación usa Frankl-Wilson con $p = 3$ y $n = 4^k$ para construir un conjunto $\mathcal{C}$ de vectores en $\mathbb{R}^N$ (con $N$ polinomial en $n$) con la siguiente propiedad: (i) todos los pares de vectores tienen producto interno en $\{-1, 0, 1\}$ (así $\mathcal{C}$ tiene un diámetro controlado), y (ii) cualquier partición de $\mathcal{C}$ en partes de diámetro pequeño requiere $\gg (1.2)^{\sqrt{N}}$ partes — exponencialmente más que $N+1$.

La construcción toma $\mathcal{C} = \{v \in \{-1, 0, 1\}^n : \text{exactamente } n/3 \text{ coordenadas son } \pm 1\}$. La estructura mod-3 de los productos internos activa el Teorema de Frankl-Wilson, que acota el número de conjuntos con ciertas propiedades de intersección y da la cota inferior en el número de partes necesarias.

El Lema de Sauer-Shelah y la dimensión VC

Lema de Sauer-Shelah (1972). Sea $\mathcal{F}$ una familia de subconjuntos de $[n]$ que no fragmenta ("shatters") ningún subconjunto de $[n]$ de tamaño $d+1$ (es decir, para todo $S \subseteq [n]$ con $|S| = d+1$, no es cierto que $\{A \cap S : A \in \mathcal{F}\} = 2^S$). Entonces:

$|\mathcal{F}| \le \binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{d}$.

Prueba por inducción. Por inducción en $n+d$. Si $d \ge n$: la cota es $2^n \ge |\mathcal{F}|$, trivial. Si $d < n$: fijamos el elemento $n$. Sea $\mathcal{F}_0 = \{A \in \mathcal{F} : n \notin A\}$ y $\mathcal{F}_1 = \{A \setminus \{n\} : A \in \mathcal{F}, n \in A\}$. Sea $\mathcal{G} = \{A \in \mathcal{F}_1 : A \in \mathcal{F}_0\text{ también}\}$ (los conjuntos que aparecen con y sin $n$). Se verifica que $\mathcal{F}_0$ no fragmenta conjuntos de tamaño $d+1$, y $\mathcal{G}$ no fragmenta conjuntos de tamaño $d$ (ambas en $[n-1]$). Por hipótesis inductiva: $|\mathcal{F}_0| \le \binom{n-1}{\le d}$ y $|\mathcal{G}| \le \binom{n-1}{\le d-1}$. Como $|\mathcal{F}| = |\mathcal{F}_0| + |\mathcal{G}| \le \binom{n-1}{\le d} + \binom{n-1}{\le d-1} = \binom{n}{\le d}$ (por la identidad de Pascal), se concluye.

La dimensión de Vapnik-Chervonenkis (dimensión VC) de $\mathcal{F}$ es el mayor $d$ tal que $\mathcal{F}$ fragmenta algún conjunto de tamaño $d$. El Lema de Sauer-Shelah dice: si la dimensión VC de $\mathcal{F}$ es $d$, entonces $|\mathcal{F}| \le n^d + 1$ (para $n$ grande). Este resultado es fundamental en teoría del aprendizaje estadístico (PAC learning): controla la complejidad de hipótesis y la velocidad de convergencia empírica.

El Teorema de Alon-Babai-Suzuki

El Teorema de Alon-Babai-Suzuki (1991) es una generalización simultánea del Teorema de Frankl-Wilson y del Lema de Sauer-Shelah. Dado un primo $p$, conjuntos $K = \{k_1,\ldots,k_r\}$ y $L = \{l_1,\ldots,l_s\}$ de residuos mod $p$ con $K \cap L = \emptyset$, y una familia $\mathcal{F}$ donde $|A| \bmod p \in K$ para todo $A$ y $|A \cap B| \bmod p \in L$ para todo $A \ne B$:

$|\mathcal{F}| \le \binom{n}{s} + \binom{n}{s-1} + \cdots + \binom{n}{s-r+1}$.

La prueba combina el método polinomial (asignar a cada $A$ un polinomio de grado $s$ que discrimina a $A$ del resto de la familia) con el Lema de la Dimensión.

En olimpiadas, estas cotas aparecen en problemas de sistemas de conjuntos con condiciones de intersección modulares. La estrategia de ataque es: (1) identificar los valores de $|A|$ y $|A \cap B|$ módulo algún primo; (2) elegir $p$, $K$, $L$ apropiados; (3) citar el teorema de Frankl-Wilson o Sauer-Shelah según corresponda.

Sistemas de conjuntos: perspectiva unificada

Los teoremas de esta lección forman una jerarquía cohesiva basada en una idea central: dimensionar el espacio de funciones relevante y usar independencia lineal.

El esquema general es: (1) Asociar a cada conjunto $A \in \mathcal{F}$ un vector $f_A$ en algún espacio vectorial $V$ sobre un campo $\mathbb{F}$. (2) Demostrar que $\{f_A : A \in \mathcal{F}\}$ es linealmente independiente en $V$ usando las propiedades de intersección. (3) Acotar $\dim V$ para concluir $|\mathcal{F}| \le \dim V$.

La elección del espacio $V$ (polinomios de grado $\le s$ sobre $\mathbb{F}_p$, funciones sobre $\{0,1\}^n$, vectores en $\mathbb{R}^n$) y del campo $\mathbb{F}$ determina la cota obtenida. Frankl-Wilson usa $\mathbb{F}_p$, el Teorema de Fisher usa $\mathbb{R}$, y el Lema de Sauer-Shelah usa una reducción inductiva que no requiere un campo explícito pero sigue el mismo espíritu.

Para la práctica olímpica: el método del rango sobre $\mathbb{F}_2$ es el más accesible y el que más aparece en IMO Shortlist. Frankl-Wilson y Sauer-Shelah son herramientas más pesadas, pero su conocimiento da perspectiva sobre por qué las cotas que aparecen en los enunciados tienen la forma $\binom{n}{\le s}$.