Al seleccionar aleatoriamente n aristas únicas de un grafo completo, ¿cuál es la distribución de probabilidad para el número de vértices cubiertos?

Question

Supongamos que tenemos un grafo completo $G = \{V,E\}$ donde $V$ es el conjunto de vértices y $E$ es el conjunto de bordes. Seleccionamos aleatoriamente $n$ único bordes de $G$ ( $n \le |E|$ ), y estos bordes cubren $m$ vértices.

El problema es: ¿cuál es la distribución de probabilidad para $m$ ?

\=========================================

He leído un post muy útil: Dado un grafo simple etiquetado al azar con n aristas, ¿cuándo es más probable obtener un grafo con más aristas que vértices?

\==========================================

Ahora estoy tratando de transformar este problema a la elección de pares de elementos al azar de un conjunto, y me parece que este post podría ser útil, ya que hizo una pregunta muy similar. https://stackoverflow.com/questions/15793172/efficiently-generating-unique-pairs-of-integers

¿Podría alguien ayudarme?

Answer 1

Para empezar, supongamos que $G=(V,E)$ es el grafo completo con $N$ vértices. Para un subconjunto $X\subset E$ , dejemos que $V_X$ denotan los vértices de $X$ . Así que la pregunta es encontrar la probabilidad de $|V_X|=m$ al azar $X$ de tamaño $n$ .

Para cualquier conjunto $U\subset V$ de tamaño $m$ podemos hallar el número de conjuntos $X\subset E$ con $V_X=U$ utilizando el principio de inclusión-exclusión $$ a_{n,m}=\sum_{r=0}^m (-1)^{m-r} \binom{m}{r}\binom{\binom{r}{2}}{n} $$ que corresponde a una suma alternada sobre conjuntos $X$ y $W$ tal que $V_X\subset W\subset U$ con $r=|W|$ de tal forma que los casos con $V_X=U$ suman uno y todos los demás suman cero. He añadido una explicación más detallada a continuación.

El número de conjuntos $U\subset V$ de tamaño $m$ es $\binom{N}{m}$ por lo que el número de formas de elegir $X\subset E$ y $U\subset V$ de tamaños $n$ y $m$ es $$ A_{n,m}=a_{n,m}\cdot\binom{N}{m} =\sum_{r=0}^m (-1)^{m-r} \binom{N}{m}\binom{m}{r}\binom{\binom{r}{2}}{n} $$ donde el número total de formas de elegir $X\subset E$ de tamaño $n$ es $$ A_n=\sum_m A_{n,m}=\binom{\binom{N}{2}}{n} $$ como se esperaba.

Así que la probabilidad de obtener $|V_X|=m$ para un $X\subset E$ de tamaño $n$ es $$ p_{m|n}=\frac{A_{n,m}}{A_n}. $$

---

He aquí una explicación más detallada del uso del principio de inclusión-exclusión en este caso concreto.

El problema es que, aunque se puede contar fácilmente el número de series $X\subset E$ con $V_X\subset U$ para cualquier $U\subset V$ pero es más difícil contar sólo los $X$ QUÉ HACER $V_X=U$ . Así que lo que queremos hacer es contar todos $X$ con $V_X\subset U$ y luego restar todos aquellos para los que $V_X$ es menor que $U$ .

Para cualquier $W\subset V$ el número de subconjuntos $X\subset E$ de tamaño $n$ con $V_X\subset W$ es $$ A_n(W)=\binom{\binom{|W|}{2}}{n} $$ ya que hay $\binom{|W|}{2}$ aristas entre los vértices de $W$ .

Si empezamos con $A_n(U)$ hemos contado todos $X$ con $V_X\subset U$ : no sólo $X$ con $V_X=U$ sino también aquellas para las que $V_X$ es menor que $U$ . Por ejemplo, si $V_X=U\setminus\{u\}$ para algunos $u$ se contabiliza en $A_n(U)$ . Así que un primer paso es restarlos: $$A_n(U)-\sum_{u\in U}A_n(U\setminus\{u\}).$$ Esto cuenta $X$ con $V_X=U$ una vez, mientras que $X$ con $V_X=U\setminus\{u\}$ para algunos $u\in U$ no se contabilizan. Sin embargo, $X$ con $V_X=U\setminus\{u_1,u_2\}$ se han restado dos veces y hay que volver a sumarlas: $$ A_n(U)-\sum_{u\in U}A_n(U\setminus\{u\}) +\sum_{\{u_1,u_2\}\subset U} A_n(U\setminus\{u_1,u_2\}. $$ Y así seguimos alternando sumas y restas hasta que obtenemos $$ \sum_{W\subset U}(-1)^{|U\setminus W|} A_n(W) $$ como el número de $X$ para que $V_X=U$ . Ahora inserte que $W\subset U$ con $|W|=r$ puede seleccionarse en $\binom{m}{r}$ diferentes maneras y $|U\setminus W|=m-r$ y se obtiene la suma de $a_{n,m}$ .