Rainbow matchings (in random graphs) - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T05:20:07Z http://mathoverflow.net/feeds/question/49054 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/49054/rainbow-matchings-in-random-graphs Rainbow matchings (in random graphs) Marcin Kotowski 2010-12-11T16:23:35Z 2010-12-13T02:55:35Z <p>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$)? </p> <p>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. </p> http://mathoverflow.net/questions/49054/rainbow-matchings-in-random-graphs/49080#49080 Answer by Piotr Achinger for Rainbow matchings (in random graphs) Piotr Achinger 2010-12-11T21:23:22Z 2010-12-11T21:23:22Z <p>(This is not an answer to your question.)</p> <p>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.</p> http://mathoverflow.net/questions/49054/rainbow-matchings-in-random-graphs/49127#49127 Answer by Aaron Meyerowitz for Rainbow matchings (in random graphs) Aaron Meyerowitz 2010-12-12T07:23:10Z 2010-12-12T15:38:36Z <p>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 <a href="http://en.wikipedia.org/wiki/Inverse_Ackermann_function#Inverse" rel="nofollow">inverse Ackerman function</a>) 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$). </p> <p>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\%$. </p> <p>This still leaves a large middle ground with open questions (and even the $k=n$ case is not settled by what I wrote) <strong>later</strong> Indeed, it appears (see below) that right after $n=3$ it moves decisively towards $1$.</p> http://mathoverflow.net/questions/49054/rainbow-matchings-in-random-graphs/49204#49204 Answer by Peter Shor for Rainbow matchings (in random graphs) Peter Shor 2010-12-13T02:43:34Z 2010-12-13T02:55:35Z <p>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 <em>transversal</em> 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 <a href="http://math.mit.edu/~shor/papers/Latin25.pdf" rel="nofollow">best known result</a> 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.</p> <p>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.</p>