In the mathematical discipline of

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, 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 , a rainbow matching in 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 square In combinatorics and in experimental design, a Latin square is an ''n'' × ''n'' array filled with ''n'' different symbols, each occurring exactly once in each row and exactly once in each column. An example of a 3×3 Latin sq ...

s. Denote by the

complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory ...

on vertices. Every proper -

edge coloring In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue ...

of corresponds to a Latin square of order . A rainbow matching then corresponds to a transversal of the Latin square, meaning a selection of positions, one in each row and each column, containing distinct entries. This connection between transversals of Latin squares and rainbow matchings in has inspired additional interest in the study of rainbow matchings in

triangle-free graph In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with ...

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 : 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 Herbert John Ryser (July 28, 1923 – July 12, 1985) was a professor of mathematics, widely regarded as one of the major figures in combinatorics in the 20th century. * In 1975, S. K. Stein and Brualdi conjectured that, when is even, every proper edge-coloring of has a rainbow matching of size . (it is known that a rainbow matching of size need not exist in this case). A more general conjecture of Stein is that a rainbow matching of size exists not only for a proper edge-coloring, but for any coloring in which each color appears on exactly edges. Some weaker versions of these conjectures have been proved: * Every proper edge-coloring of has a rainbow matching of size . * Every proper edge-coloring of has a rainbow matching of size * Every proper edge-coloring of has a rainbow matching of size .

Bounds depending on the minimum degree

Wang asked if there is a function such that every properly edge-colored graph with minimum

degree Degree may refer to: As a unit of measurement * Degree (angle), a unit of angle measurement ** Degree of geographical latitude ** Degree of geographical longitude * Degree symbol (°), a notation used in science, engineering, and mathematics ...

and at least vertices must have a rainbow matching of size . Obviously at least vertices are necessary, but how many are sufficient? * Diemunsch, et al. answered this question in the affirmative and showed that given a properly edge-colored graph with minimum degree and order at least , there exists a rainbow matching of size in . * This bound was later improved to by Andras Gyarfas and Gabor N. Sarkozy. They also show that any graph with at least vertices has a rainbow matching of size at least . These are the best known estimate to date.

Existence when the same edge may have different colors

Suppose that each edge may have several different colors, while each two edges of the same color must still have no vertex in common. In other words, each color is a matching. How many colors are needed in order to guarantee the existence of a rainbow matching?

In complete bipartite graphs

Drisko studied this question using the terminology of

Latin rectangle In combinatorial mathematics, a Latin rectangle is an matrix (where ), using symbols, usually the numbers or as its entries, with no number occurring more than once in any row or column. An Latin rectangle is called a Latin square. An example ...

s. He proved that, for any , in the complete bipartite graph , any family of matchings (=colors) of size has a perfect rainbow matching (of size ). He applied this theorem to questions about

group action In mathematics, a group action on a space is a group homomorphism of a given group into the group of transformations of the space. Similarly, a group action on a mathematical structure is a group homomorphism of a group into the automorphism ...

s and

difference set In combinatorics, a (v,k,\lambda) difference set is a subset D of size k of a group G of order v such that every nonidentity element of G can be expressed as a product d_1d_2^ of elements of D in exactly \lambda ways. A difference set D is said ...

s. Drisko also showed that matchings may be necessary: consider a family of matchings, of which are and the other are Then the largest rainbow matching is of size (e.g. take one edge from each of the first matchings). Alon showed that Drisko's theorem implies an older result in

additive number theory Additive number theory is the subfield of number theory concerning the study of subsets of integers and their behavior under addition. More abstractly, the field of additive number theory includes the study of abelian groups and commutative semigr ...

In general bipartite graphs

Aharoni and Berger generalized Drisko's theorem to any bipartite graph, namely: any family of matchings of size in a bipartite graph has a rainbow matching of size . Aharoni, Kotlar and Ziv showed that Drisko's extremal example is unique in any bipartite graph.

In general graphs

In general graphs, matchings are no longer sufficient. When is even, one can add to Drisko's example the matching and get a family of matchings without any rainbow matching. Aharoni, Berger, Chudnovsky, Howard and Seymour proved that, in a general graph, matchings (=colors) are always sufficient. It is not known whether this is tight: currently the best lower bound for even is and for odd it is .

Rainbow fractional matchings

fractional matching In graph theory, a fractional matching is a generalization of a matching in which, intuitively, each vertex may be broken into fractions that are matched to different neighbor vertices. Definition Given a graph ''G'' = (''V'', ''E''), a fraction ...

