Rainbow matching
In the mathematical discipline of graph theory, a rainbow matching in an edge-colored graph is a matching in which all the edges have distinct colors.
Definition
Given an edge-colored graph G =, a rainbow matching M in G is a set of pairwise non-adjacent edges, that is, no two edges share a common vertex, such that all the edges in the set have distinct colors.A maximum rainbow matching is a rainbow matching that contains the largest possible number of edges.
History
Rainbow matchings are of particular interest given their connection to transversals of Latin squares.Denote by Kn,n the complete bipartite graph on n+n vertices. Every proper n-edge coloring of Kn,n corresponds to a Latin square of order n. A rainbow matching then corresponds to a Latin transversal of the Latin square, meaning a selection of n positions, one in each row and each column, containing distinct entries.
This connection between Latin transversals and rainbow matchings in Kn,n has inspired additional interest in the study of rainbow matchings in triangle-free graphs.
Existence when each edge has a single color
An edge-coloring is called proper if each edge has a single color, and each two edges of the same color have no vertex in common.A proper edge-coloring does not guarantee the existence of a perfect rainbow matching. For example, consider the graph K2,2 - the complete bipartite graph on 2+2 vertices. Suppose the edges and are colored green, and the edges and are colored blue. This is a proper coloring, but there are only two perfect matchings, and each of them is colored by a single color. This invokes the question: when does a large rainbow matching is guaranteed to exist?
Bounds depending only on the number of vertices
Much of the research on this question was published using the terminology of Latin transversals in Latin squares. Translated into the rainbow matching terminology:- In 1967, H. J. Ryser conjectured that, when n is odd, every proper edge-coloring of Kn,n has a rainbow matching of size n.
- In 1975, S. K. Stein and Brualdi conjectured that, when n is even, every proper edge-coloring of Kn,n has a rainbow matching of size n-1..
Some weaker versions of these conjectures have been proved:
- Every proper edge-coloring of Kn,n has a rainbow matching of size 2n/3.
- Every proper edge-coloring of Kn,n has a rainbow matching of size n - sqrt.
- Every proper edge-coloring of Kn,n has a rainbow matching of size n - 11 log22.
Bounds depending on the minimum degree
- Diemunsch, et al. answered this question in the affirmitive and showed that given a properly edge-colored graph G with minimum degree d and order at least f = 98δ/23, there exists a rainbow matching of size d in G.
- This bound was later improved to f = 4d − 3 by Andras Gyarfas and Gabor N. Sarkozy. They also show that any graph with at least 2d vertices has a rainbow matching of size at least d-2d2/3. These are the best known estimate to date.
Existence when the same edge may have different colors
In complete bipartite graphs
Drisko studied this question using the terminology of Latin rectangles. He proved that, for any n≤k, in the complete bipartite graph Kn,k, any family of 2n-1 matchings of size n has a perfect rainbow matching. He applied this theorem to questions about group actions and difference sets.Drisko also showed that 2n-1 matchings may be necessary: consider a fam
Alon showed that Drisko's theorem implies an older result in additive number theory.
In general bipartite graphs
Aharoni and Berger generalized Drisko's theorem to any bipartite graph, namely: any family of 2n-1 matchings of size n in a bipartite graph has a rainbow matching of size n.Aharoni, Kotlar and Ziv showed that Drisko's extremal example is uni
In general graphs
In general graphs, 2n-1 matchings are no longer sufficient. When n is even, one can add to Drisko's example the matching and get a family of 2n-1 matchings without any rainbow matching.Aharoni, Berger, Chudnovsky, Howard and Seymour proved that, in a general graph, 3n-2 matchings are always sufficient. It is not known whether this is tight: currently the best lower bound for even n is 2n and for odd n it is 2n-1.
Rainbow fractional matchings
A fractional matching is a set of edges with a non-negative weight assigned to each edge, such that the sum of weights adjacent to each edge is at most 1. The size of a fractional matching is the sum of weights of all edges. It is a generalization of a matching, and can be used to generalize both the colors and the rainbow matching:- Instead of requiring that each color be a matching of size n, the requirement is weakened: each "color" can be an arbitrary set of edges, but it should admit a fractional matching of size at least n.
- Instead of looking for a rainbow matching, we look for a rainbow fractional matching - a fractional matching in which each edge with a positive weight has a different color.
Aharoni, Holzman and Jiang extend this theorem to arbitrary graphs as follows. Let n be any positive integer or half-integer. Any family of 2n fractional-matchings of size at least n in an arbitrary graph has a rainbow-fractional-matching of size n. The 2n is the smallest possible for fractional matchings in arbitrary graphs: the extremal case is constructed using an odd-length cycle.
Partial proof
For the case of perfect fractional matchings, both the above theorems can derived from the colorful Caratheodory theorem.For every edge e in E, let 1e be a vector of size |V|, where for each vertex v in V, element v in 1e equals 1 if e is adjacent to v, and 0 otherwise. Every fractional matching corresponds to a conical combination of edges, in which each element is at most 1. A conical combination in which each element is exactly 1 corresponds to a perfect fractional matching. In other words, a collection F of edges admits a perfect fractional matching, if and only if 1V 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. This means that the vector 1V is in the conical hull of each of these n subsets. By the colorful Caratheodory theorem, there exists a selection of 2n edges, one from each subset, that their conical hull contains 1V. This corresponds to a rainbow perfect fractional matching. The expression 2n is the dimension of the vectors 1e - each vector has 2n elements.
Now, suppose that the graph is bipartite. In a bipartite graph, there is a constraint on the vectors 1e : the sum of elements corresponding to each part of the graph must be 1. Therefore, the vectors 1e live in a -dimensional space. Therefore, the same argument as above holds when there are only 2n-1 subsets of edges.
Rainbow matching in hypergraphs
An r-uniform hypergraph is a set of hyperedges each of which contains exactly r vertices. Aharoni, Holzman and Jiang extend their theorem to such hypergraphs as follows. Let n be any positive rational number. Any family of fractional-matchings of size at least n in an r-uniform hypergraph has a rainbow-fractional-matching of size n. The is the smallest possible when n is an integer.An r-partite hypergraph is an r-uniform hypergraph in which the vertices are partitioned into r disjoint sets and each hyperedge contains exactly one vertex of each set. Let n be any positive integer. Any family of rn-r+1 fractional-matchings of size at least n in an r-partite hypergraph has a rainbow-fractional-matching of size n. The rn-r+1 is the smallest possible: the extremal case is when n=r-1 is a prime power, and all colors are edges of the truncated projective plane of order n. So each color has n2=rn-r+1 edges and a fractional matching of size n, but any fractional matching of that size requires all rn-r+1 edges.