I have the following problem
consider a random bipartite with vertex classes $A$ and $B$ of size $|A|=|B|=\mathrm{log}^{2}(n)$ graph in which every possible edge is chosen independently with probability $p(n)=\frac{1}{{\mathrm{log} (n)}}$. Now i don't know if this graph will contain w.h.p a perfect matching but if it does i'd like to prove it. So i guess my first question is does it? If the answer to my first question is yes, id' like to be able to prove it. As i'm fairly new to perfect matchings i had the following idea, although i'm not sure if this is a conventional way to prove a random bipartite graph has a perfect matching w.h.p
I'm aware that Halls condition is a necessary and sufficient condition to prove the existence of a perfect matching i.e. for any subset $S \subseteq A$ that $|N(S)| \geq |S|$. So would it suffice to show that for any $S \subseteq A$ that $|N(S)| \geq |S|$ in the following way. If a set $S'$ violates Halls condition then there must exist at least $\mathrm{log}^{2}(n)-|S'|$ vertices in $B$ which are not adjacent to any vertex in $S'$. Given any collection of these vertices the probability they are not independent to any vertex in $S'$ is $(1-p)^{|S'|(\mathrm{log}^{2}(n)-|S'|)}$. In addition there are $\binom{\mathrm{log}^{2}(n)}{\mathrm{log}^{2}(n)-|S'|}$ possible choices for $|S'|$ and $|S'|$ can range from $1$ to $\mathrm{log}^{2}(n)$. Henceit would suffice to require $\sum_{|S'|=1}^{\mathrm{log}^{2}(n)} \binom{\mathrm{log}^{2}(n)}{\mathrm{log}^{2}(n)-|S'|}(1-p)^{|S'|(\mathrm{log}^{2}(n)-|S'|)}=o(1).$ where $p=\frac{1}{\mathrm{log}(n)}$.
So firstly i'd like to know whether a perfect matching exists w.h.p and secondly whether my proof would be sufficient for it. I appreciate any help.
Best Answer
What is the purpose of the variable $n$ in your notation? If I understand correctly, we could say that you have a bipartite graph with two vertex classes of size $n$ and each of the $n^2$ possible edges present with probability $\frac1{\sqrt{n}}.$ So the expected number of edges is $n\sqrt{n}.$ The result of Erdos-Renyi is that with $n\log{n}+cn+o(n)$ edges chosen randomly the probability of a perfect matching converges to $$e^{-2e^{-c}}$$ as $n \rightarrow \infty.$ So the probability of a perfect matching in your case seems quite high indeed.