Rainbow matchings (in random graphs) - MathOverflow

Rainbow matchings (in random graphs)

2010-12-11T16:23:35Z

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.

Answer by Piotr Achinger for Rainbow matchings (in random graphs)

2010-12-11T21:23:22Z

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

Answer by Aaron Meyerowitz for Rainbow matchings (in random graphs)

2010-12-12T07:23:10Z

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

Answer by Peter Shor for Rainbow matchings (in random graphs)

2010-12-13T02:43:34Z

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.