existe un grafo bipartito cuyo tamaño $\geq \frac{m}{2}$

Question

La cuestión que intento resolver ahora es "Demostrar que toda gráfica $G$ tiene un subgrafo bipartito de tamaño $\geq \frac{m}{2}$ " mediante un método probabilístico (definiendo un espacio muestral y una variable aleatoria).

Me pregunto si mi respuesta de abajo es correcta, así que le agradecería que la comprobara.

1) Definir un espacio muestral $\Omega$ = {el conjunto de todos los posibles subgrafos bipartitos $V_1 \bigsqcup V_2$ de $G$ }.

2) Definir una variable aleatoria $X: \Omega \rightarrow \mathbb{R}$ tal que para $V_1 \bigsqcup V_2 \in \Omega$ , $X(V_1 \bigsqcup V_2)$ es el número de aristas de $V_1 \bigsqcup V_2$ . También, $X= \sum^m_{i=1}Y_i$ donde $Y_i$ es el indicador de la existencia de la arista $e_i$ en $V_1 \bigsqcup V_2$ . Por definición de $X$ , $\forall V_1 \bigsqcup V_2 \in \Omega$ el tamaño máximo de un subgrafo bipartito $\geq X(V_1 \bigsqcup V_2)$ .

3) El valor esperado $E(X) = \sum^m_{i=1} E(Y_i) = \sum^m_{i=1} P(e_i \in V_1 \bigsqcup V_2) = \sum^m_{i=1} \frac{1}{2} = \frac{m}{2}$ . Para cada $i$ , $P(e_i \in V_1 \bigsqcup V_2) = \frac{1}{2}$ porque $e_i$ es "en $V_1 \bigsqcup V_2$ " o "no".

Gracias de antemano.

Answer 1

Me cuesta seguir tu anotación, OP. No sé si lo has dicho así o no, pero no todo subgrafo bipartito de $G$ está en el conjunto $\Omega$ como se ha definido en 1).

Así es como yo enfocaría este problema: Partición al azar $V(G)$ en dos conjuntos $V_1$ y $V_2$ de la siguiente manera. Para cada vértice $v$ Lanzar una moneda justa: Vértice de la cara $v$ entra en $V_1$ ; colas $v$ entra en $V_2$ . Ahora, a partir de esta partición de $V(G)$ en $V_1$ y $V_2$ creamos un subgrafo $G_B$ de $G$ que es necesariamente bipartita, con partes $V_1$ y $V_2$ . Para cada arista $uv \in E(G)$ el borde $uv$ también está en $G_B$ si $u$ se pone en $V_1$ y $v$ en $V_2$ o $u$ se pone en $V_2$ y $v$ en $V_1$ .

Entonces, para cada $e \in E(G)$ la probabilidad de que la partición de $V(G)$ en $V_1$ y $V_2$ es tal que la arista $e$ también está en $G_B$ es precsisamente $\frac{1}{2}$ . Puedes terminar desde aquí.

Answer 2

No creo que su razonamiento sea válido. El hecho de que $e_i$ es "en $V_1\cup V_2$ " o "no" no implica que la probabilidad de que la arista esté dentro sea la mitad. Tomando otro ejemplo (más sencillo), la arista $e_i$ está conectada a todas las demás aristas, o "no lo está". Pero la probabilidad de que la arista esté conectada a todas las demás aristas no es claramente la mitad.

Si usted estuviera mirando $\Omega$ el conjunto de todos los subgráficos de $G$ entonces sí tendrías $E(X)=1/2$ en todos los subgráficos de $G$ existe una correspondencia única de 1 a 1 entre los gráficos que incluyen $e_i$ y sin incluir $e_i$ . Pero aquí, con $\Omega$ el conjunto de todos los posibles subgrafos bipartitos, no es el caso de ningún gráfico $G$ .

Por ejemplo, definamos $G = K_3$ el gráfico completo en 3 vértices etiquetados. Tiene 7 subgrafos bipartitos (3 con 2 aristas, 3 con 1 arista y uno sin aristas). Entonces para cada arista $P(e_i \in V_1\cup V_2)=3/7$ .