1
$\begingroup$

Consider a random bipartite graph constructed on vertex classes of size $n$ with each edge present independently with probability $p$. How could I go about calculating the size of the expected matching?

$\endgroup$
1
$\begingroup$

If $p$ is fixed and does not depend on $n$, then by a result of Frieze and Melsted (http://www.math.cmu.edu/~af1p/Texfiles/cuckoo2.pdf), the probability that there exists a perfect matching is 1-o(1). In another word, the size of the maximal matching is $n$ with high probability.

The paper of Frieze and Melsted has the following theorem: Let $\Gamma$ be a bipartite graph chosen uniformly from the sets of graphs with bipartition $L$, $R$, $|L| = n$,$|R| = m$ such that each vertex of $L$ has degree $d \ge 3$ and each vertex of $R$ has degree at least two. Then with high probability, the size of the maximum matching in $\Gamma$ is $\min \{m, n\}$.

Though the above theorem does not directly answer the question here, in our setting we have $m = n$ and the mean degree of each vertex is $pn \gg 3$. So the conditions of the theorem should be satisfied with high probability and there exists a perfect matching.

$\endgroup$
  • $\begingroup$ what if $p$ does depend on $n$? $\endgroup$ – Pavan Sangha Jan 15 '15 at 11:21
0
$\begingroup$

Suppose that the expected number of matchings of size $r$ for some $r \leq n$ is at least $1$. That is, we expect to have a matching of size $r$. By linearity of expectation:

$$1 \leq {n \choose r}^2 r! \ {p^{r}}$$ that is you need to find the asymptotic for $r$ to satisfy this.

$\endgroup$
  • 1
    $\begingroup$ Ok just to clarify your calculation, the expected number of $r$-matchings is $\binom{n}{r}^{2}r!p^{r}$ this follows because there are $\binom{n}{r}^{2}$ ways to select a set of $r$ vertices from each class, then there are $r!$ possible matchings each which occur with probability $p^{r}$ Is this correct? $\endgroup$ – Pavan Sangha Jan 13 '15 at 14:52
  • $\begingroup$ What if I changed the question to the expected size of the largest matching? $\endgroup$ – Pavan Sangha Jan 13 '15 at 14:53
  • $\begingroup$ @PavanSangha you got my calculation right. This "treats" the case of the largest matching because the largest matching to occur will be typically with the largest $r$ such that the inequality holds. $\endgroup$ – Pablo Jan 13 '15 at 14:55
  • $\begingroup$ @PavanSangha if you wish to make this more accurate, you need to calculate the probabilities of the maximal matching being of any given size. You can do this by taking my expectation and plugging it into some inequality (Markov, Chebyshev). Then will you be able to estimate the expectations using the estimates on these probabilities. $\endgroup$ – Pablo Jan 13 '15 at 15:00
  • 3
    $\begingroup$ "The expected number of matchings is at least $1$" and "We expect to have a matching of size $r$" are not the same thing! For example, consider the case where $r=n$ and $p=\frac{10}{n}$. Then the expected number of matchings tends to infinity exponentially with $n$, but it can be shown that there will almost surely not be a matching (e.g. because with high probability there is an isolated vertex in the graph; this ties in with some of Pavan's other questions). $\endgroup$ – Kevin P. Costello Jan 13 '15 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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