Rainbow matching

Last updated

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.

Contents

Definition

Given an edge-colored graph G = (V,E), 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

On the top left a Latin square, on the bottom left the relative proper n-edge coloring. On the top right a Latin transversal and on the bottom right the relative rainbow matching. Rainbow matching.svg
On the top left a Latin square, on the bottom left the relative proper n-edge coloring. On the top right a Latin transversal and on the bottom right the relative rainbow matching.

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 transversal of the Latin square, meaning a selection of n positions, one in each row and each column, containing distinct entries.

This connection between transversals of Latin squares and rainbow matchings in Kn,n has inspired additional interest in the study of rainbow matchings in triangle-free graphs. [1]

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 (x1,y1) and (x2,y2) are colored green, and the edges (x1,y2) and (x2,y1) 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:

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:

Bounds depending on the minimum degree

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?

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 [12] 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 (=colors) of size n has a perfect rainbow matching (of size n). He applied this theorem to questions about group actions and difference sets.

Drisko also showed that 2n – 1 matchings may be necessary: consider a family of 2n – 2 matchings, of which n – 1 are { (x1, y1), (x2, y2), ..., (xn, yn)} and the other n – 1 are {(x1, y2), (x2, y3), …, (xn, y1) }. Then the largest rainbow matching is of size n – 1 (e.g. take one edge from each of the first n – 1 matchings).

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

In general bipartite graphs

Aharoni and Berger [15] 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 [16] showed that Drisko's extremal example is unique in any bipartite graph.

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 { (x1, x2), (y1, y2), (x2, x3), (y2, y3), … } and get a family of 2n – 1 matchings without any rainbow matching.

