El método de Lovász: lema local y aplicaciones

¿Cuándo falla el método del primer momento?

Sea $\mathcal{A}_1, \mathcal{A}_2, \ldots, \mathcal{A}_m$ una colección de "eventos malos" en un espacio de probabilidad. El método del primer momento estándar dice: si $\sum_i \Pr[\mathcal{A}_i] < 1$, entonces $\Pr[\bigcap_i \overline{\mathcal{A}_i}] > 0$, y existe un punto del espacio donde ningún evento malo ocurre. Esta es la unión acotada o cota de Markov para la unión.

El problema: en muchas aplicaciones combinatorias, $\sum_i \Pr[\mathcal{A}_i] \gg 1$. Por ejemplo, en el problema de 2-colorar un hipergrafo $k$-uniforme con $n$ vértices y $m$ aristas de modo que ninguna arista sea monocromática: el evento malo $\mathcal{A}_e$ (arista $e$ monocromática) tiene $\Pr[\mathcal{A}_e] = 2^{1-k}$. Si $m \ge 2^{k-1}$, la suma de probabilidades ya es $\ge 1$ y la cota de unión no ayuda. Sin embargo, si $m$ es grande pero las aristas se intersectan poco (cada arista comparte vértices con pocas otras), intuitivamente los eventos deberían ser "casi independientes" y debería existir una buena coloración.

El Lema Local de Lovász (Erdős-Lovász, 1975) formaliza esta intuición: si los eventos malos no son "demasiado dependientes" entre sí, la probabilidad de evitarlos todos sigue siendo positiva incluso cuando su suma de probabilidades es grande.

El Lema Local de Lovász: versión simétrica

Consideremos eventos $\mathcal{A}_1, \mathcal{A}_2, \ldots, \mathcal{A}_m$ en un espacio de probabilidad. Decimos que $\mathcal{A}_i$ es mutuamente independiente de un conjunto $S$ de otros eventos si $\Pr[\mathcal{A}_i \mid \bigcap_{j \in T} \overline{\mathcal{A}_j}] = \Pr[\mathcal{A}_i]$ para todo $T \subseteq S$. El grafo de dependencia $G$ tiene vértice $i$ por cada $\mathcal{A}_i$, y arista $\{i,j\}$ si $\mathcal{A}_i$ no es mutuamente independiente de $\{\mathcal{A}_j\}$ (i.e., $\mathcal{A}_i$ y $\mathcal{A}_j$ pueden estar correlacionados).

LLL Versión Simétrica. Si $\Pr[\mathcal{A}_i] \le p$ para todo $i$, y cada $\mathcal{A}_i$ comparte arista en el grafo de dependencia con a lo sumo $d$ otros eventos, y si

$p(d+1) \le \frac{1}{e}$

entonces $\Pr\left[\bigcap_{i=1}^{m} \overline{\mathcal{A}_i}\right] > 0$. En particular, existe un punto del espacio donde ningún evento malo ocurre.

La constante $1/e$ es óptima: para $p(d+1) > 1/e$ hay ejemplos donde la probabilidad es cero. La prueba original de Erdős-Lovász usa inducción; la prueba moderna de Shearer es más limpia y da condiciones más precisas.

El LLL versión asimétrica y la prueba por el argumento de Shearer

LLL Versión Asimétrica (Lovász, 1977). Sea $G = (V, E)$ el grafo de dependencia. Existen valores $x_i \in (0,1)$ tales que $\Pr[\mathcal{A}_i] \le x_i \prod_{\{i,j\} \in E} (1-x_j)$ para todo $i$. Entonces:

$\Pr\left[\bigcap_{i=1}^{m} \overline{\mathcal{A}_i}\right] \ge \prod_{i=1}^{m}(1-x_i) > 0$.

La versión asimétrica es más fuerte y flexible: permite que los eventos tengan distintas probabilidades y distintos grados en el grafo de dependencia. La condición $p(d+1) \le 1/e$ de la versión simétrica se obtiene tomando $x_i = 1/(d+1)$ uniformemente.

Prueba de la versión asimétrica. Se demuestra por inducción sobre el número de eventos $m$, usando el siguiente lema auxiliar: si las $x_i$ satisfacen la condición, entonces para todo $S \subseteq [m]$ con $i \notin S$, $\Pr[\mathcal{A}_i \mid \bigcap_{j \in S} \overline{\mathcal{A}_j}] \le x_i$. La inducción sobre el tamaño de $S$ y la descomposición $S = S_1 \cup S_2$ donde $S_1$ son los vecinos de $i$ en $G$ y $S_2$ el resto (de los que $\mathcal{A}_i$ es independiente) completan la prueba.

