La idea central: existencia sin construcción explícita

La revolución de Erdős: objetos que existen pero nadie ha construido

En 1947, Paul Erdős publicó una prueba de dos páginas que demostró $R(k,k) > 2^{k/2}$ —estableciendo que los números de Ramsey crecen al menos exponencialmente. La prueba no construía ningún grafo específico. En cambio, Erdős argumentó: si coloreo al azar las aristas de $K_n$ con dos colores, la probabilidad de que exista un clique monocromático de tamaño $k$ es menor que 1, luego existe una 2-coloración sin clique monocromático de tamaño $k$.

Este argumento fundó el método probabilístico: una técnica de existencia pura. Su poder reside en la asimetría: demostrar que un objeto existe es mucho más fácil que construirlo explícitamente. Hoy, décadas después, muchos de los grafos cuya existencia Erdős probó así todavía no se han construido explícitamente.

El principio fundamental es engañosamente simple. Sea $\Omega$ un espacio de probabilidad sobre objetos combinatorios (grafos, coloraciones, permutaciones, conjuntos). Sea $\mathcal{A}$ la propiedad que queremos que el objeto satisfaga. Si $\Pr[\mathcal{A}] > 0$, entonces existe un objeto en $\Omega$ que satisface $\mathcal{A}$. El paso clave es elegir bien el espacio de probabilidad $\Omega$.

En la práctica, dos herramientas dominan: (1) calcular $\Pr[\mathcal{A}]$ directamente y mostrar que es positiva, y (2) usar la esperanza: si $X$ es una variable aleatoria con $\mathbb{E}[X] > c$, entonces con probabilidad positiva $X > c$, luego existe un objeto donde $X > c$. El segundo método es más flexible y da lugar a técnicas como la alteración.

El argumento original de Erdős: cotas para $R(k,k)$

Sea $n$ un entero que fijaremos después. Coloreamos cada arista de $K_n$ independientemente de rojo o azul con probabilidad $1/2$ cada una. Sea $S$ un conjunto de $k$ vértices. La probabilidad de que $S$ induzca un clique monocromático (todos rojo o todos azul) es $2 \cdot (1/2)^{\binom{k}{2}} = 2^{1-\binom{k}{2}}$.

Sea $X$ el número de cliques monocromáticos de tamaño $k$. Por linealidad de la esperanza:

$\mathbb{E}[X] = \binom{n}{k} \cdot 2^{1-\binom{k}{2}}$.

Si $\mathbb{E}[X] < 1$, entonces $\Pr[X \ge 1] \le \mathbb{E}[X] < 1$, lo que implica $\Pr[X = 0] > 0$. Luego existe una 2-coloración de $K_n$ sin clique monocromático de tamaño $k$, y esto prueba $R(k,k) > n$.

La condición $\mathbb{E}[X] < 1$ se satisface cuando $\binom{n}{k} < 2^{\binom{k}{2}-1}$. Usando la cota $\binom{n}{k} \le n^k / k!$ y la estimación de Stirling $k! \ge (k/e)^k$, si $n = \lfloor 2^{k/2} \rfloor$ se verifica fácilmente que la condición se cumple para $k$ suficientemente grande. Esto establece:

El método de la alteración

A veces la probabilidad de que el objeto aleatorio satisfaga la propiedad es cero, pero podemos alterar el objeto para repararlo. La idea es: generar un objeto aleatorio, identificar los "defectos", y eliminarlos con un coste controlado.

Ejemplo: grafos de cintura grande y número cromático grande. Para todo $k \ge 1$, existe un grafo con número cromático $\chi(G) \ge k$ y cintura $g(G) \ge k$ (sin ciclos cortos). Este teorema de Erdős (1959) es uno de los resultados más sorprendentes de la combinatoria: la intuición dice que la presencia de triángulos (y ciclos cortos) es lo que "fuerza" colores, pero resulta que se puede tener un número cromático arbitrariamente grande sin ningún ciclo corto.

