Rainbow Matchings: existence and counting

A perfect matching M in an edge–colored complete bipartite graph K n , n is rainbow if no pair of edges in M have the same color. We obtain asymptotic enumeration results for the number of rainbow matchings in terms of the maximum number of occurrences of a color. We also consider two natural models of random edge–colored K n , n and show that, if the number of colors is at least n, then there is whp a random matching. This in particular shows that almost every matrix in which every entry appears n times has a Latin transversal.