11.6: El Método Probabilístico

Al inicio de este capítulo, presentamos la prueba original de Erdős para el límite inferior para el número de Ramsey\(R(n,n)\) utilizando el conteo. Posteriormente, reelaboramos la prueba en un entorno probabilístico. La historia ha demostrado que esta segunda perspectiva es la correcta. Para ilustrar el poder de este enfoque, presentamos un teorema clásico, que también se debe a Erdős, mostrando que existen gráficas con gran contorno y gran número cromático.

El contorno\(g\) de una gráfica\(G\) es el entero más pequeño para el cual\(G\) contiene un ciclo en\(g\) vértices. El contorno de un bosque se toma como infinito, mientras que el contorno de una gráfica es de tres si y sólo si tiene un triángulo. Se pueden consultar las familias de triángulos libres, gran número cromático, gráficas construidas en el Capítulo 5 y ver que cada una tiene cincha cuatro.

Teorema 11.7. Erdõs

Por cada par\(g,t\) de enteros con\(g \geq 3\), existe una gráfica\(G\) con\(\chi (G)>t\) y la cincha de\(G\) mayor que\(g\).

Prueba

Antes de continuar con los detalles del argumento, hagamos una pausa para obtener la idea general detrás de la prueba. Elegimos enteros\(n\) y\(s\) con\(n>s\), y eventualmente quedará claro qué tan grandes deben ser en términos de\(g\) y\(t\). Entonces consideraremos una gráfica aleatoria sobre conjunto de vértices\(\{1,2,…,n\}\), y al igual que antes, para cada uno\(i\) y\(j\) con\(1≤i<j≤n\), la probabilidad de que el par\(ij\) sea un borde es\(p\), pero ahora\(p\) dependerá de\(n\). Por supuesto, la probabilidad de que cualquier par dado sea un borde es completamente independiente de todos los demás pares.

Nuestro primer objetivo es elegir los valores de\(n, s\) y\(p\) para que con alta probabilidad, una gráfica aleatoria no tenga un conjunto independiente de tamaño\(s\). Se podría pensar como un segundo gol, trataríamos de obtener una gráfica aleatoria sin pequeños ciclos. Pero este objetivo es demasiado restrictivo. En cambio, solo tratamos de obtener una gráfica en la que haya relativamente pocos ciclos pequeños. De hecho, queremos que el número de ciclos pequeños sea menor que\(n/2\). Entonces eliminaremos un vértice de cada ciclo pequeño, dando como resultado una gráfica con al menos\(n/2\) vértices, no teniendo ciclos pequeños y sin conjunto independiente de tamaño\(s\). El número cromático de esta gráfica es al menos\(n/2s\), así que vamos a querer tener la desigualdad\(n>2st\).

Ahora para algunos detalles. Dejar\(X_1\) ser la variable aleatoria que cuenta el número de conjuntos independientes\(s\) -elemento. Entonces

\(E(X_1) = \dbinom{n}{s} (1-p)^{C(s,2)}\)

Ahora queremos\(E(X_1)<1/4\). Desde\(C(n,s)≤n^s=e^{s \ln ⁡n}\) y\((1−p)^{C(s,2)}≤e^{−ps^2/2}\), basta con establecer\(s=2 \ln ⁡n/p\). Por Desigualdad de Markov, la probabilidad que\(X_1\) supera\(1/2≥2E(X_1)\) es menor a 1/2.

Ahora vamos a\(X_2\) contar el número de ciclos en\(G\) de tamaño como máximo\(g\). Entonces

\(E(X_2) \leq \displaystyle \sum_{i=3}^g n(n-1)(n-2) ... (n-i+1)p^i \leq g(pn)^g\).

Ahora, queremos\(E(X_2)≤n/4\), y un cálculo fácil muestra que\(g(np)^g≤n/4\) cuando\(p=n^1/g^{−1}/10\). Nuevamente por Desigualdad de Markov, la probabilidad que\(X_2\) supera\(n/2≥2E(X_2)\) es menor a 1/2.

Concluimos que existe una gráfica\(G\) para la cual\(X_1=0\) y\(X_2≤n/2\). Eliminar un vértice de cada uno de los pequeños ciclos adentro\(G\) y dejar que\(H\) sea la gráfica que quede. Claramente,\(H\) tiene al menos\(n/2\) vértices, ningún ciclo de tamaño como máximo\(g\) y ningún conjunto independiente de tamaño\(s\). Por último, la desigualdad\(n>2st\) requiere\(n^{1/g}/(40 \ln n) > t\).

11.6.1 Ganar la intuición con el método probabilístico

Investigadores experimentados son capaces de simplificar los cálculos en un argumento de este tipo, ya que saben lo que se puede descartar de manera segura y lo que no. Aquí hay un recorrido rápido por los pasos esenciales. Queremos\(E(X_1)\) ser pequeños, así que nos fijamos\(n^se^{−ps^2}=1\) y conseguimos\(s= \ln ⁡n/p\). Queremos que el número de ciclos pequeños sea sobre\(n\) así que establecemos\((gp)^g=n\) y obtengamos\(p=n^1/g^{−1}\). Por último, queremos\(n=st\) lo que requiere\(n^{1/g}=t\). El resto es solo prestar atención a los detalles.