La prueba usa el método de la alteración. Tomamos $G = G(n,p)$ con $p = n^{1/k - 1}$. Con la elección correcta de $n$: (i) el número esperado de ciclos de longitud $< k$ es $o(n)$, y (ii) el número de independencia satisface $\alpha(G) < n/2k$ con alta probabilidad. Luego eliminamos un vértice de cada ciclo corto: perdemos $o(n)$ vértices. El grafo resultante $G'$ tiene cintura $\ge k$. Además, como $\alpha(G') \le \alpha(G) < n/2k$ y el número de vértices de $G'$ es $\ge n/2$ (solo se eliminaron $o(n)$ vértices), el número cromático de $G'$ satisface $\chi(G') \ge |V(G')|/\alpha(G') > k$.

El modelo $G(n,p)$: grafos de Erdős-Rényi

El espacio probabilístico más utilizado en combinatoria es el modelo $G(n,p)$: el grafo aleatorio en $n$ vértices donde cada una de las $\binom{n}{2}$ aristas se incluye independientemente con probabilidad $p$.

Propiedades clave de $G(n,p)$: (1) El grado esperado de cada vértice es $(n-1)p \approx np$ para $p$ pequeño. (2) Si $p = c/n$ con $c < 1$, la componente conexa más grande tiene $O(\log n)$ vértices con alta probabilidad (w.a.p.). Si $c > 1$, existe una única componente gigante de tamaño $\Theta(n)$ w.a.p. — este es el umbral de conectividad, un fenómeno de umbral brusco típico en grafos aleatorios. (3) La distribución del número de triángulos es aproximadamente Poisson con media $\binom{n}{3}p^3$ cuando $np^3 \to 0$.

El umbral para la propiedad $\mathcal{P}$ es el valor $p^*(n)$ tal que si $p \gg p^*$ entonces $G(n,p)$ satisface $\mathcal{P}$ w.a.p., y si $p \ll p^*$ no la satisface w.a.p. Este concepto de umbral, profundamente desarrollado por Bollobás y otros, es fundamental en la combinatoria probabilística moderna.

En olimpiadas, $G(n,p)$ aparece raramente de forma explícita, pero el pensamiento "¿qué pasa si elijo los objetos aleatoriamente?" es exactamente el motor del método probabilístico. Siempre que busques demostrar existencia en combinatoria sin construir explícitamente, pregúntate: ¿cuál sería el espacio de probabilidad natural? ¿qué distribución garantiza que la propiedad se cumpla con probabilidad positiva?

Técnica: el método del primer momento

El método del primer momento (o método de la esperanza) es la herramienta más básica del método probabilístico:

Lema. Para cualquier variable aleatoria $X \ge 0$ entero-valorada: (i) $\Pr[X > 0] \le \mathbb{E}[X]$. (ii) Si $\mathbb{E}[X] > 0$ entonces $\Pr[X > 0] > 0$. (iii) $\Pr[X \ge \mathbb{E}[X]] > 0$ (luego existe un resultado donde $X \ge \mathbb{E}[X]$).

La variante (iii) dice: si $\mathbb{E}[X] = \mu$, entonces algún resultado en el espacio tiene $X \ge \mu$. Esto es útil para demostrar la existencia de configuraciones con muchas instancias de una propiedad.

Aplicación en IMO Shortlist C6, 2011. En un torneo (grafo dirigido completo) con $n$ vértices, se define $f(T)$ como el número de pares ordenados $(a,b)$ con $a \to b$ y $b$ alcanzable desde $a$ en exactamente 2 pasos. Prueba que existe un torneo con $f(T) \ge n(n-1)(n-3)/8$ cuando $n$ es impar. La prueba usa que el torneo aleatorio uniforme tiene esta esperanza exacta, calculada por linealidad.

La señal olímpica del método probabilístico

En una olimpiada, la señal de que se pide el método probabilístico es típicamente: "Demuestra que existe una $[coloración / selección / orientación / función]$ con la propiedad $\mathcal{P}$" o "Demuestra que en todo $[objeto]$ de tamaño $n$ existe un sub-$[objeto]$ de tamaño $f(n)$".

El diagrama de ataque es: (1) Elegir el espacio probabilístico correcto (lo más natural posible). (2) Definir la variable aleatoria $X$ que cuenta las "violaciones" de $\mathcal{P}$ o las "instancias" de $\mathcal{P}$. (3) Calcular $\mathbb{E}[X]$ por linealidad. (4) Concluir existencia: si $X$ cuenta violaciones y $\mathbb{E}[X] < 1$, existe un objeto con $X = 0$; si $X$ cuenta instancias, existe un objeto con $X \ge \mathbb{E}[X]$.

En la lección 3.2 veremos por qué la linealidad de la esperanza — el hecho de que $\mathbb{E}[X_1 + X_2] = \mathbb{E}[X_1] + \mathbb{E}[X_2]$ incluso cuando $X_1, X_2$ no son independientes — es el corazón computacional del método. Esta propiedad, que parece trivial, tiene consecuencias combinatorias profundísimas.