La probabilidad de Selección de Un Conjunto Aleatorio en el Gráfico de $k$ Bordes Que es Independiente.

Question

En el gráfico de $k$ bordes, si tomamos cada vértice al azar y de forma independiente con una probabilidad de $\frac{1}{2}$, demostrar que la probabilidad de que este conjunto de elegidos al azar de los vértices es un conjunto independiente es mayor que $\frac{1}{2^k}$.

El enfoque que estoy usando implica considerar todas las posibles selecciones de los vértices, y la delimitación de la probabilidad de que esas selecciones tienen un conjunto independiente.

Muchas gracias!

Answer 1

Elegir un nodo arbitrario de cada una de las $k$ bordes, formando así un conjunto de $K \le k$ nodos. Si ninguno de estos nodos es seleccionado, el conjunto de nodos seleccionados es independiente, porque es falta al menos un nodo de cada borde. La probabilidad de que ninguno de los elegidos, los nodos seleccionados es exactamente $2^{-K} \ge 2^{-k}$.

Answer 2

Bien, estrictamente hablando, esto sólo es cierto para $k > 0$. Para $k=0$ tenemos un gráfico sin bordes, y la probabilidad de escoger un conjunto independiente es igual a $1=\frac{1}{2^0}$.

En cuanto a su enfoque, yo no entiendo realmente lo que es. Si usted considera que cualquier selección de vértices, es independiente o no. No es una cuestión de probabilidad, debido a que la gráfica no es al azar. La gráfica es fijo, la selección es al azar.

Aquí hay una posible manera de acercarse a este. Para cualquier fijo de selección de vértices, la probabilidad de elegir esta exacta de selección es $\frac{1}{2^n}$ donde $n$ es el número de vértices del grafo. Aquí uso la suposición de que nosotros recogida de las diferentes vértices de forma independiente el uno del otro. Es probablemente implícita.

Ahora, a partir de esta observación, podemos ver que la probabilidad de escoger un conjunto independiente de vértices es simplemente $$ p = \frac{m}{2^n}, $$ donde $m$ el número total de diferentes conjuntos independientes de los vértices.

Así, se llega a probar que $m>2^{n-k}$. No es difícil. Aquí es un indicio de que podría ayudar con eso: usted puede utilizar el hecho de que un gráfico con $n$ vértices y $k$ bordes tiene al menos $n-k$ de los componentes conectados.