Método probabilístico

Supongamos que tenemos un grafo completo en${\displaystyle n}$vértices . Deseamos mostrar (para valores suficientemente pequeños de${\displaystyle n}$) que es posible colorear los bordes del grafo en dos colores (por ejemplo, rojo y azul) de manera que no haya ningún subgrafo completo en${\displaystyle r}$vértices que son monocromáticos (cada arista coloreada del mismo color).

Para ello, coloreamos el grafo aleatoriamente. Coloreamos cada arista de forma independiente con probabilidad${\displaystyle 1/2}$de ser rojo y${\displaystyle 1/2}$de ser azul. Calculamos el número esperado de subgrafos monocromáticos en${\displaystyle r}$vértices de la siguiente manera:

Para cualquier conjunto${\displaystyle S_{r}}$de${\displaystyle r}$vértices de nuestro grafo, definen la variable${\displaystyle X(S_{r})}$ser${\displaystyle 1}$si cada borde entre los${\displaystyle r}$los vértices son del mismo color y${\displaystyle 0}$de lo contrario. Tenga en cuenta que el número de monocromáticos${\displaystyle r}$-subgrafos es la suma de${\displaystyle X(S_{r})}$sobre todos los subconjuntos posibles${\displaystyle S_{r}}$Para cualquier conjunto individual${\displaystyle S_{r}^{i}}$, el valor esperado de${\displaystyle X(S_{r}^{i})}$es simplemente la probabilidad de que todos los${\displaystyle C(r,2)}$bordes en${\displaystyle S_{r}^{i}}$son del mismo color:

${\displaystyle E[X(S_{r}^{i})]=2\cdot 2^{-{r \choose 2}}}$

(el factor de${\displaystyle 2}$(Esto se debe a que hay dos colores posibles).

Esto es cierto para cualquiera de los${\displaystyle C(n,r)}$posibles subconjuntos que podríamos haber elegido, es decir${\displaystyle i}$abarca desde${\displaystyle 1}$a${\displaystyle C(n,r)}$. Entonces tenemos que la suma de${\displaystyle E[X(S_{r}^{i})]}$en general${\displaystyle S_{r}^{i}}$es

${\displaystyle \sum _{i=1}^{C(n,r)}E[X(S_{r}^{i})]={n \choose r}2^{1-{r \choose 2}}.}$

La suma de las expectativas es la esperanza de la suma ( independientemente de si las variables son independientes ), por lo que la esperanza de la suma (el número esperado de todos los monocromáticos)${\displaystyle r}$-subgrafos) es

${\displaystyle E[X(S_{r})]={n \choose r}2^{1-{r \choose 2}}.}$

Considere qué sucede si este valor es menor que${\displaystyle 1}$. Dado que el número esperado de monocromáticos${\displaystyle r}$-subgrafos es estrictamente menor que${\displaystyle 1}$, existe una coloración que satisface la condición de que el número de monocromáticos${\displaystyle r}$-subgrafos es estrictamente menor que${\displaystyle 1}$. El número de monocromáticos${\displaystyle r}$-subgrafos en esta coloración aleatoria es un entero no negativo , por lo tanto debe ser${\displaystyle 0}$(${\displaystyle 0}$es el único entero no negativo menor que${\displaystyle 1}$). De ello se deduce que si

${\displaystyle E[X(S_{r})]={n \choose r}2^{1-{r \choose 2}}<1}$

(lo cual se cumple, por ejemplo, para${\displaystyle n=5}$y${\displaystyle r=4}$), debe existir una coloración en la que no haya monocromáticos${\displaystyle r}$-subgrafos. ^{[ a ]}

Por definición del número de Ramsey , esto implica que${\displaystyle R(r,r)}$debe ser más grande que${\displaystyle n}$. En particular,${\displaystyle R(r,r)}$debe crecer al menos exponencialmente con${\displaystyle r}$.

Una debilidad de este argumento es que es completamente contraproducente . El problema de encontrar dicha coloración lleva abierto más de 50 años.

Un artículo de Erdős de 1959 (véase la referencia citada más adelante) abordó el siguiente problema en la teoría de grafos : dados enteros positivos g y k , ¿existe un grafo G que contenga solo ciclos de longitud al menos g , tal que el número cromático de G sea al menos k ?

Se puede demostrar que existe tal grafo para cualquier g y k , y la demostración es razonablemente sencilla. Sea n muy grande y consideremos un grafo aleatorio G con n vértices, donde cada arista en G existe con probabilidad p = n ^{1/ g −1} . Demostramos que, con probabilidad positiva, G satisface las dos propiedades siguientes:

Propiedad 1. G contiene como máximo n /2 ciclos de longitud menor que g .

Demostración. Sea X el número de ciclos de longitud menor que g . El número de ciclos de longitud i en el grafo completo de n vértices es

${\displaystyle {\frac {n!}{2\cdot i\cdot (ni)!}}\leq {\frac {n^{i}}{2}}}$

y cada uno de ellos está presente en G con probabilidad p ⁱ . Por lo tanto, por la desigualdad de Markov tenemos

${\displaystyle \Pr \left(X>{\tfrac {n}{2}}\right)\leq {\frac {2}{n}}E[X]\leq {\frac {1}{n}}\sum _{i=3}^{g-1}p^{i}n^{i}={\frac {1}{n}}\sum _{i=3}^{g-1}n^{\frac {i}{g}}\leq {\frac {g}{n}}n^{\frac {g-1}{g}}=gn^{-{\frac {1}{g}}}=o(1).}$

Por lo tanto, para n suficientemente grande , la propiedad 1 se cumple con una probabilidad de más de 1/2 .

Propiedad 2. G no contiene ningún conjunto independiente de tamaño${\displaystyle \lceil {\tfrac {n}{2k}}\rceil }$.

Demostración. Sea Y el tamaño del conjunto independiente más grande en G. Claramente, tenemos

${\displaystyle \Pr(Y\geq y)\leq {n \choose y}(1-p)^{\frac {y(y-1)}{2}}\leq n^{y}e^{-{\frac {py(y-1)}{2}}}=e^{-{\frac {y}{2}}\cdot (py-2\ln n-p)}=o(1),}$

cuando

${\displaystyle y=\left\lceil {\frac {n}{2k}}\right\rceil \!.}$Por lo tanto, para n suficientemente grande , la propiedad 2 se cumple con una probabilidad de más de 1/2 .

Para valores de n suficientemente grandes , la probabilidad de que un gráfico de la distribución tenga ambas propiedades es positiva, ya que los eventos para estas propiedades no pueden ser disjuntos (si lo fueran, sus probabilidades sumarían más de 1).

Aquí viene el truco: dado que G tiene estas dos propiedades, podemos eliminar como máximo n /2 vértices de G para obtener un nuevo grafo G′ en${\displaystyle n'\geq n/2}$vértices que contienen solo ciclos de longitud al menos g . Podemos ver que este nuevo grafo no tiene un conjunto independiente de tamaño${\displaystyle \left\lceil {\frac {n'}{k}}\right\rceil }$. G′ solo puede particionarse en al menos k conjuntos independientes y, por lo tanto, tiene un número cromático de al menos k .

Este resultado da una pista de por qué el cálculo del número cromático de un grafo es tan difícil: incluso cuando no hay razones locales (como ciclos pequeños) para que un grafo requiera muchos colores, el número cromático aún puede ser arbitrariamente grande.