11.4: Aplicando la probabilidad a la teoría de Ramsey
- Page ID
- 118367
El siguiente teorema, debido a P. Erdős, es un verdadero clásico, y se presenta aquí de una manera fiel a cómo se publicó por primera vez. Como veremos más adelante, posteriormente fue refundido —pero eso es sacar el carro delante del caballo.
Si\(n\) es un entero positivo. Entonces
\(R(n,n) \geq \dfrac{n}{e \sqrt{2}} 2^{\frac{1}{2}n}\)
- Prueba
-
Dejar\(t\) ser un entero con\(t>n\) y considerar el conjunto\(\mathcal{F}\) de todas las gráficas etiquetadas con conjunto de vértices\(\{1,2,…,t\}\). Claramente, hay\(2^{C(t,2)}\) gráficas en esta familia. Let\(\mathcal{F_1}\) denotar la subfamilia que consiste en aquellas gráficas que contienen un subgrafo completo de tamaño\(n\). Es fácil ver que
\(|\mathcal{F_1}| \leq \dbinom{t}{n} 2^{n(t-n)}2^{C(t-n,2)}\).
Del mismo modo,\(\mathcal{F_2}\) denotemos la subfamilia que consiste en aquellas gráficas que contienen un conjunto independiente de tamaño\(n\). De ello se deduce que
\(|\mathcal{F_2}| \leq \dbinom{t}{n} 2^{n(t-n)}2^{C(t-n,2)}\).
Queremos tomar el entero\(t\) tan grande como podamos sin dejar de garantizar eso\(|\mathcal{F_1}|+|\mathcal{F_2}| \leq |\mathcal{F}|\). Esto implicará que existe una gráfica\(G\) en la\(\mathcal{F}\) que no contenga una subgrafía completa de tamaño\(n\) o un conjunto independiente de tamaños\(n\). Por lo tanto, considere la siguiente desigualdad:
\[2 \dbinom{t}{n} 2^{n(t-n)}2^{C(t-n,2)} < 2^{C(t,2)} \label{11.4.1} \]
Ahora nos preguntamos ¿qué tan grande no puede ser sin violar la desigualdad (\(\ref{11.4.1}\))? Para responder a esto, utilizamos la desigualdad trivial\( \binom{t}{n} \leq t^n/n!\) y el uso de la aproximación de Stirling para\(n!\). Después de un poco de álgebra y tomando la\(n^{th}\) raíz de ambos lados, vemos que solo necesitamos garantizar que
\(t \leq \dfrac{n}{e \sqrt{n}} 2^{\frac{1}{2}n}\)
Ahora echemos un segundo vistazo a la prueba del Teorema 11.4. Consideramos un espacio de probabilidad\((S,P)\) donde los resultados son gráficas con conjunto de vértices\(\{1,2,…,t\}\). Para cada uno\(i\) y\(j\) con\(1 \leq i<j \leq t\), edge\(ij\) está presente en la gráfica con probabilidad 1/2. Además, los eventos para distintos pares son independientes.
Let\(X_1\) denotar la variable aleatoria que cuenta el número de subconjuntos\(n\) -elemento de\(\{1,2,…,t\}\) para los cuales todos los\(\binom{n}{2}\) pares son bordes en la gráfica. Del mismo modo,\(X_2\) es la variable aleatoria la que cuenta el número de subconjuntos independientes\(n\) -elemento de\(\{1,2,…,t\}\). A continuación, establecer\(X=X_1+X_2\).
Por linealidad de expectativa,\(E(X)=E(X_1)+E(X_2)\) mientras
\(E(X_1) = E(X_2) = \dbinom{t}{n} \dfrac{1}{2^{C(n,2)}}\).
Si\(E(X)<1\), entonces debe existir una gráfica con vértice establecido\(\{1,2,…,t\}\) sin una\(K_n\) o una\(I_n\). Y la cuestión de qué tan grande\(t\) puede ser manteniendo\(E(X)<1\) lleva a exactamente el mismo cálculo que teníamos antes.
Después de más de cincuenta años y del esfuerzo de muchos investigadores muy brillantes, solo se han realizado mejoras marginales en los límites\(R(n,n)\) del Teorema 11.2 y el Teorema 11.4. En particular, nadie puede establecer si hay alguna constante\(c<2\) y un entero\(n_0\) para que\(R(n,n)<2^{cn}\) cuando\(n>n_0\). De igual manera, nadie ha podido responder si hay alguna constante\(d>1/2\) y un entero\(n_1\) para que\(R(n,n)>2^{dn}\) cuando\(n>n_1\). Sin duda te daríamos una\(A\) para este curso si lograras hacer alguna de las dos.
Carlos dijo que había estado tratando de demostrar un buen límite inferior al\(R(n,n)\) usar solo métodos constructivos, es decir, no se permiten técnicas aleatorias. Pero estaba teniendo problemas. Todo lo que intentó parecía sólo para demostrar que\(R(n,n) \geq n^c\) dónde\(c\) está una constante. Eso parece tan débil en comparación con el límite exponencial que el método probabilístico da fácilmente. Por lo general Alice no era muy comprensiva con las quejas de los demás y desde luego no de Carlos, que parecía estar siempre al frente. Pero esta vez, Alice le dijo a Carlos y de una manera que todos pudieron escuchar “A lo mejor no deberías ser tan duro contigo mismo. Leí un artículo en la web que nadie ha podido demostrar que hay una constante\(c>1\) y un entero\(n_0\) para que\(R(n,n)>c^n\) cuando\(n>n_0\), siempre que solo se permitan métodos constructivos. Y tal vez, solo tal vez, no es tan malo decir que no puedes hacer algo que muchos otros famosos parecen incapaces de hacer”. Bob vio un nuevo lado de Alice y esto tampoco fue del todo malo.