1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ You need to take the sum over all choices of $S\subseteq A$ and $T\subseteq B$ with $|S|+|T|=\log^2(n)+1$ of the probability that there is no edge from $S$ to $T$, that is, $(1-p)^{|S|\,|T|}$. (It will make your life much easier if you give a name to $\log n$ and use that as the main parameter.) Other than that, it should work, even for a somewhat smaller $p$. $\endgroup$
    – Emil Jeřábek
    Commented Dec 7, 2014 at 18:40

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

For a lot on the subject, see Frieze and Pittel and references therein (in particular, I think the result you want is due to Erdos-Renyi(!)(1960, 1964); average degree $O(\log n)$ is enough.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Just to clarify: that’s average degree logarithmic in the size of the graph, so in the OP notation it’s $O(\log\log n)$. $\endgroup$
    – Emil Jeřábek
    Commented Dec 7, 2014 at 19:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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