Aharoni, Berger, Chudnovsky, Howard and Seymour [17] proved that, in a general graph, 3n – 2 matchings (=colors) 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. [18]

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 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:

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 [15] is equivalent to the following. Let n be any positive integer. Given any family of 2n – 1 fractional-matchings (=colors) of size n in a bipartite graph, there exists a rainbow-fractional-matching of size n.

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 (=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.

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 (so each vector 1e has 2 ones and |V|-2 zeros). 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 (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). 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 (2n – 1)-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 (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 n be any positive rational number. Any family of ⌈r⋅n⌉ fractional-matchings (=colors) of size at least n in an r-uniform hypergraph has a rainbow-fractional-matching of size n. [18] : Thm.1.6  The ⌈r⋅n⌉ 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 (so a 2-partite hypergraph is a just bipartite graph). Let n be any positive integer. Any family of rn – r + 1 fractional-matchings (=colors) of size at least n in an r-partite hypergraph has a rainbow-fractional-matching of size n. [18] : Thm.1.7  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. [19]

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 r-uniform hypergraph (admitting a perfect matching of size n), the vectors 1e live in a (rn)-dimensional space. For an r-uniform r-partite hypergraph, the r-partiteness constraints imply that the vectors 1e live in a (rn – r + 1)-dimensional space.

Notes

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

Computation

Garey and Johnson have shown that computing a maximum rainbow matching is NP-complete even for edge-colored bipartite graphs. [20]

Applications

Rainbow matchings have been applied for solving packing problems. [21]

See also

Related Research Articles

In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph G = (V, E), a perfect matching in G is a subset M of edge set E, such that every vertex in the vertex set V is adjacent to exactly one edge in M.

In mathematics, Hall's marriage theorem, proved by Philip Hall, is a theorem with two equivalent formulations. In each case, the theorem gives a necessary and sufficient condition for an object to exist:

<span class="mw-page-title-main">Hypergraph</span> Generalization of graph theory

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.

<span class="mw-page-title-main">Bipartite graph</span> Graph divided into two independent sets

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets and , that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Complete bipartite graph</span> Bipartite graph where each node of 1st set is linked to all nodes of 2nd set

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.

<span class="mw-page-title-main">Edge coloring</span> Problem of coloring a graphs edges such that meeting edges do not match

In graph theory, a proper 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, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

<span class="mw-page-title-main">Graph factorization</span>

In graph theory, a factor of a graph G is a spanning subgraph, i.e., a subgraph that has the same vertex set as G. A k-factor of a graph is a spanning k-regular subgraph, and a k-factorization partitions the edges of the graph into disjoint k-factors. A graph G is said to be k-factorable if it admits a k-factorization. In particular, a 1-factor is a perfect matching, and a 1-factorization of a k-regular graph is a proper edge coloring with k colors. A 2-factor is a collection of cycles that spans all vertices of the graph.

<span class="mw-page-title-main">Kőnig's theorem (graph theory)</span> Theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs

In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

In graph theory, a matching in a hypergraph is a set of hyperedges, in which every two hyperedges are disjoint. It is an extension of the notion of matching in a graph.

In graph theory, a vertex cover in a hypergraph is a set of vertices, such that every hyperedge of the hypergraph contains at least one vertex of that set. It is an extension of the notion of vertex cover in a graph.

In graph theory, the term bipartite hypergraph describes several related classes of hypergraphs, all of which are natural generalizations of a bipartite graph.

In the mathematical field of graph theory, Hall-type theorems for hypergraphs are several generalizations of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Ofra Kessler, Ron Aharoni, Penny Haxell, Roy Meshulam, and others.

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.

In graph theory, a balanced hypergraph is a hypergraph that has several properties analogous to that of a bipartite graph.

In graph theory, Ryser's conjecture is a conjecture relating the maximum matching size and the minimum transversal size in hypergraphs.

In geometry, a truncated projective plane (TPP), also known as a dual affine plane, is a special kind of a hypergraph or geometric configuration that is constructed in the following way.

In graph theory, perfect matching in high-degree hypergraphs is a research avenue trying to find sufficient conditions for existence of a perfect matching in a hypergraph, based only on the degree of vertices or subsets of them.

In graph theory, a rainbow-independent set (ISR) is an independent set in a graph, in which each vertex has a different color.

In graph theory, Meshulam's game is a game used to explain a theorem of Roy Meshulam related to the homological connectivity of the independence complex of a graph, which is the smallest index k such that all reduced homological groups up to and including k are trivial. The formulation of this theorem as a game is due to Aharoni, Berger and Ziv.

References

  1. ↑ West, D.B. (2009), Rainbow Matchings
  2. 1 2 Aharoni, Ron; Berger, Eli; Kotlar, Dani; Ziv, Ran (2017-01-04). "On a conjecture of Stein". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. 87 (2): 203–211. doi:10.1007/s12188-016-0160-3. ISSN   0025-5858. S2CID   119139740.
  3. ↑ Stein, Sherman (1975-08-01). "Transversals of Latin squares and their generalizations". Pacific Journal of Mathematics. 59 (2): 567–575. doi: 10.2140/pjm.1975.59.567 . ISSN   0030-8730.
  4. ↑ Koksma, Klaas K. (1969-07-01). "A lower bound for the order of a partial transversal in a latin square". Journal of Combinatorial Theory. 7 (1): 94–95. doi: 10.1016/s0021-9800(69)80009-8 . ISSN   0021-9800.
  5. ↑ Woolbright, David E (1978-03-01). "An n × n Latin square has a transversal with at least n−n distinct symbols". Journal of Combinatorial Theory, Series A. 24 (2): 235–237. doi: 10.1016/0097-3165(78)90009-2 . ISSN   0097-3165.
  6. ↑ Hatami, Pooya; Shor, Peter W. (2008-10-01). "A lower bound for the length of a partial transversal in a Latin square". Journal of Combinatorial Theory, Series A. 115 (7): 1103–1113. doi: 10.1016/j.jcta.2008.01.002 . ISSN   0097-3165.
  7. ↑ Keevash, Peter; Pokrovskiy, Alexey; Sudakov, Benny; Yepremyan, Liana (2022-04-15). "New bounds for Ryser's conjecture and related problems". Transactions of the American Mathematical Society, Series B. 9 (8): 288–321. arXiv: 2005.00526 . doi: 10.1090/btran/92 . ISSN   2330-0000.
  8. ↑ Montgomery, Richard (2023). "A proof of the Ryser-Brualdi-Stein conjecture for large even n". arXiv: 2310.19779 [math.CO].
  9. ↑ Wang, Guanghui (2009), "Rainbow Matchings in Properly Edge Colored Graphs", The Electronic Journal of Combinatorics , 18 (1): 162
  10. ↑ Diemunsch, Jennifer; Ferrara, Michael; Lo, Allan; Moffatt, Casey; Pfender, Florian; Wenger, Paul S. (2012), "Rainbow Matchings of Size δ(G) in Properly Edge-Colored Graphs", The Electronic Journal of Combinatorics , 19 (2): 52, arXiv: 1108.2521 , doi: 10.37236/2443 , S2CID   119177198
  11. ↑ Gyarfas, Andras; Sarkozy, Gabor N. (2012). "Rainbow matchings and partial transversals of Latin squares". arXiv: 1208.5670 [CO math. CO].
  12. ↑ Drisko, Arthur A. (1998-11-01). "Transversals in Row-Latin Rectangles". Journal of Combinatorial Theory, Series A. 84 (2): 181–195. doi: 10.1006/jcta.1998.2894 . ISSN   0097-3165.
  13. ↑ Alon, Noga (2011). "Multicolored Matchings in Hypergraphs". Moscow Journal of Combinatorics and Number Theory. 1: 3–10.
  14. ↑ Flores, Carlos; Ordaz, Oscar (1996-05-01). "On the Erdös-Ginzburg-Ziv theorem". Discrete Mathematics. 152 (1–3): 321–324. doi: 10.1016/0012-365x(94)00328-g . ISSN   0012-365X.
  15. 1 2 Aharoni, Ron; Berger, Eli (2009-09-25). "Rainbow Matchings in $r$-Partite $r$-Graphs". The Electronic Journal of Combinatorics. 16 (1). doi: 10.37236/208 . ISSN   1077-8926.
  16. ↑ Aharoni, Ron; Kotlar, Dani; Ziv, Ran (2018-01-01). "Uniqueness of the extreme cases in theorems of Drisko and Erdős–Ginzburg–Ziv". European Journal of Combinatorics. 67: 222–229. doi: 10.1016/j.ejc.2017.08.008 . ISSN   0195-6698. S2CID   38268762.
  17. ↑ Aharoni, Ron; Berger, Eli; Chudnovsky, Maria; Howard, David; Seymour, Paul (2019-06-01). "Large rainbow matchings in general graphs". European Journal of Combinatorics. 79: 222–227. arXiv: 1611.03648 . doi:10.1016/j.ejc.2019.01.012. ISSN   0195-6698. S2CID   42126880.
  18. 1 2 3 4 Aharoni, Ron; Holzman, Ron; Jiang, Zilin (2019-10-29). "Rainbow Fractional Matchings". Combinatorica. 39 (6): 1191–1202. arXiv: 1805.09732 . doi:10.1007/s00493-019-4019-y. ISSN   0209-9683. S2CID   119173114.
  19. ↑ Füredi, Zoltán (1989-05-01). "Covering the complete graph by partitions". Discrete Mathematics. 75 (1–3): 217–226. doi: 10.1016/0012-365x(89)90088-5 . ISSN   0012-365X.
  20. ↑ Garey, M. R.; Johnson, D. S. (1979). Victor Klee (ed.). Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. San Francisco, Calif.: W. H. Freeman and Co. pp.  x+338. ISBN   0-7167-1045-5. MR   0519066.
  21. ↑ Bannach, Max; Berndt, Sebastian; Maack, Marten; Mnich, Matthias; Lassota, Alexandra; Rau, Malin; Skambath, Malte (2020-07-06). "Solving Packing Problems with Few Small Items Using Rainbow Matchings". arXiv: 2007.02660 [cs.DS].
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.