Finding threshold for the given graph

180 Views Asked by At

I am trying to calculate the threshold probability for the connectedness of a bipartite graph $G(n,n,p)$. I am trying to do it as it is done for a random graph $G(n,p)$. So I believe the conditions that we need to satisfy is 1) it should not have isolated vertex and 2) the given graph should not contain a component of size between $2$ & $a \ln n$.

Let X stands for the number of isolated vertices. Then the expected value of the number of isolated vertices in $G(n,n,p)$ is: \begin{equation} \mathbb{E}X=2n(1-p)^n \end{equation} So the graph $G(n,n,p)$ is connected if it doesn't have any isolated vertices then by Markov inequality:

\begin{equation} \mathbb{P}(X\ge 1)\le \mathbb{E}X. \end{equation}

Since I know that for $G(n,p)$ the threshold is $\frac{\ln n}{n}$. So I am considering p to be $\frac{\ln n + w(n)}{n}$ when $w(n)\rightarrow -\infty$

So Now \begin{align*}E[X] &= 2n \left( 1 - p \right)^n = 2 \exp \left( \ln n + n \ln \left( 1- p \right)\right) \\&= 2 \exp \left( \ln n + n (-p + O(p^2)) \right) \\ &= 2 \exp \left( -\omega_n + O(\ln n + \omega_n/ n)^2 \right) , \end{align*}

Now I am stuck from here. Am I doing it right? So now how should I proceed from here to prove the second condition also. I am not able to comprehend. Any help or resource is much appreciated. Thank you in advance.

1

There are 1 best solutions below

0
On

You'll suffer less if you estimate $(1-p)^n \sim e^{-np}$. The inequality $(1-p) \le e^{-np}$ is always valid; the asymptotic estimate as $n \to \infty$ is valid provided $p \ll \frac1{\sqrt n}$, which is fine in this problem.

Now $\mathbb E[\mathbf X] \sim 2ne^{-np} = 2n e^{-\ln n - \omega(n)} = 2 e^{-\omega(n)}$.

When you look at $\omega(n) \to -\infty$, you're looking at values of $p$ below the threshold. Here, we expect $\mathbf X$ to be large - but the first moment method can't tell us that $\mathbf X$ is large just because $\mathbb E[\mathbf X]$ is large! We'd want to use the second moment method, instead. (You can find a similar calculation done for $G(n,p)$ in this question.) Once we've done that, we can show that w.h.p. $\mathbf X>0$; therefore, below the threshold, $G(n,n,p)$ is not connected w.h.p.

However, when we're above the threshold and $\omega(n) \to \infty$, having $\mathbb E[\mathbf X] \sim 2e^{-\omega(n)}$ tells us that $\mathbb E[\mathbf X] \to 0$, which is enough to tell us that $\mathbf X = 0$ w.h.p. In other words, above the threshold, there are no isolated vertices w.h.p.

There are several ways to proceed next to prove that $G(n,n,p)$ is connected in this range, but it sounds like you want to continue by checking that $G(n,n,p)$ has no "small" components for some range of "small". Here, the idea that if we want a component with $s+t$ vertices, $s$ in one part and $t$ in the other, the expected number is at most $$ \binom ns \binom nt p^{s+t-1} (1-p)^{s(n-t)+t(n-s)} s^{t-1} t^{s-1} $$ where the last factor comes from the number of spanning trees of $K_{s,t}$. The factor $p^{s+t-1}$ (which works in our favor) should beat the factor $s^{t-1} t^{s-1}$ (which works against us), with enough to spare to sum over the possible values of $s$ and $t$. When $s,t$ are relatively small, the remaining terms behave a lot like $\mathbb E[\mathbf X]^{s+t}$, which we know goes to $0$.