Planteamiento probabilístico para demostrar un teorema de la teoría de grafos

Question

Un teorema de la teoría de grafos es el siguiente,

Deje $G=(V,E)$ ser finito gráfico donde $V$ es el conjunto de vértices y el $E$ es el conjunto de aristas. Entonces existe un subconjunto de vértices $W$, es decir,$W \subset V$, de tal manera que el número de aristas de conectar $W$ $W^C$ al menos $\frac{|E|}{2}$ donde $W^C = V\backslash W$ $|E|$ es el número total de aristas en el grafo $G$.

La pregunta es para probar este teorema por un enfoque probabilístico.

Mi idea es la siguiente: Deje $|V|=n,|W|=m$, entonces el máximo número posible de los bordes entre el$W,W^C$$m\times(n-m)$. El máximo número posible de aristas en el grafo $G$$C_n^2 = \frac{n!}{2!\times(n-2)!}$. Podemos tratar los bordes como si estuvieran dispersos al azar en el $C_n^2$ posiciones, y con una probabilidad de $p=\frac{m\times(n-m)}{C_n^2}$ uno de los bordes conectaría $W,W^C$.

Entonces es como un ensayo de Bernoulli de $|E|$ de veces con probabilidad de éxito $p=\frac{m\times(n-m)}{C_n^2}$, y la probabilidad de que hay al menos $\frac{|E|}{2}$ bordes de conectar $W,W^C$$\sum\limits_{k = \left\lceil {\frac{1}{2}|E|} \right\rceil }^{|E|} {C_{|E|}^k{p^k}{{(1 - p)}^{|E| - k}}} $. Pero esta probabilidad es de un particular,$W$. Tenemos que mostrar con probabilidad existe uno o más $W$ la satisfacción de las condiciones del mencionado teorema. Me quedé atrapado aquí. Alguien puede ayudar con esta prueba? Gracias!

Answer 1

Tomar el gráfico de $G = (V,E)$ y para cada vértice, seleccionar al azar si se encuentran en $W$ independiente de la probabilidad de $p = \frac{1}{2}$. Para cada arista $e_i \in E$, defina la variable aleatoria $X_i$, $1$ si $e$ se conecta $W$$W^C$, e $0$ lo contrario. A continuación, $\mathbb{P}(X_i = 1) = \frac{1}{2}$, e $\mathbb{E}(X_i) = \frac{1}{2}$.

Por la linealidad de la expectativa: $$\mathbb{E}(\text{number of edges connecting $W$ and $W^C$}) = \mathbb{E}(\sum X_i) = \sum E(X_i) = \sum \frac{1}{2} = \frac{|E|}{2}$$

Ya que el número de aristas que cruzan el corte es $\frac{|E|}{2}$, debe haber al menos una selección de $W$ que tiene al menos $\frac{|E|}{2}$ bordes cruce de la corte.

Se puede ver que la demanda sostiene que, con certeza, porque si se supone que todas las opciones posibles para $W$ tienen menos de $\frac{|E|}{2}$ bordes de cruzar la corte, entonces tenemos la contradictorios:

$$\mathbb{E}(\text{number of edges connecting $W$ and $W^C$}) < \frac{|E|}{2}$$

ETA: Para aquellos que todavía están confundidos - he aquí un pequeño ejemplo claro: Supongamos $V = \{v_1, v_2\}$$E = \{(v_1,v_2)\}$.

Tenemos en cuenta todas las opciones posibles para $W$, donde los vértices son colocados de forma independiente en $W$ con una probabilidad de $\frac{1}{2}$:

1. $W = \emptyset$. No hay bordes de la cruz el corte. Esto ha probabilidad de $\mathbb{P}(v_1 \notin W \cap v_2 \notin W) = \frac{1}{2}\cdot \frac{1}{2} = \frac{1}{4}$.
2. $W = \{v_1\}$. Uno cruza el borde de corte. Esto ha probabilidad de $\mathbb{P}(v_1 \in W \cap v_2 \notin W) = \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4}$.
3. $W = \{v_2\}$. Uno cruza el borde de corte. De nuevo, esto tiene probabilidad de $\mathbb{P}(v_1 \notin W \cap v_2 \in W) = \frac{1}{4}$.
4. $W = \{v_1,v_2\}$. No cruza el borde de corte. De nuevo, la probabilidad se $\frac{1}{4}$.

A continuación, $\mathbb{P}((v_1,v_2) \textrm{ crosses the cut}) = \frac{1}{2}$ y el número esperado de cruzar los bordes es $$0\cdot \frac{1}{4} + 1\cdot \frac{1}{4}+1\cdot \frac{1}{4}+0\cdot \frac{1}{4} = \frac{1}{2} = \frac{|E|}{2}$$

Si todas las posibilidades que tenía menos de $\frac{|E|}{2}$ bordes cruce de la corte, la expectativa tiene que ser menos de $\frac{|E|}{2}$. Por lo tanto, debe haber al menos una opción para $W$ tal que al menos el $\frac{|E|}{2}$ bordes cruza el corte. En este caso, una opción es $W = \{v_1\}$.