# Perfect matching in random bipartite graph - with fixed probability

as a follow up from this question :

Suppose that we have a simpler problem, where the probability $$p$$ is fixed. Of course we could use the above result to proove that almost every graph in the model $$\mathcal{G}_{n,n,p}$$ contains a perfect matching, saying for instance that $$p > \frac{\sqrt{n} + \log{n}}{n}$$ for big enough $$n$$.

However, couldn't we find a more direct result? I've been looking at the probability of findind a set $$S$$ (size $$k$$) giving a contradiction for Hall's mariage theorem. With $$q=1-p$$, we need each element of $$S$$ not connected to the $$n-k-1$$ elements not in $$N(S)$$, therefore : $$Pr[ |N(S)|<|S| ] \leq q^{nk-k(k-1)}$$

And $$Pr[\nexists \text{ a perfect matching}] \leq \sum_{k=1}^n \binom{n}{k}q^{nk-k(k-1)}$$

But from there, trying to proove that this sum tends to 0, simple binomial approximation $$\sim n^k/k!$$ gives too large a bound. Would you recommand any other calculation? Thanks

Many approximations to the binomial $$\binom nk$$ are not symmetric in $$k$$ and $$n-k$$, so they perform badly when $$k$$ is close to $$n$$. (For example, $$\frac{n^k}{k!}$$ is somewhere around $$e^n$$ when $$k=n$$, even though actually $$\binom nn = 1$$.)

Here, the sum is almost but not quite symmetric: we can write the power of $$q$$ as $$q^{k(n+1-k)} < q^{k(n-k)}$$, and the latter is symmetric. So we can bound the sum by $$2 \sum_{k=1}^{n/2} \binom nk q^{k(n-k)}$$ and avoid the problematic values of $$k$$, getting a sum that's easy to bound using your approximation. It's even enough to write $$\binom nk \le n^k$$ and get $$\binom nk q^{k(n-k)} \le (n \cdot q^{n-k})^k \le (n \cdot q^{n/2})^k$$.