Timeline for Expected matching in a bipartite graph
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 13, 2015 at 19:44 | comment | added | Pablo | @KevinP.Costello theoretically you are completely right and I see the difference, but my point was that if you have a good expectation and use Chebyshev (this distribution is fairly concrete) you can derive bounds on the size of the maximal matching. Maybe for this to work well you cannot let $p$ go to $0$ too fast. | |
| Jan 13, 2015 at 19:35 | comment | added | Kevin P. Costello | "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). | |
| Jan 13, 2015 at 15:00 | comment | added | Pablo | @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. | |
| Jan 13, 2015 at 14:55 | comment | added | Pablo | @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. | |
| Jan 13, 2015 at 14:53 | comment | added | Pavan Sangha | What if I changed the question to the expected size of the largest matching? | |
| Jan 13, 2015 at 14:52 | comment | added | Pavan Sangha | 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? | |
| Jan 13, 2015 at 14:23 | history | edited | Pablo | CC BY-SA 3.0 |
deleted 25 characters in body
|
| Jan 13, 2015 at 14:16 | history | answered | Pablo | CC BY-SA 3.0 |