Probabilidad de que un gráfico sea bipartito

Question

Dado el gráfico vacío en $n$ vértices, añadimos $m$ de la $\binom{n}{2}$ bordes posibles, uniformemente al azar.

¿Cuál es la probabilidad de que el grafo resultante sea bipartito (es decir, que no contenga ciclos Impares)?

Formulación alternativa: En el modelo de grafos aleatorios $G(n,m)$ ¿Cuántos de los $\binom{\binom{n}{2}}{m}$ ¿los gráficos son bipartitos?

Answer 1

Cuando $m \ll n$ la probabilidad es muy alta, ya que con alta probabilidad (es decir, con probabilidad que tiende a $1$ ) $G(n,m)$ es un bosque, y todos los bosques son bipartitos.

Cuando $m = \frac12 cn$ (donde $G(n,m)$ es muy parecido a un grafo aleatorio binomial con probabilidad de aristas $\frac cn$ ) depende mucho del valor de $c$ . Si $0 < c < 1$ estamos en la fase subcrítica donde, con alta probabilidad, el mayor componente del grafo aleatorio tiene $O(\log n)$ vértices. Por lo tanto, podemos determinar si el gráfico es bipartito contando los ciclos pequeños.

El número esperado de ciclos de longitud $k$ es asintóticamente $\frac{c^k}{2k}$ que se obtiene multiplicando los siguientes factores:

• Tenemos $\binom nk \sim \frac{n^k}{k!}$ formas de elegir $k$ vértices.
• Hay $\frac{k!}{2k}$ maneras de elegir un ciclo en esos $k$ vértices.
• Hay una probabilidad de $\binom{\binom n2-k}{m-k} / \binom{\binom n2}{m} \sim \frac{c^k}{n^k}$ que todas las aristas de ese ciclo están presentes. (Esta es la aproximación que requiere $k$ para ser pequeño; aquí, tenemos $k = O(\log n)$ pero cualquier $k = o(n)$ lo haría).

Se puede demostrar por el método de los momentos que el número de ciclos de longitud $k$ es asintóticamente Poisson (se explica por la intuición de que los ciclos surgen de muchos eventos casi independientes que son individualmente muy improbables). Por tanto, la probabilidad de que no haya ciclos de longitud $k$ es $e^{-c^k/2k}$ en el límite.

Necesitaría más justificación, pero probablemente es cierto que estos eventos son asintóticamente independientes como $n \to \infty$ . Esto significa que la probabilidad de que $G(n,m)$ es bipartita se obtiene tomando el producto de estas probabilidades $$ \exp\left(-\frac{c^3}{6} - \frac{c^5}{10} - \frac{c^7}{14} - \dots\right) = \exp\left(\frac12c - \frac12 \operatorname{arctanh} c\right). $$ Esta probabilidad tiende a $0$ como $c \to 1$ por lo que por monotonicidad vemos que cuando $m = \frac12cn$ et $c>1$ el gráfico no es bipartito con alta probabilidad.

Intuitivamente, en este punto, estamos en la fase supercrítica; el número de ciclos (algunos de ellos bastante largos) tiende al infinito, y como no hay ninguna razón particular que los obligue a ser pares, es probable que muchos de ellos sean Impares.