Probabilidades de vértices aislados para diferentes grafos aleatorios

Question

Estoy tratando de enseñarme un poco más sobre las probabilidades de umbral para los grafos aleatorios, y estoy mirando la probabilidad de que los grafos tengan un vértice aislado, cuando añadimos algunas restricciones (cuando por un 'grafo aleatorio' quiero decir que tomamos el conjunto de vértices y añadimos cada posible arista (no dirigida) entre vértices con probabilidad p). Por ejemplo, en el grafo estándar ('sin restricciones') de n vértices, tenemos algo así como p = log(n)/n como una probabilidad por encima de la cual esperamos no obtener vértices aislados a.e., y por debajo de la cual a.e. obtenemos un vértice aislado. Este caso está bien documentado - sin embargo, puedo encontrar poco o nada en los libros o en línea en el caso de tipos específicos de gráfico aleatorio que son, por ejemplo, Conectado en k/conectado en k-borde bipartito/tripartito, etc.

El caso que más me interesa (de momento) es el de los grafos bipartitos, y supongo que es el siguiente caso más fácil de entender también, pero no encuentro documentación en ningún sitio. ¿Existe una forma sencilla de extender el resultado de los grafos normales a los grafos bipartitos, asumiendo que ambos conjuntos de vértices tienen el mismo tamaño? Supongo que mi preocupación es que, obviamente, se trata de un conjunto diferente de grafos factibles al caso general de 2n vértices, tanto de menos grafos con un vértice aislado como de menos grafos en total, por lo que no me queda claro que podamos decir inmediatamente que la "proporción" de grafos que tienen un vértice aislado se comportará necesariamente igual para n grandes.

Como mencioné anteriormente, estaré encantado de leer cualquier cosa que alguien pueda sugerir en casos más restringidos, simplemente no he sido capaz de encontrarlo yo mismo, así que las recomendaciones serán muy apreciadas.

¡Muchas gracias!

Answer 1

Para muchos grafos estructurados (k-conectado/k-edge-conectado/bipartito/etc.) la idea de hacer un grafo añadiendo aristas al azar no tiene mucho sentido. Puedes elegir un grafo k-conectado al azar en n vértices enumerando todos los grafos de este tipo y eligiendo uno. Para los bipartitos puedes hacer algo como lo que quieres. Imagina un grafo bipartito sobre $n+m$ vértices, con el $n$ vértices en un lado de la división especificada de antemano. A continuación, hay $nm$ aristas candidatas que puedes rellenar al azar y puedes preguntar por la probabilidad de un vértice aislado. El caso más sencillo es $n=m$ , por lo que hay $n^2$ aristas candidatas, y cada vértice tiene $n$ de que se conecten a ella.

Para un vértice dado, si se elige $p$ aristas, la probabilidad de que esté aislada es $$ \frac{(n^2-n)(n^2-n-1)\ldots(n^2-n-p+1)}{n^2(n^2-1)\ldots(n^2-p+1)}=\frac{(n^2-n)!(n^2-p)!}{n^2!(n^2-n-p)!} $$
Una aproximación es considerar estos eventos independientes (ignorando las correlaciones inducidas por el hecho de que una arista que no va a un determinado vértice sí va a otro) y calcular la probabilidad de que cualquier vértice quede aislado.

Answer 2

No puedo dejar esto como comentario, así que me temo que tendré que dejarlo como "respuesta". He estado haciendo simulaciones en grafos bipartitos aleatorios de tamaño hasta 500x500 (es decir, 2n=1000), y los límites parecen estar fuera de un factor de dos: casi no obtengo vértices aislados hasta p=log(500)/500, y por encima de 2log(500)/500 obtengo una coincidencia cada vez: entre estos valores a veces obtengo una coincidencia y a veces no. He comprobado todo y no veo por ningún lado que pueda haber perdido un 2: ¿estoy siendo lento o es posible que por alguna razón se obtengan límites del doble de lo previsto?

Answer 3

EDITAR : Lo siento, no pensé en las funciones de umbral. Asumí que estábamos trabajando con una constante $p$ , pensó en el problema, y perdió de vista la pregunta real. No sé si es relevante, pero lo dejaré.

Dejemos que $G$ sea un grafo bipartito en $2n$ vértices con partes $A$ y $B$ con $|A| = |B| = n$ .

Dejemos que $E_A$ sea el evento que $A$ tiene un vértice aislado, $E_B$ sea el evento que $B$ tiene un vértice aislado. Estamos buscando $P(E_A \cup E_B) = P(E_A) + P(E_B) - P(E_A \cap E_B)$ .

Cada vértice de $A$ tiene $n$ posibles aristas, cada una con probabilidad independiente $p$ por lo que la probabilidad de que esté aislado es $(1-p)^n$ . Sumando sobre los vértices de $A$ la probabilidad de que cualquier vértice en $A$ está aislado es $n(1-p)^n$ . El caso de $B$ teniendo un aislado es claramente simétrico. Por lo tanto, $P(E_A) = P(E_B) = n(1-p)^n$ .

Ahora considere $P(E_A \cap E_B) = P(E_A)P(E_B|E_A)$ . Para cualquier vértice en $B$ tenemos $n - 1$ posibles aristas (porque sabemos que uno de los vértices en $A$ está aislado). La probabilidad de que un determinado vértice en $B$ está aislado es entonces $(1 - p)^{n - 1}$ . Sumando sobre los vértices de $B$ , $P(E_B|E_A) = n(1-p)^{n-1}$ . Así que $P(E_A \cap E_B) = (n(1-p)^n)(n(1-p)^{n-1}) = n^2(1-p)^{2n-1}$ .

Ponerlo todo junto, $P(E_A \cup E_B) = 2n(1-p)^n + n^2(1-p)^{2n - 1}$ .

Como referencia, recomiendo encarecidamente el libro de Diestel Teoría de los gráficos que tiene un tratamiento introductorio de los grafos aleatorios (puede estar por encima de este nivel). Hay una vista previa gratuita aquí - http://diestel-graph-theory.com/ . Bollobas". Teoría moderna de los grafos tiene un tratamiento similar pero ligeramente más profundo. Bollobas también escribió un texto titulado Gráficos aleatorios que no conozco, pero se le considera un líder en el campo. No estoy seguro de que ninguno de estos aborda su problema específico.