Probabilidad de que un gráfico aleatorio sea bipartito

Question

Partimos de un "vacío" en el gráfico de $n$ vértices de pie solo. Cada vértice tiene $s$ posibilidades de elegir un vértice en cada oportunidad como en su vecino, de manera uniforme y en forma independiente de la $n$ vértices, incluyendo a sí mismo, con la sustitución. Un vértice elige a sus vecinos, uno por uno. Así que un vértice puede elegir sí mismo, y puede elegir un vértice muchas veces. El grafo es dirigido por lo que si $u$ elige $v$ pero $v$ no elige a $u$, $(u,v)\in E$ pero $(v,u) \not\in E$ . $s \ge 2$ es una constante entero.

Quiero mostrar al $n\to +\infty$, es poco probable que tengamos un gráfico bipartito. Es decir, para $G(V,E)$, $\exists A \subset V$, todos los bordes en $E$ entre $A$ $V-A$ y sin borde en $E$ está dentro de $A$ o en el interior de $V-A$, que debe ser raro.

Hice algunos experimentos con MATLAB y parece que la probabilidad podría ser exponencialmente pequeño. (Por favor, no ser afectado por el resultado, que puede estar mal.) Sin embargo, yo sólo quiero mostrar es el que va a $0$ más rápido que el de $O(n^{-1})$.

Gracias!

Answer 1

La forma habitual de hacerlo es la siguiente:

Supongamos que el grafo ES bipartito. A continuación, hay una partición $[n]=A\cup B$, $A\cap B=\varnothing$, tal que todas las aristas en el grafo tiene un extremo en $A$ y uno final en $B$.

Deje $S$ el número de particiones, es decir, el número de maneras en que podemos escribir $[n]=A\cup B$, $A\cap B=\varnothing$, de tal manera que no hay bordes dentro de $A$ y sin bordes en el interior de $B$. Entonces la probabilidad de que el grafo es bipartito es, precisamente,$P(S>0)$. Pero, por la desigualdad de Markov, sabemos que $$ P(S>0)=P(S\geq 1)\leq\frac{\mathbb{E}[S]}{1}=\mathbb{E}[S], $$ donde $\mathbb{E}$ denotar la expectativa. Pero, ya que las expectativas romper sobre la suma, tenemos $$ \mathbb{E}[S]=\sum_{\substack{[n]=A\cup B\\A\cap B=\varnothing}}P(\text{sin bordes dentro de $A$ o $B$}). $$ Considere la posibilidad de esta probabilidad. Esto es equivalente a decir "No vértice en $A$ elige un vecino en $A$ y ningún vértice en $B$ elige un vecino en $B$". Dado que las decisiones se toman de forma independiente, esto simplifica mucho: $$ P(\text{sin bordes dentro de $A$ o $B$})=\prod_{v\in A}P(\text{$v$ elige sin vecinos en $A$})\cdot\prod_{v\B}P(\text{$v$ elige sin vecinos en $B$}) $$ Para una fija $v$ y un conjunto fijo $A$, $$ P(\text{$v$ elige sin vecinos en $A$})=\frac{\binom{b+s-1}{s-1}}{\binom{n+s-1}{s-1}}, $$ donde $\newcommand{\order}[1]{\lvert #1 \rvert}b:=\order{B}$. Por qué? Debido a $v$ no la elección de los elementos de $A$ significa que sólo escoge los elementos de $B$; el número de formas de elegir los $s$ elementos de $b$, con reemplazo, es $\binom{b+s-1}{s-1}$. Etc.

Tenemos un simiar resultado para $v\in B$, excepto el uso de $a:=\order{A}$ en lugar de $b$. Así, esto nos dice $$ \begin{align*} \mathbb{E}[S]&=\sum_{a+b=n}\sum_{\substack{[n]=A\cup B\\\order{A}=a,\order{B}=b}}\left[\frac{\binom{a+s-1}{s-1}}{\binom{n+s-1}{s-1}}\right]^b\left[\frac{\binom{b+s-1}{s-1}}{\binom{n+s-1}{s-1}}\right]^a\\ &=\binom{n+s-1}{s-1}^{-n}\sum_{a+b=n}\sum_{\substack{[n]=A\cup B\\\order{A}=a,\order{B}=b}}\binom{a+s-1}{s-1}^b\binom{b+s-1}{s-1}^a\\ &=\binom{n+s-1}{s-1}^{-n}\sum_{a=1}^{n-1}\binom{n}{a}\binom{a+s-1}{s-1}^b\binom{b+s-1}{s-1}^a. \end{align*} $$ Aquí, hemos utilizado el hecho de que la determinación de la $a$ determina la $b$, y determinar el $A$ determina la $B$... y el hecho de que no se $\binom{n}{a}$ formas de elegir los $A$, determinado $a$.