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.

Improve this question
$\endgroup$
8
  • $\begingroup$ Where does the colouring come from? I guess every edge is coloured uniformly at random? $\endgroup$
    – Andrew D. King
    Commented Dec 11, 2010 at 18:45
  • $\begingroup$ Yes, the color of each edge is chosen uniformly at random. $\endgroup$
    – Marcin Kotowski
    Commented 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
    Commented 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$
    – Andrew D. King
    Commented 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$
    – Dave Pritchard
    Commented Dec 12, 2010 at 10:34

3 Answers 3

Reset to default
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.

Improve this answer
$\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$
    – Dave Pritchard
    Commented 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
    Commented 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.

Improve this answer
$\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$.

Improve this answer
$\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$
    – Dave Pritchard
    Commented 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$
    – Dave Pritchard
    Commented 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$
    – Aaron Meyerowitz
    Commented 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$
    – Aaron Meyerowitz
    Commented 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$
    – Dave Pritchard
    Commented Dec 13, 2010 at 11:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .