Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose we have an $(n,n)$-bipartite graph with edges colored with $k$ colors. Is anything known about the existence of rainbow matchings (i.e. a matching that uses each color exactly once, for $k=n$) for a random bipartite graph (e.g. that for $k$ colors and more than $f(k,n)$ edges we get a rainbow matching with $p \rightarrow 1$)?

In the noncolored case, Hall's theorem makes proving this kind of results relatively simple, since we are interested in the non-existence of "no matching possible" witness (i.e. a subset that violates Hall condition) and we can use union bound to bound the probability from above (for $A_k$ = "k-th subset is a witness" give bound to $\mathbb{P}(\cup A_k)$). However, there is no simple condition of this kind equivalent to the existence of a rainbow matching.

share|improve this question
Where does the colouring come from? I guess every edge is coloured uniformly at random? –  Andrew D. King Dec 11 '10 at 18:45
Yes, the color of each edge is chosen uniformly at random. –  Marcin Kotowski Dec 11 '10 at 19:07
Do you mean that $k=n$? (otherwise I do not see how to interpret the "uses each color exactly once" requirement). –  fedja Dec 12 '10 at 3:24
@fejda I took that to mean it doesn't need to be a perfect matching. Consider the formulation of this as a question on the existence of an independent systems of representatives. Construct a graph with vertex set $(V_1, \ldots, V_k)$ corresponding to edges of colour $i$. Now make vertices $v_i \in V_i$ and $v_j \in V_j$ adjacent precisely if the corresponding edges share an endpoint in the bipartite graph. What you want is a matching hitting all the colours, i.e. a stable set intersecting each $V_i$ for $1 \le i \le k$. –  Andrew D. King Dec 12 '10 at 3:50
I left & deleted a comment due to confusion about reading the problem statement. It was a little confusing for me but I eventually understood you are picking a $f(k, n)$-edge subgraph of $K_{n, n}$ uniformly at random, and then assigning each edge one of $k$ colours uniformly at random; you want to compute $f$ so there is a $k$-edge rainbow matching w.h.p. Finally, you are considering only the asymptotics of $n \to \infty$, since otherwise "w.h.p" makes no sense. –  Dave Pritchard Dec 12 '10 at 10:34
show 3 more comments

3 Answers

Isn't this very much related to the problem of a transversal in a Latin square? Suppose we have an $(n,n)$ bipartite graph with $n$ edge colors, such that every vertex has one edge of each color. This is equivalent to an $n\times n$ Latin square. A rainbow matching is a transversal of the Latin square. There is a conjecture (due to Ryser) that every Latin square with $n$ odd has a transversal, that is, a perfect rainbow matching. For even $n$, the conjecture (due to Brualdi) is that it has a partial transversal of length $n-1$ (i.e., a rainbow matching of cardinality $n-1$). To indulge in a little self-promotion, the best known result is that there exists a partial transversal of length $n -O(\log^2 n)$. There are also a number of results about transversals and partial transversals in near-Latin squares, which will probably be relevant to rainbow matching questions.

I guess the relevant Latin square question would be: does a random Latin square have a transversal with high probability? I know extensive calculations have been done which suggest that the answer is yes. I don't know whether anybody has proven this.

share|improve this answer
Note that the "each vertex has one edge of each color" is not part of the original problem, so the "relevant Latin square question" is not a re-statement of what was discussed earlier. (But, of course similar methods could in principle apply, and they are indeed very much related.) –  Dave Pritchard Dec 13 '10 at 11:10
@Dave: Thanks for pointing that out. I really should have put it in my answer. –  Peter Shor Dec 13 '10 at 13:56
add comment

(This is not an answer to your question.)

Let $M$ be the $n\times n$ matrix with coefficients in $k[x_1, \ldots, x_n]$, whose $ij$-th entry is the variable $x_{color(i,j)}$. Then it is sufficient to prove that with high probability $det(M)$ has nonzero coefficient in $x_1\cdot\ldots\cdot x_n$ for $n$ sufficiently large (i.e., $det(M)$ is nonzero in $k[x_1, \ldots, x_n]/(x_1^2, \ldots, x_n^2)$). So maybe we could try to look at the partial differentials of $\det M$ and find a suitable witness this way? I have no idea if this can be useful.

share|improve this answer
add comment

I think that you need to formulate a more specific question. For fixed $k$, the $n$ is fairly irrelevant. Let $g(n)$ be a non-decreasing function which increases to infinity but exceedingly slowly (such as the inverse Ackerman function) then $f(n,k)=g(n)$ yields $k$ disjoint unequally colored edges with probability going to 1 (although for $k=6$, n will have to be unspeakable huge before $g(n)>5$).

At the other extreme, let $p_n$ be the probability that a random edge coloring of $K_{nn}$ (with n colors) yields a rainbow matching (with $n$ edges). I would have guessed that as $\lim_{n \rightarrow \infty}p_n=1$, and maybe that is true, but the small numbers point in the other direction. $p_1=1$, $p_2=\frac{7}{8}=87.5\%$ and $p_3=\frac{5090}{6561}=77.58\%$.

This still leaves a large middle ground with open questions (and even the $k=n$ case is not settled by what I wrote) later Indeed, it appears (see below) that right after $n=3$ it moves decisively towards $1$.

share|improve this answer
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. –  Dave Pritchard Dec 12 '10 at 10:26
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. –  Dave Pritchard Dec 12 '10 at 11:07
@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. –  Aaron Meyerowitz Dec 12 '10 at 15:31
@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. –  Aaron Meyerowitz Dec 12 '10 at 15:36
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. –  Dave Pritchard Dec 13 '10 at 11:12
show 2 more comments

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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