Número cromático de subgráfico abarcando al azar

Question

Que $G=(V,E)$ ser un gráfico con cromática número $χ(G)=k>4$, que $G'=(V,E')$ ser un subgráfico expansión de $G$, creado por cosecha cada borde de $E$ $1/2$ de la probabilidad.

¿Cómo puedo mostrar que hay un constante $c>0$ tal que $χ(G')≤2$ con probabilidad menos de $2^{{-ck^2}}$?

Como primer paso, ¿cómo puedo Mostrar $k=5$?

Answer 1

Para $k=5$ (o cualquier otro fijo $k$), ya que podemos optar $c$ a ser algo que nos gusta, sólo necesitamos algunos obligado en la probabilidad independiente del número de vértices.

De hecho, se puede demostrar que la probabilidad es en la mayoría de las $\frac12$, una vez que se prueba el siguiente lema:

Deje $H_1$ $H_2$ ser gráficos en el mismo conjunto de vértices, y deje $H_1 \cup H_2$ ser el grafo obtenido al tomar todos los bordes presentes en cualquiera de las $H_1$ o $H_2$. A continuación,$\chi(H_1 \cup H_2) \le \chi(H_1) \cdot \chi(H_2)$.

Prueba: Dado un $r_i$-colorear $f_i$$H_i$$i \in \{1,2\}$, podemos construir un $r_1r_2$colorear de $H_1 \cup H_2$ dar $v$ color $(f_1(v), f_2(v))$. Si $v$ $w$ son adyacentes en $H_1 \cup H_2$, ya sea que están adyacentes en $H_1$ (e $f_1(v) \ne f_1(w)$) o son adyacentes en $H_2$ (e $f_2(v) \ne f_2(w)$), por lo que en cualquiera de los casos tenemos $(f_1(v), f_2(v)) \ne (f_1(w), f_2(w))$.

Dado que abarca un subgrafo $G'$$G$, si dejamos $G''$ el gráfico constituida por todos los bordes de $G$ no $G'$,$4 < \chi(G) \le \chi(G') \cdot \chi(G'')$, lo $\chi(G') > 2$ o $\chi(G'') > 2$. Así que hemos dividido todos los posibles gráficos en parejas en las que al menos una gráfica tiene cromática número de más de $2$, lo que significa que $\Pr[\chi(G') \le 2]$ es en la mayoría de las $\frac12$.

---

Para utilizar esto para obtener el general obligado queremos, es suficiente para particionar el conjunto de borde $E$ a $\Omega(k^2)$ partes disjuntas $E_1, E_2, \dots, E_t$, de tal manera que $\chi(G_{E_i}) \ge 5$ todos los $i$. Luego de un elegido al azar $E' \subseteq E$, $\chi(G_{E'}) \le 2$ sólo si $\chi(G_{E' \cap E_i}) \le 2$ todos los $i$. Estas son las $t$ eventos independientes con probabilidad en la mayoría de los $\frac12$ por el argumento anterior, por lo $\Pr[\chi(G_{E'}) \le 2] \le 2^{-t}$.

Para encontrar $E_1, \dots, E_t$, fijar un $k$-colorear $f$$G$, y considerar los conjuntos de $V_{abcde} = f^{-1}(\{a,b,c,d,e\})$ para algunos de los colores que $a, b, c, d, e$. No es difícil ver que si dejamos $E_{abcde}$ ser el conjunto de todas las aristas entre pares de vértices en $V_{abcde}$,$\chi(G_{E_{abcde}}) = 5$; tenemos $E_{abcde} \cap E_{a'b'c'd'e'} = \varnothing$ si en la mayoría de un color es compartida entre el$\{a,b,c,d,e\}$$\{a',b',c',d',e'\}$.

Por lo que queda elegir $\Omega(k^2)$ subconjuntos de a $\{1,2,\dots,k\}$ del tamaño de la $5$ entre los que no hay dos comparten más de un elemento, que se puede hacer probabilísticamente con un primer momento de cálculo.