11
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Where does the colouring come from? I guess every edge is coloured uniformly at random? $\endgroup$ Dec 11, 2010 at 18:45
  • $\begingroup$ Yes, the color of each edge is chosen uniformly at random. $\endgroup$ Dec 11, 2010 at 19:07
  • $\begingroup$ Do you mean that $k=n$? (otherwise I do not see how to interpret the "uses each color exactly once" requirement). $\endgroup$
    – fedja
    Dec 12, 2010 at 3:24
  • $\begingroup$ @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$. $\endgroup$ Dec 12, 2010 at 3:50
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 12, 2010 at 10:34

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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.) $\endgroup$ Dec 13, 2010 at 11:10
  • $\begingroup$ @Dave: Thanks for pointing that out. I really should have put it in my answer. $\endgroup$
    – Peter Shor
    Dec 13, 2010 at 13:56
1
$\begingroup$

(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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 12, 2010 at 10:26
  • 2
    $\begingroup$ 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. $\endgroup$ Dec 12, 2010 at 11:07
  • 1
    $\begingroup$ @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. $\endgroup$ Dec 12, 2010 at 15:31
  • 1
    $\begingroup$ @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. $\endgroup$ Dec 12, 2010 at 15:36
  • $\begingroup$ 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. $\endgroup$ Dec 13, 2010 at 11:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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