Rainbow matching

Every proper n-edge coloring of Kn,n corresponds to a Latin square of order n. A rainbow matching then corresponds to a transversal of the Latin square, meaning a selection of n positions, one in each row and each column, containing distinct entries.

A proper edge-coloring does not guarantee the existence of a perfect rainbow matching.

This invokes the question: when does a large rainbow matching is guaranteed to exist?

Translated into the rainbow matching terminology: A more general conjecture of Stein is that a rainbow matching of size n – 1 exists not only for a proper edge-coloring, but for any coloring in which each color appears on exactly n edges.

[2] Some weaker versions of these conjectures have been proved: Wang asked if there is a function f(d) such that every properly edge-colored graph G with minimum degree d and at least f(d) vertices must have a rainbow matching of size d.[9] Obviously at least 2d vertices are necessary, but how many are sufficient?

How many colors are needed in order to guarantee the existence of a rainbow matching?

Alon[13] showed that Drisko's theorem implies an older result[14] in additive number theory.

Aharoni, Berger, Chudnovsky, Howard and Seymour[17] proved that, in a general graph, 3n – 2 matchings (=colors) are always sufficient.

Any family of 2n fractional-matchings (=colors) of size at least n in an arbitrary graph has a rainbow-fractional-matching of size n.[18]: Thm.1.5  The 2n is the smallest possible for fractional matchings in arbitrary graphs: the extremal case is constructed using an odd-length cycle.

In other words, a collection F of edges admits a perfect fractional matching, if and only if 1v (the vector of |V| ones) is contained in the conical hull of the vectors 1e for e in F. Consider a graph with 2n vertices, and suppose there are 2n subsets of edges, each of which admits a perfect fractional matching (of size n).

By the colorful Caratheodory theorem, there exists a selection of 2n edges, one from each subset, that their conical hull contains 1v.

For a general r-uniform hypergraph (admitting a perfect matching of size n), the vectors 1e live in a (rn)-dimensional space.

In contrast, the case of rainbow integral matchings in r-uniform hypergraphs is much less understood.