Aplicación 1: 2-coloración de hipergrafos uniformes

Teorema. Si $H$ es un hipergrafo $k$-uniforme ($k \ge 3$) donde cada arista intersecta a lo sumo otras $d$ aristas, y si $d \le 2^{k-2}/e - 1$, entonces $H$ admite una 2-coloración propia (sin aristas monocromáticas).

Prueba por LLL. Coloreamos cada vértice independientemente de rojo/azul con probabilidad $1/2$. El evento malo $\mathcal{A}_e$ es "la arista $e$ es monocromática", con $\Pr[\mathcal{A}_e] = 2^{1-k}$. El grafo de dependencia: $\mathcal{A}_e$ y $\mathcal{A}_{e'}$ comparten arista si $e$ y $e'$ tienen un vértice en común. Como cada arista tiene $k$ vértices y cada vértice intersecta a lo sumo $d/(k)$ aristas (aproximadamente), el grado en el grafo de dependencia es a lo sumo $d$. La versión simétrica del LLL requiere $2^{1-k} \cdot (d+1) \le 1/e$, es decir $d+1 \le 2^{k-1}/e$, lo que da $d \le 2^{k-2}/e - 1$ (estimación burda). Para $k=3$: $d \le 2/e - 1 \approx 0.35$, lo que significa $d = 0$: aristas disjuntas. Para $k=10$: $d \le 512/e - 1 \approx 187$.

Este resultado es notable: el hipergrafo puede ser mucho más complejo que uno donde la cota de unión funciona (que requeriría $m < 2^{k-1}$, es decir que el número total de aristas sea pequeño), siempre que la dependencia local sea limitada.

Aplicación 2: El problema del k-SAT

Una fórmula en forma normal conjuntiva (FNC) tiene $m$ cláusulas, cada una siendo la disyunción de exactamente $k$ literales. El **$k$-SAT** pregunta si existe una asignación de valores de verdad a las variables que satisfaga todas las cláusulas.

Teorema. Toda fórmula $k$-SAT donde cada variable aparece en a lo sumo $2^k/(ek)$ cláusulas es satisfacible.

Prueba por LLL. Asignamos a cada variable independientemente el valor Verdad o Falso con probabilidad $1/2$. El evento malo $\mathcal{A}_c$ es "la cláusula $c$ es falsa". Como $c$ tiene $k$ literales distintos, $\Pr[\mathcal{A}_c] = 2^{-k}$. El grafo de dependencia: $\mathcal{A}_c$ y $\mathcal{A}_{c'}$ comparten arista si $c$ y $c'$ comparten al menos una variable. Como $c$ tiene $k$ variables y cada variable aparece en a lo sumo $2^k/(ek)$ cláusulas, el grado de $\mathcal{A}_c$ en el grafo de dependencia es a lo sumo $k \cdot (2^k/(ek) - 1) \le 2^k/e - 1$. La condición del LLL simétrico: $2^{-k} \cdot (2^k/e) = 1/e$. La condición es exactamente $p(d+1) = 1/e$, que satisface la hipótesis del LLL (con $\le$ en lugar de $<$, pero la versión estricta aplica con una ligera modificación de la constante). Por tanto existe una asignación que satisface todas las cláusulas.

Este resultado tiene implicaciones en complejidad computacional: sugiere que el $k$-SAT es "fácil" (siempre satisfacible) cuando la densidad de cláusulas por variable es baja.

El algoritmo de Moser-Tardos: haciendo constructivo el LLL

Un defecto del LLL original es que es puramente existencial: muestra que existe una asignación buena pero no dice cómo encontrarla eficientemente. En 2010, Robin Moser y Gábor Tardos (estudiante de doctorado en ese entonces) demostraron un resultado revolucionario: el LLL es constructivo en tiempo polinomial bajo las mismas condiciones.

El algoritmo de Moser-Tardos es sorprendentemente simple: (1) Asignar valores aleatorios a todas las variables. (2) Mientras exista un evento malo que ocurra: elegir uno cualquiera $\mathcal{A}_i$ y re-asignar aleatoriamente las variables que aparecen en $\mathcal{A}_i$. (3) Repetir.

La prueba de que este algoritmo termina en tiempo esperado polinomial (de hecho, proporcional al número de variables) bajo las condiciones del LLL asimétrico usa un argumento entrópico elegante, conectando el tiempo de ejecución con la información de Kolmogorov.

Para olimpiadas, el LLL constructivo no es relevante directamente, pero la intuición de "resampling local" —corregir violaciones localmente sin destruir lo ya arreglado— es una heurística poderosa de diseño de argumentos.