Simulacro 3: problemas C4–C7 tipo ISL

Instrucciones del simulacro avanzado

Los siguientes dos problemas son de dificultad comparable a C4–C7 del Shortlist IMO: problemas que raramente aparecen en el examen final del IMO, pero que forman el núcleo del trabajo de los líderes del equipo y de los estudiantes que aspiran a medalla de oro por amplio margen. El tiempo sugerido en competencia sería 4–6 horas por problema. Estudia las soluciones con atención a cada paso: cada línea importa.

Problema 7 (C5-nivel): Lista-coloración y LLL

Enunciado. Sea $G$ un grafo con grado máximo $\Delta$. Demuestra que $G$ es $(\Delta + 1)$-lista-coloreable: para cualquier asignación de listas $L(v)$ con $|L(v)| \ge \Delta + 1$ para cada vértice $v$, existe una coloración propia de $G$ donde cada vértice $v$ recibe un color de $L(v)$.

Solución (argumento greedy, sin probabilidad). Ordenamos los vértices $v_1, v_2, \ldots, v_n$ en cualquier orden. Coloreamos $v_1$ con cualquier color de $L(v_1)$. Para colorear $v_i$, sus vecinos ya coloreados son a lo sumo $i-1 \le \Delta$ vértices (pero en realidad, a lo sumo $\Delta$ vecinos en total). Los colores usados por los vecinos ya coloreados de $v_i$ "bloquean" a lo sumo $\Delta$ colores de $L(v_i)$. Como $|L(v_i)| \ge \Delta+1$, siempre queda al menos un color disponible en $L(v_i)$. ✓

**Versión difícil: el número de lista-coloración $\text{ch}(G) \le \Delta$ para grafos bipartitos.** Esta es la Conjetura de Galvin-Dinitz (1994, demostrada por Galvin): si $G$ es bipartito con grado máximo $\Delta$, entonces $\text{ch}(G) = \chi(G)$, es decir, las listas de tamaño $\chi(G) =$ número cromático son suficientes. La demostración usa el Lovász Local Lemma versión asimétrica.

Argumento probabilístico con LLL. Para cada vértice $v$, elegimos un color $c(v) \in L(v)$ uniformemente al azar (independientemente). El "evento malo" $A_{\{u,v\}}$ es que $c(u) = c(v)$ para la arista $\{u,v\}$. Tenemos $\Pr[A_{\{u,v\}}] \le \frac{1}{|L(u)|} + \frac{1}{|L(v)|} \le \frac{2}{\Delta+1}$ (en realidad, $\Pr[A_{\{u,v\}}] = \sum_c \Pr[c(u)=c]\Pr[c(v)=c] \le \sum_c \frac{1}{|L(u)| \cdot |L(v)|} \le \frac{1}{\Delta+1}$). Cada evento $A_e$ depende de a lo sumo $2(\Delta-1)$ otros eventos (las otras aristas incidentes en los extremos de $e$). El LLL garantiza $\Pr[\bigcap_e \overline{A_e}] > 0$ si $e \cdot \frac{1}{\Delta+1} \cdot (2\Delta - 1) \le 1$, que se satisface para $\Delta$ suficientemente grande. ✓

Problema 8 (C6-nivel): Número de Ramsey y el método de segundo momento

Enunciado. Demuestra que $R(k,k) > 2^{k/2}$ para todo $k \ge 3$. Es decir, existe una 2-coloración de $K_n$ con $n = 2^{k/2}$ sin triángulo monocrómático de tamaño $k$.

Solución (Erdős 1947, argumento probabilístico). Sea $n = \lfloor 2^{k/2} \rfloor$. Coloreamos cada arista de $K_n$ roja o azul con probabilidad $1/2$ cada una, de manera independiente. Para un subconjunto $S \subseteq V$ con $|S| = k$, sea $A_S$ el evento "el subgrafo inducido en $S$ es monocrómático" (todas las $\binom{k}{2}$ aristas del mismo color). Entonces:

$\Pr[A_S] = 2 \cdot (1/2)^{\binom{k}{2}} = 2^{1 - \binom{k}{2}}$.

El número de subconjuntos $S$ de tamaño $k$ es $\binom{n}{k}$. Por la unión:

$\Pr[\text{existe } S \text{ monocrómático}] \le \binom{n}{k} \cdot 2^{1-\binom{k}{2}}$.

Usamos $\binom{n}{k} \le \frac{n^k}{k!}$. Queremos que esta probabilidad sea menor que $1$:

$\frac{n^k}{k!} \cdot 2^{1-\binom{k}{2}} < 1 \iff n^k < k! \cdot 2^{\binom{k}{2}-1}$.

Como $\binom{k}{2} - 1 = \frac{k(k-1)}{2} - 1 > \frac{k}{2} \cdot (k-1) - 1$, para $n = 2^{k/2}$ tenemos $n^k = 2^{k^2/2}$ y $2^{\binom{k}{2}-1} = 2^{k(k-1)/2 - 1}$. Verificamos: $2^{k^2/2} < k! \cdot 2^{k(k-1)/2 - 1} \iff 2^{k/2 + 1} < k!$, que es verdad para $k \ge 3$.

Por lo tanto, con probabilidad positiva, ningún subconjunto de $k$ vértices es monocrómático. Existe una coloración sin $K_k$ monocrómático en $K_n$, lo que implica $R(k,k) > n = 2^{k/2}$. ✓