El método del rango en problemas olímpicos

El patrón estándar: de la condición combinatoria al rango

El método del rango en olimpiadas sigue un guión casi invariante. Reconocerlo es la mitad de la solución:

Paso 1: Traducción. El enunciado dice algo como "existe una familia de $m$ conjuntos con la propiedad $\mathcal{P}$" o "si la familia $\mathcal{F}$ satisface $\mathcal{P}$ entonces $|\mathcal{F}| \le f(n)$". La propiedad $\mathcal{P}$ típicamente involucra intersecciones, cardinalidades, o paridades.

Paso 2: Construcción de la matriz. Definimos la matriz de incidencia $M \in \{0,1\}^{|\mathcal{F}| \times n}$ (o, si el problema es sobre grafos, la matriz de adyacencia $A$, o la matriz de Laplace $L = D - A$). Si el problema es sobre mod $p$, trabajamos sobre $\mathbb{F}_p$.

**Paso 3: Cálculo de $MM^T$.** Usando la propiedad $\mathcal{P}$, calculamos las entradas de $MM^T$: $(MM^T)_{ij} = |A_i \cap A_j|$. Típicamente, la diagonal es constante (o acotada) y los elementos fuera de la diagonal son constantes (o todos pertenecen a un conjunto pequeño de valores). Esto da que $MM^T$ tiene una forma especial (matriz circulante, o $\lambda I + \mu J$, etc.).

**Paso 4: Rango de $MM^T$.** Calculamos o acotamos el rango de $MM^T$. Si $MM^T$ es invertible, su rango es $|\mathcal{F}|$. Como $\operatorname{rk}(MM^T) \le \operatorname{rk}(M) \le n$, concluimos $|\mathcal{F}| \le n$.

Ejemplo resuelto: familias con intersección uniforme (sobre $\mathbb{R}$)

Problema. Sea $\mathcal{F} = \{A_1,\ldots,A_m\}$ una familia de subconjuntos de $[n]$, todos de tamaño $k$, tales que $|A_i \cap A_j| = \lambda$ para todo $i \ne j$, con $k \ne \lambda$. Prueba que $m \le n$.

Solución. Construimos la matriz de incidencia $M \in \{0,1\}^{m\times n}$. Calculamos $MM^T$: $(MM^T)_{ii} = |A_i| = k$ y $(MM^T)_{ij} = |A_i \cap A_j| = \lambda$ para $i \ne j$. Así $MM^T = (k-\lambda)I_m + \lambda J_m$.

Los valores propios de $(k-\lambda)I_m + \lambda J_m$ son: $k - \lambda + \lambda m = k + \lambda(m-1)$ con vector propio $(1,1,\ldots,1)$, y $k - \lambda$ con multiplicidad $m-1$ (vectores propios ortogonales a $\mathbf{1}$). Como $k \ne \lambda$, ambos valores propios son no nulos (el segundo es $k-\lambda \ne 0$, y el primero es $k+\lambda(m-1) > 0$ si $k > 0$). Luego $\operatorname{rk}(MM^T) = m$.

Como $\operatorname{rk}(MM^T) \le \operatorname{rk}(M) \le n$ (la matriz $M$ tiene $n$ columnas), concluimos $m \le n$. $\square$

Ejemplo resuelto: familias con intersección mod 2 (sobre $\mathbb{F}_2$)

Problema. Sea $\mathcal{F} = \{A_1,\ldots,A_m\}$ una familia de subconjuntos de $[n]$ tal que: $|A_i|$ es impar para todo $i$, y $|A_i \cap A_j|$ es par para todo $i \ne j$. Prueba que $m \le n$.

**Solución sobre $\mathbb{F}_2$.** Trabajamos con la matriz de incidencia $M \in \mathbb{F}_2^{m \times n}$. La matriz de Gram $G = MM^T$ sobre $\mathbb{F}_2$ tiene $G_{ii} = |A_i| \bmod 2 = 1$ y $G_{ij} = |A_i \cap A_j| \bmod 2 = 0$ para $i \ne j$. Luego $G = I_m$ sobre $\mathbb{F}_2$.

$G = I_m$ tiene rango $m$ sobre $\mathbb{F}_2$. Como $\operatorname{rk}_{\mathbb{F}_2}(G) = \operatorname{rk}_{\mathbb{F}_2}(MM^T) \le \operatorname{rk}_{\mathbb{F}_2}(M) \le n$, concluimos $m \le n$. $\square$

Nótese que en $\mathbb{F}_2$ no usamos nada sobre valores propios; el argumento es puramente sobre rango.

El Método del Rango en grafos: coloraciones y espectro

En problemas de grafos, el rango de la matriz de adyacencia $A$ sobre distintos campos da información espectral. El Teorema de Hoffman conecta el espectro con el número cromático: si $A$ tiene valor propio mínimo $\lambda_{\min} < 0$, entonces $\chi(G) \ge 1 - \lambda_{\max}/\lambda_{\min}$.

Sobre $\mathbb{F}_2$, la cota de rango de $A$ da información sobre la paridad de ciclos. El Teorema de König sobre grafos bipartitos puede verse como: $G$ es bipartito $\Leftrightarrow$ $A(G)$ sobre $\mathbb{F}_2$ tiene rango $\le n/2$ (las filas de una parte son combinación lineal de las de la otra) — esto no es exactamente correcto pero captura el espíritu.

Para IMO Shortlist C5-C6 con grafos, la estrategia es: (1) asociar vectores en $\mathbb{F}_2^n$ (o $\mathbb{R}^n$) a los objetos del problema; (2) usar las condiciones del problema para establecer relaciones de ortogonalidad o dependencia; (3) concluir via rango.

El número de Ramsey y el método espectral. La cota $R(k,k) \le 4^k$ puede mejorarse con el método espectral: si $G$ tiene densidad de aristas $\ge 1/2$ y no tiene clique de tamaño $k$, la cota sobre el espectro de $A(G)$ limita el número de vértices. Esto da $R(k,k) \le (1+o(1)) \cdot k \cdot 2^k / \log k$, una mejora sobre la cota probabilística pero lejos de la cota inferior.

Síntesis: cuándo usar qué método algebraico

Al final del Capítulo 4, el estudiante debe tener un mapa mental claro de cuándo usar cada herramienta:

Método polinomial (Nullstellensatz Combinatorio): cuando el problema pide existencia de un punto en $S_1 \times \cdots \times S_n$ con cierta propiedad, y hay un polinomio natural que codifica la propiedad. Señales: el enunciado involucra un primo $p$ y la cota tiene la forma "$n > \sum \deg f_i$" o "$|S_i| = k$".

**Rango sobre $\mathbb{R}$ (Teorema de Fisher, Gram):** cuando todos los conjuntos tienen el mismo tamaño y las intersecciones son iguales (o toman pocos valores). Señales: "familia con intersección constante", "diseño de bloques", condiciones simétricas sobre intersecciones.

**Rango sobre $\mathbb{F}_2$ (Lema de la Dimensión):** cuando las condiciones involucran paridades — tamaños impares, intersecciones pares, diferencias simétricas. Señales: "$|A|$ impar", "$|A \cap B|$ par", estructuras XOR.

Frankl-Wilson / Sauer-Shelah: cuando la cota esperada es $\binom{n}{\le s}$ y hay condiciones de intersección modulares con $s+1$ valores posibles. Señales: cota polinomial en $n$ con exponente $s$ fijo.

Dominar estos cuatro marcos y reconocer cuál aplica en 5 minutos de lectura del enunciado es una habilidad que distingue a los candidatos a la selección olímpica.