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?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ what if $p$ does depend on $n$? $\endgroup$ Commented Jan 15, 2015 at 11:21
$\begingroup$
$\endgroup$
6
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.
-
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$ Commented Jan 13, 2015 at 14:52
-
$\begingroup$ What if I changed the question to the expected size of the largest matching? $\endgroup$ Commented Jan 13, 2015 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$– PabloCommented Jan 13, 2015 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$– PabloCommented Jan 13, 2015 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$ Commented Jan 13, 2015 at 19:35