What is the probability that a random $n\times n$ bipartite graph has an isolated vertex?

Question

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!

Answer 1

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}