# Threshold for perfect Matchings in Bipartite graph

Consider the random bipartite graph with vertex classes of size $n$ and each edge being present independently with probability $p(n)$.

I know one way to prove the threshold of a perfect matching is to look at Halls theorem, but could we do it using first and second moment methods?

To clarify what I mean. We can work out using Halls theorem a value for the probability $p$ that the graph contains a perfect matching by showing w.h.p $|N(S)|\geq S$ for all subsets $S \subseteq V$.

Can we do the same thing but just by counting sets of independent edges of size $n$ (here both vertex classes have size $n$)? So what I mean here is if I counted all possible sets of $n$ independent edges, and then let $X$ be the random variable representing the number of sets of $n$ independent edges present. Could I obtain this value of $p$ by working out what it needs to be to ensure $X>0$ using first and second moment methods?

• provide more details here, please... Jan 5 '15 at 19:02
• What do you mean by "proving the threshold" and by the "threshold of a perfect matching"?
– Seva
Jan 5 '15 at 19:16
• The question at mathoverflow.net/questions/60075/… , though addressing a different graph property, has a similar flavor. Jan 6 '15 at 23:41
• Imagine adding edges at random until the moment there is a perfect matching. This is purely a guess, but I suspect that the last edge needed takes an isolated vertex any gives it a neighbor (and a forced edge.) At this stage the vast majority, or at least an appreciable fraction of of vertices might have degree 3 or more and there will likely be exponentially many matchings. Jan 7 '15 at 10:02