11
$\begingroup$

By a random $n\times n$ bipartite graph, I mean a random bipartite graph on two vertex classes of size $n$, with the edges added independently, each with probability $p$.

I want to find the probability that such a graph contains an isolated vertex.

Let $X$ and $Y$ be the vertex classes. I can calculate the probability that $X$ contains an isolated vertex by considering one vertex first and using the fact that vertices in $X$ are independent.

But I don't know how to calculate the probability that $X\cup Y$ contains an isolated vertex. Can someone help? Thanks!

$\endgroup$
1

1 Answer 1

3
$\begingroup$

This can be done using inclusion/exclusion. We have $n+n$ conditions for the individual vertices being isolated. There are $\binom nk\binom nl$ combinations of these conditions that require $k$ particular vertices in $X$ and $l$ particular vertices in $Y$ to be isolated, and the probability for this is $q^{kn+ln-kl}$, with $q=1-p$. Thus by inclusion/exclusion the desired probability that at least one vertex is isolated is

\begin{align} &1-\sum_{k=0}^n\sum_{l=0}^n(-1)^{k+l}\binom nk\binom nlq^{kn+ln-kl}\\ ={}&1-\sum_{k=0}^n(-1)^k\binom nkq^{kn}\sum_{l=0}^n(-1)^l\binom nlq^{ln-kl}\\ ={}&1-\sum_{k=0}^n(-1)^k\binom nkq^{kn}\left(1-q^{n-k}\right)^n\\ ={}&1-\sum_{k=0}^n(-1)^k\binom nk\left(q^k-q^n\right)^n\;. \end{align}

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .