Timeline for Rainbow matchings (in random graphs)
Current License: CC BY-SA 2.5
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 21, 2010 at 21:11 | comment | added | Omer | The second moment method does work here. Two random matchings have roughly Poi$(1)$ edges in common, so the events that they are rainbow are nearly independent. | |
| Dec 16, 2010 at 9:15 | comment | added | Dave Pritchard | I thought some more about the $f(n, n)$ problem and got as far as the following. A natural approach is to build a rainbow matching as large as possible (maybe using "augmenting paths") while exposing the colour of one edge at a time. I think this easily gives a rainbow matching of size $n - O(\sqrt{n})$ (w/o augmenting paths). But the last bits are very difficult; even in the unlikely scenario that the first $n-1$ edges we look at form a rainbow matching, I can't figure out any exposure argument to get a rainbow matching of size $n$. | |
| Dec 13, 2010 at 11:12 | comment | added | Dave Pritchard | Thanks for the clarification; I missed earlier, but see now, that without the $\omega(n)$ term, the probability of a bad set of coupons is a fixed positive number depending on $k$ but not $n$, so it's really needed. The calculation is great too. | |
| Dec 12, 2010 at 15:38 | history | edited | Aaron Meyerowitz | CC BY-SA 2.5 |
update
|
| Dec 12, 2010 at 15:36 | comment | added | Aaron Meyerowitz | @Dave and for the first part, I agree that it is the coupon collector problem so $k \log k$ is relevant. One would need $f(n,k)=k\log k +\alpha_{n}k$ with $\alpha_n$ going to infinity as $n$ does. | |
| Dec 12, 2010 at 15:31 | comment | added | Aaron Meyerowitz | @Dave good call. For $n=4$ it seems (from random trials) that one gets a rainbow perfect matching somewhat more than 99.55% (but probably less than 99.56%) of he time. | |
| Dec 12, 2010 at 11:07 | comment | added | Dave Pritchard | The second question, whether $f(n, n)$ exists, is quite interesting! (I.e., whether $K_{n, n}$ with a random $n$-colouring a.a.s has a rainbow perfect matching.) It looks to me that the expected number of rainbow perfect matchings is $(n!)^2/n^n$ which is huge; nonetheless the first thing I tried to prove that 1 exists a.a.s, the second moment method, doesn't seem to help. | |
| Dec 12, 2010 at 10:26 | comment | added | Dave Pritchard | Actually, with the first part, you can deduce $f(n, k) = \Theta(k \log k)$ as $n \to \infty$ for any fixed $k$ since the edges become disjoint w.h.p, and then it reduces to the coupon collector problem with $k$ coupons. | |
| Dec 12, 2010 at 9:18 | history | edited | Aaron Meyerowitz | CC BY-SA 2.5 |
deleted 3 characters in body
|
| Dec 12, 2010 at 7:23 | history | answered | Aaron Meyerowitz | CC BY-SA 2.5 |