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!


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}


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.