4
$\begingroup$

Let $p<1$ be a constant. Consider two sets $A,B$, each with $n$ vertices. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears with probability $p$, independently of the remaining edges. From this question (which referenced a paper by Erdős and Rényi), we know that the probability that there exists a matching between $A$ and $B$ approaches $1$ as $n\rightarrow\infty$.

What can we say about the probability itself for any particular value of $n$? What is a lower bound for it, in terms of $n$ and $p$? I tried to deduce it from the above paper, but the way it is written it is quite hard to read off what this probability should be.

$\endgroup$
6
  • $\begingroup$ If perfect matching does not exist, by Hall theorem there are subsets $A',B'$ such that $|A'|+|B'|\geq n+1$ and there are no edges between $A',B'$. It looks likely that it is most probable when $A'=A$ or $B'=B$, and so the probability should behave as $2np^n$. $\endgroup$ Jan 28, 2016 at 23:21
  • $\begingroup$ @FedorPetrov I can see the factor $p^n$, but I think the number of pairs $(A',B')$ is much more than $2n$ $\endgroup$
    – Alexi
    Jan 29, 2016 at 0:07
  • $\begingroup$ If $A'=A$, $B'$ may be taken a single point, and vice versa. $\endgroup$ Jan 29, 2016 at 0:11
  • $\begingroup$ @FedorPetrov Yes, but we have to consider when $A'\neq A$ and $B'\neq B$ as well, no? $\endgroup$
    – Alexi
    Jan 29, 2016 at 0:16
  • 1
    $\begingroup$ Yes, but exponent of $p$ increases too much. $\endgroup$ Jan 29, 2016 at 0:35

1 Answer 1

2
+50
$\begingroup$

Let $q=1-p$ be a probability that there is no edge between two given vertices. For any subsets $A'\subset A$, $B'\subset B$, $|B'|+|A'|=n+1$, denote by $X(A',B')$ the following event: there are no edges between $A'$ and $B'$. The absence of a perfect matching is a union of these events by Hall theorem. Thus the following is an upper bound of the probability that there is no perfect matching: $$ {\rm prob}\, \bigcup X(A',B')\leqslant \sum {\rm prob}\, X(A',B')=\sum_{k=1}^n \binom{n}{k} \binom{n}{k-1} q^{k(n-k+1)}. $$ As usual, it may be improved by using the fact that these events are positively correlated by Kleitman lemma or how do you prefer to call it: $$ {\rm prob}\, \bigcup X(A',B')=1-{\rm prob}\,\bigcap \overline{X(A',B')}\leqslant 1-\prod {\rm prob}\,\overline{X(A',B')}=\\1- \prod_{k=1}^n (1-q^{k(n-k+1)})^{\binom{n}{k} \binom{n}{k-1}}. $$ As for the lower bound of the probability that there is no perfect matching, we may use part of inclusion-exclusion: say, if we consider only $2n$ events with $\min(|A'|,|B'|)=1$, denote them $Y_1,\dots,Y_{2n}$, we may use $$ {\rm prob}\, \bigcup Y_i\geqslant \sum {\rm prob}\, Y_i-\sum_{i<j} {\rm prob}\, Y_i\cap Y_j=2nq^n-n(n-1) q^{2n}-n^2q^{2n-1}. $$ I guess that in most asymptotic regimes these two bounds are enough, but if you see that no, please specify which dependence of $p$ and $n$ are you interested in.

$\endgroup$
4
  • $\begingroup$ Can we get an upper bound without a summation? $\endgroup$
    – Alexi
    Feb 3, 2016 at 15:52
  • $\begingroup$ Sorry, I do not quite understand what does it mean. $\endgroup$ Feb 3, 2016 at 16:03
  • $\begingroup$ Your upper bound $\sum_{k=1}^n\binom{n}{k}\binom{n}{k-1}q^{k(n-k+1)}$ -- it's not easy to see what this is (approximately). So I was asking whether we can derive a closed-form upper bound (i.e. not a summation) $\endgroup$
    – Alexi
    Feb 3, 2016 at 16:06
  • $\begingroup$ We may estimate summands, usually summands with $k=1,k=n$ are much greater then all the others. $\endgroup$ Feb 3, 2016 at 16:40

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.