is a set of edges with a non-negative weight assigned to each edge, such that the sum of weights adjacent to each vertex 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 , the requirement is weakened: each "color" can be an arbitrary set of edges, but it should admit a fractional matching of size at least . * 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. It is known that, in a bipartite graph, the maximum fractional matching size equals the maximum matching size. Therefore, the theorem of Aharoni and Berger is equivalent to the following. Let be any positive integer. Given any family of fractional-matchings (=colors) of size in a bipartite graph, there exists a rainbow-fractional-matching of size . Aharoni, Holzman and Jiang extend this theorem to arbitrary graphs as follows. Let be any positive integer or half-integer. Any family of fractional-matchings (=colors) of size at least in an arbitrary graph has a rainbow-fractional-matching of size . The 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 in , let be a vector of size , where for each vertex in , element in equals 1 if is adjacent to , and 0 otherwise (so each vector has 2 ones and -2 zeros). Every fractional matching corresponds to a

conical combination Given a finite number of vectors x_1, x_2, \dots, x_n in a real vector space, a conical combination, conical sum, or weighted sum''Convex Analysis and Minimization Algorithms'' by Jean-Baptiste Hiriart-Urruty, Claude Lemaréchal, 1993, pp. 101, 102/ ...

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 of edges admits a perfect fractional matching, if and only if (the vector of ones) is contained in the

conical hull Given a finite number of vectors x_1, x_2, \dots, x_n in a real vector space, a conical combination, conical sum, or weighted sum''Convex Analysis and Minimization Algorithms'' by Jean-Baptiste Hiriart-Urruty, Claude Lemaréchal, 1993, pp. 101, 102/ ...

of the vectors for in . Consider a graph with vertices, and suppose there are subsets of edges, each of which admits a perfect fractional matching (of size ). This means that the vector is in the conical hull of each of these subsets. By the colorful Caratheodory theorem, there exists a selection of edges, one from each subset, that their conical hull contains . This corresponds to a rainbow perfect fractional matching. The expression is the dimension of the vectors - each vector has elements. Now, suppose that the graph is bipartite. In a bipartite graph, there is a constraint on the vectors : the sum of elements corresponding to each part of the graph must be 1. Therefore, the vectors live in a -dimensional space. Therefore, the same argument as above holds when there are only subsets of edges.

Rainbow matching in hypergraphs

An ''r-uniform

hypergraph In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices. Formally, an undirected hypergraph H is a pair H = (X,E) wh ...

'' is a set of hyperedges each of which contains exactly vertices (so a 2-uniform hypergraph is a just a graph without self-loops). Aharoni, Holzman and Jiang extend their theorem to such hypergraphs as follows. Let be any positive rational number. Any family of fractional-matchings (=colors) of size at least in an -uniform hypergraph has a rainbow-fractional-matching of size . The is the smallest possible when is an integer. An ''r-partite hypergraph'' is an -uniform hypergraph in which the vertices are partitioned into disjoint sets and each hyperedge contains exactly one vertex of each set (so a 2-partite hypergraph is a just bipartite graph). Let be any positive integer. Any family of fractional-matchings (=colors) of size at least in an -partite hypergraph has a rainbow-fractional-matching of size . The is the smallest possible: the extremal case is when is a

prime power In mathematics, a prime power is a positive integer which is a positive integer power of a single prime number. For example: , and are prime powers, while , and are not. The sequence of prime powers begins: 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17 ...

, and all colors are edges of the truncated

projective plane In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines (namely, parallel lines) that do ...

of order . So each color has edges and a fractional matching of size , but any fractional matching of that size requires all edges.

Partial proof

For the case of perfect fractional matchings, both the above theorems can derived from the colorful caratheodory theorem in the previous section. For a general -uniform hypergraph (admitting a perfect matching of size ), the vectors live in a -dimensional space. For an -uniform -partite hypergraph, the -partiteness constraints imply that the vectors live in a -dimensional space.

Notes

The above results hold only for rainbow ''fractional'' matchings. In contrast, the case of rainbow ''integral'' matchings in -uniform hypergraphs is much less understood. The number of required matchings for a rainbow matching of size grows at least exponentially with .

Computation

Garey and

Johnson Johnson is a surname of Anglo-Norman origin meaning "Son of John". It is the second most common in the United States and 154th most common in the world. As a common family name in Scotland, Johnson is occasionally a variation of ''Johnston'', a ...

have shown that computing a maximum rainbow matching is

NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...

even for edge-colored

bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...

Applications

Rainbow matchings have been applied for solving

packing problems Packing problems are a class of optimization problems in mathematics that involve attempting to pack objects together into containers. The goal is to either pack a single container as densely as possible or pack all objects using as few conta ...

References

{{DEFAULTSORT:Rainbow Matching Graph theory objects Graph coloring Rainbow problems

Definition

History

Existence when each edge has a single color

Bounds depending only on the number of vertices

Bounds depending on the minimum degree

Existence when the same edge may have different colors

In complete bipartite graphs

In general bipartite graphs

In general graphs

Rainbow fractional matchings

Partial proof

Rainbow matching in hypergraphs

Partial proof

Notes

Computation

Applications

See also

References