rainbow matching

Given an edge-colored graph {{math|1=G = (V,E)}}, a rainbow matching {{mvar|M}} in {{mvar|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.

File:Rainbow matching.svg, on the bottom left the relative proper {{mvar|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 {{math|K{{sub|n,n}}}} the complete bipartite graph on {{math|n + n}} vertices. Every proper {{mvar|n}}-edge coloring of {{math|K{{sub|n,n}}}} corresponds to a Latin square of order {{mvar|n}}. A rainbow matching then corresponds to a transversal of the Latin square, meaning a selection of {{mvar|n}} positions, one in each row and each column, containing distinct entries.

This connection between transversals of Latin squares and rainbow matchings in {{math|K{{sub|n,n}}}} has inspired additional interest in the study of rainbow matchings in triangle-free graphs.

{{citation

| last1 = West | first1 = D.B.

| year = 2009

| title = Rainbow Matchings

| url = http://www.math.uiuc.edu/~west/regs/rainmat.html}}

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 {{math|K{{sub|2,2}}}}: the complete bipartite graph on 2+2 vertices. Suppose the edges {{math|(x{{sub|1}},y{{sub|1}})}} and {{math|(x{{sub|2}},y{{sub|2}})}} are colored green, and the edges {{math|(x{{sub|1}},y{{sub|2}})}} and {{math|(x{{sub|2}},y{{sub|1}})}} 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?

{{See also|Hall-type theorems for hypergraphs#More conditions from rainbow matchings}}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 {{mvar|n}} is odd, every proper edge-coloring of {{math|K{{sub|n,n}}}} has a rainbow matching of size {{mvar|n}}.{{Cite journal|last1=Aharoni|first1=Ron|last2=Berger|first2=Eli|last3=Kotlar|first3=Dani|last4=Ziv|first4=Ran|date=2017-01-04|title=On a conjecture of Stein|journal=Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg|volume=87|issue=2|pages=203–211|doi=10.1007/s12188-016-0160-3|s2cid=119139740|issn=0025-5858}}
• In 1975, S. K. Stein and Brualdi conjectured that, when {{mvar|n}} is even, every proper edge-coloring of {{math|K{{sub|n,n}}}} has a rainbow matching of size {{math|n – 1}}.{{Cite journal|last=Stein|first=Sherman|date=1975-08-01|title=Transversals of Latin squares and their generalizations|journal=Pacific Journal of Mathematics|volume=59|issue=2|pages=567–575|doi=10.2140/pjm.1975.59.567|issn=0030-8730|doi-access=free}} (it is known that a rainbow matching of size {{mvar|n}} need not exist in this case).

A more general conjecture of Stein is that a rainbow matching of size {{math|n – 1}} exists not only for a proper edge-coloring, but for any coloring in which each color appears on exactly {{mvar|n}} edges.

Some weaker versions of these conjectures have been proved:

• Every proper edge-coloring of {{math|K{{sub|n,n}}}} has a rainbow matching of size {{math|2n/3}}.{{Cite journal|last=Koksma|first=Klaas K.|date=1969-07-01|title=A lower bound for the order of a partial transversal in a latin square|journal=Journal of Combinatorial Theory|volume=7|issue=1|pages=94–95|doi=10.1016/s0021-9800(69)80009-8|issn=0021-9800|doi-access=free}}
• Every proper edge-coloring of {{math|K{{sub|n,n}}}} has a rainbow matching of size {{tmath|n - \sqrt{n}.}}{{Cite journal|last=Woolbright|first=David E|date=1978-03-01|title=An n × n Latin square has a transversal with at least n−n distinct symbols|journal=Journal of Combinatorial Theory, Series A|volume=24|issue=2|pages=235–237|doi=10.1016/0097-3165(78)90009-2|issn=0097-3165|doi-access=free}}
• Every proper edge-coloring of {{math|K{{sub|n,n}}}} has a rainbow matching of size {{math|n – 11 log{{sub|2}}{{sup|2}}(n)}}.{{Cite journal|last1=Hatami|first1=Pooya|last2=Shor|first2=Peter W.|date=2008-10-01|title=A lower bound for the length of a partial transversal in a Latin square|journal=Journal of Combinatorial Theory, Series A|volume=115|issue=7|pages=1103–1113|doi=10.1016/j.jcta.2008.01.002|issn=0097-3165|doi-access=free}}
• Every proper edge-coloring of {{math|K{{sub|n,n}}}} has a rainbow matching of size {{math|n – O(log n/log log n)}}.{{Cite journal |last1=Keevash |first1=Peter |last2=Pokrovskiy |first2=Alexey |last3=Sudakov |first3=Benny |last4=Yepremyan |first4=Liana |date=2022-04-15 |title=New bounds for Ryser's conjecture and related problems |url=https://www.ams.org/btran/2022-09-08/S2330-0000-2022-00092-3/ |journal=Transactions of the American Mathematical Society, Series B |language=en |volume=9 |issue=8 |pages=288–321 |doi=10.1090/btran/92 |issn=2330-0000|doi-access=free |arxiv=2005.00526 }}
• Every proper edge-coloring of {{math|K{{sub|n,n}}}} has a rainbow matching of size {{math|n – 1}}.{{Cite arXiv |last=Montgomery |first=Richard |date=2023 |title=A proof of the Ryser-Brualdi-Stein conjecture for large even n |class=math.CO |eprint=2310.19779}} (Preprint)

Wang asked if there is a function {{math|f(d)}} such that every properly edge-colored graph {{mvar|G}} with minimum degree {{mvar|d}} and at least {{math|f(d)}} vertices must have a rainbow matching of size {{mvar|d}}.

{{citation

| last1 = Wang | first1 = Guanghui

| url = http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p162

| issue = 1

| journal = The Electronic Journal of Combinatorics

| pages = 162

| title = Rainbow Matchings in Properly Edge Colored Graphs

| volume = 18

| year = 2009}} Obviously at least {{math|2d}} 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 {{mvar|G}} with minimum degree {{mvar|d}} and order at least {{math|1=f(d) = 98δ/23}}, there exists a rainbow matching of size {{mvar|d}} in {{mvar|G}}.

{{citation

| last1 = Diemunsch | last2 = Ferrara | last3 = Lo | last4 = Moffatt | last5 = Pfender | last6 = Wenger

| first1 = Jennifer | first2 = Michael | first3 = Allan | first4 = Casey | first5 = Florian | first6 = Paul S.

| url = http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i2p52

| issue = 2

| journal = The Electronic Journal of Combinatorics

| pages = 52

| title = Rainbow Matchings of Size δ(G) in Properly Edge-Colored Graphs

| volume = 19

| year = 2012| doi = 10.37236/2443 | s2cid = 119177198 | doi-access = free | arxiv = 1108.2521 }}

• This bound was later improved to {{math|1=f(d) = 4d – 3}} by Andras Gyarfas and Gabor N. Sarkozy.

{{cite arXiv | last1 = Gyarfas | last2 = Sarkozy | first1 = Andras | first2 = Gabor N. | eprint = 1208.5670 | class = math. CO | title = Rainbow matchings and partial transversals of Latin squares | year = 2012}} They also show that any graph with at least {{math|2d}} vertices has a rainbow matching of size at least {{math|d – 2d{{sup|2/3}}}}. These are the best known estimate to date.

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?

Drisko{{Cite journal|last=Drisko|first=Arthur A.|date=1998-11-01|title=Transversals in Row-Latin Rectangles|journal=Journal of Combinatorial Theory, Series A|volume=84|issue=2|pages=181–195|doi=10.1006/jcta.1998.2894|issn=0097-3165|doi-access=free}} studied this question using the terminology of Latin rectangles. He proved that, for any {{math|n ≤ k}}, in the complete bipartite graph {{math|K{{sub|n,k}}}}, any family of {{math|2n – 1}} matchings (=colors) of size {{mvar|n}} has a perfect rainbow matching (of size {{mvar|n}}). He applied this theorem to questions about group actions and difference sets.

Drisko also showed that {{math|2n – 1}} matchings may be necessary: consider a family of {{math|2n – 2}} matchings, of which {{math|n – 1}} are {{math|{ (x{{sub|1}}, y{{sub|1}}), (x{{sub|2}}, y{{sub|2}}), ..., (x{{sub|n}}, y{{sub|n}})} }} and the other {{math|n – 1}} are {{math|{(x{{sub|1}}, y{{sub|2}}), (x{{sub|2}}, y{{sub|3}}), …, (x{{sub|n}}, y{{sub|1}}) }.}} Then the largest rainbow matching is of size {{math|n – 1}} (e.g. take one edge from each of the first {{math|n – 1}} matchings).

Alon{{Cite journal|last=Alon|first=Noga|date=2011|title=Multicolored Matchings in Hypergraphs|journal=Moscow Journal of Combinatorics and Number Theory|volume=1|pages=3–10}} showed that Drisko's theorem implies an older result{{Cite journal|last1=Flores|first1=Carlos|last2=Ordaz|first2=Oscar|date=1996-05-01|title=On the Erdös-Ginzburg-Ziv theorem|journal=Discrete Mathematics|volume=152|issue=1–3|pages=321–324|doi=10.1016/0012-365x(94)00328-g|issn=0012-365X|doi-access=free}} in additive number theory.

Aharoni and Berger{{Cite journal|last1=Aharoni|first1=Ron|last2=Berger|first2=Eli|date=2009-09-25|title=Rainbow Matchings in $r$-Partite $r$-Graphs|journal=The Electronic Journal of Combinatorics|volume=16|issue=1|doi=10.37236/208|issn=1077-8926|doi-access=free}} generalized Drisko's theorem to any bipartite graph, namely: any family of {{math|2n – 1}} matchings of size {{mvar|n}} in a bipartite graph has a rainbow matching of size {{mvar|n}}.

Aharoni, Kotlar and Ziv{{Cite journal|last1=Aharoni|first1=Ron|last2=Kotlar|first2=Dani|last3=Ziv|first3=Ran|date=2018-01-01|title=Uniqueness of the extreme cases in theorems of Drisko and Erdős–Ginzburg–Ziv|journal=European Journal of Combinatorics|volume=67|pages=222–229|doi=10.1016/j.ejc.2017.08.008|s2cid=38268762|issn=0195-6698|doi-access=free}} showed that Drisko's extremal example is unique in any bipartite graph.

In general graphs, {{math|2n – 1}} matchings are no longer sufficient. When {{mvar|n}} is even, one can add to Drisko's example the matching {{math|{ (x{{sub|1}}, x{{sub|2}}), (y{{sub|1}}, y{{sub|2}}), (x{{sub|2}}, x{{sub|3}}), (y{{sub|2}}, y{{sub|3}}), … } }} and get a family of {{math|2n – 1}} matchings without any rainbow matching.

Aharoni, Berger, Chudnovsky, Howard and Seymour{{Cite journal|last1=Aharoni|first1=Ron|last2=Berger|first2=Eli|last3=Chudnovsky|first3=Maria|last4=Howard|first4=David|last5=Seymour|first5=Paul|date=2019-06-01|title=Large rainbow matchings in general graphs|journal=European Journal of Combinatorics|volume=79|pages=222–227|doi=10.1016/j.ejc.2019.01.012|issn=0195-6698|arxiv=1611.03648|s2cid=42126880}} proved that, in a general graph, {{math|3n – 2}} matchings (=colors) are always sufficient. It is not known whether this is tight: currently the best lower bound for even {{mvar|n}} is {{math|2n}} and for odd {{mvar|n}} it is {{math|2n – 1}}.{{Cite journal|last1=Aharoni|first1=Ron|last2=Holzman|first2=Ron|last3=Jiang|first3=Zilin|date=2019-10-29|title=Rainbow Fractional Matchings|journal=Combinatorica|volume=39|issue=6|pages=1191–1202|doi=10.1007/s00493-019-4019-y|issn=0209-9683|arxiv=1805.09732|s2cid=119173114}}

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:

• Instead of requiring that each color be a matching of size {{mvar|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 {{mvar|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.

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 {{mvar|n}} be any positive integer. Given any family of {{math|2n – 1}} fractional-matchings (=colors) of size {{mvar|n}} in a bipartite graph, there exists a rainbow-fractional-matching of size {{mvar|n}}.

Aharoni, Holzman and Jiang extend this theorem to arbitrary graphs as follows. Let {{mvar|n}} be any positive integer or half-integer. Any family of {{math|2n}} fractional-matchings (=colors) of size at least {{mvar|n}} in an arbitrary graph has a rainbow-fractional-matching of size {{mvar|n}}.{{Rp|Thm.1.5}} The {{math|2n}} is the smallest possible for fractional matchings in arbitrary graphs: the extremal case is constructed using an odd-length cycle.

For the case of perfect fractional matchings, both the above theorems can derived from the colorful Caratheodory theorem.

For every edge {{mvar|e}} in {{mvar|E}}, let {{math|1{{sub|e}}}} be a vector of size {{math|{{abs|V}}}}, where for each vertex {{mvar|v}} in {{mvar|V}}, element {{mvar|v}} in {{math|1{{sub|e}}}} equals 1 if {{mvar|e}} is adjacent to {{mvar|v}}, and 0 otherwise (so each vector {{math|1{{sub|e}}}} has 2 ones and {{math|{{abs|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 {{mvar|F}} of edges admits a perfect fractional matching, if and only if {{math|1{{sub|{{mvar|v}}}} }} (the vector of {{math|{{abs|V}}}} ones) is contained in the conical hull of the vectors {{math|1{{sub|e}}}} for {{mvar|e}} in {{mvar|F}}.

Consider a graph with {{math|2n}} vertices, and suppose there are {{math|2n}} subsets of edges, each of which admits a perfect fractional matching (of size {{mvar|n}}). This means that the vector {{math|1{{sub|{{mvar|v}}}}}} is in the conical hull of each of these {{mvar|n}} subsets. By the colorful Caratheodory theorem, there exists a selection of {{math|2n}} edges, one from each subset, that their conical hull contains {{math|1{{sub|{{mvar|v}}}}}}. This corresponds to a rainbow perfect fractional matching. The expression {{math|2n}} is the dimension of the vectors {{math|1{{sub|e}}}} - each vector has {{math|2n}} elements.

Now, suppose that the graph is bipartite. In a bipartite graph, there is a constraint on the vectors {{math|1{{sub|e}}}}: the sum of elements corresponding to each part of the graph must be 1. Therefore, the vectors {{math|1{{sub|e}}}} live in a {{math|(2n – 1)}}-dimensional space. Therefore, the same argument as above holds when there are only {{math|2n – 1}} subsets of edges.

An r-uniform hypergraph is a set of hyperedges each of which contains exactly {{mvar|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 {{mvar|n}} be any positive rational number. Any family of {{math|⌈r⋅n⌉}} fractional-matchings (=colors) of size at least {{mvar|n}} in an {{mvar|r}}-uniform hypergraph has a rainbow-fractional-matching of size {{mvar|n}}.{{Rp|Thm.1.6}} The {{math|⌈r⋅n⌉}} is the smallest possible when {{mvar|n}} is an integer.

An r-partite hypergraph is an {{mvar|r}}-uniform hypergraph in which the vertices are partitioned into {{mvar|r}} disjoint sets and each hyperedge contains exactly one vertex of each set (so a 2-partite hypergraph is a just bipartite graph). Let {{mvar|n}} be any positive integer. Any family of {{math|rn – r + 1}} fractional-matchings (=colors) of size at least {{mvar|n}} in an {{mvar|r}}-partite hypergraph has a rainbow-fractional-matching of size {{mvar|n}}.{{Rp|Thm.1.7}} The {{math|rn – r + 1}} is the smallest possible: the extremal case is when {{math|1=n = r – 1}} is a prime power, and all colors are edges of the truncated projective plane of order {{mvar|n}}. So each color has {{math|1=n{{sup|2}} = rn – r + 1}} edges and a fractional matching of size {{mvar|n}}, but any fractional matching of that size requires all {{math|rn – r + 1}} edges.{{Cite journal|last=Füredi|first=Zoltán|date=1989-05-01|title=Covering the complete graph by partitions|journal=Discrete Mathematics|volume=75|issue=1–3|pages=217–226|doi=10.1016/0012-365x(89)90088-5|issn=0012-365X|doi-access=free}}

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

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

{{See also|matching in hypergraphs}}

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

{{cite book|last1=Garey|first1=M. R.|title=Computers and Intractability: A Guide to the Theory of NP-Completeness|last2=Johnson|first2=D. S.|publisher=W. H. Freeman and Co.|year=1979|isbn=0-7167-1045-5|editor=Victor Klee|editor-link=Victor Klee|series=A Series of Books in the Mathematical Sciences|location=San Francisco, Calif.|pages=[https://archive.org/details/computersintract0000gare/page/ x+338]|mr=519066|author-link1=Michael R. Garey|author-link2=David S. Johnson}}

Rainbow matchings have been applied for solving packing problems.{{cite arXiv |last1=Bannach |first1=Max |last2=Berndt |first2=Sebastian |last3=Maack |first3=Marten |last4=Mnich |first4=Matthias |last5=Lassota |first5=Alexandra |last6=Rau |first6=Malin |last7=Skambath |first7=Malte |date=2020-07-06 |title=Solving Packing Problems with Few Small Items Using Rainbow Matchings |class=cs.DS |eprint=2007.02660 }}

• Rainbow coloring
• Rainbow-colorable hypergraph
• Rainbow-independent set
• Rainbow covering
• Hall-type theorems for hypergraphs

{{Reflist}}

{{DEFAULTSORT:Rainbow Matching}}

Category:Graph theory objects

Category:Graph coloring

matching

Category:Latin squares

Category:NP-complete problems