# Rainbow matchings in bipartite graphs

Given *k* disjoint matchings in a bipartite graph, a **rainbow matching** is a matching that contains one edge from each of them. Is it true that any family of *k* disjoint matchings of size *k+1* has a rainbow matching?

## Remarks

The conjecture was suggested by Aharoni and Berger as a generalization of the conjecture of Brualdi ^{[1]} and Stein ^{[2]} on Latin squares, see the survey ^{[3]}. Kotlar and Ziv ^{[4]} proved that any family of *k* disjoint matchings of size [math]\lfloor \frac{5}{3} k\rfloor[/math] has a rainbow matching. Clemens and Ehrenmüller ^{[5]} improved the bound to [math]\frac{3}{2}k+o(k)[/math], and recently Pokrovskiy ^{[6]} improved it to [math]k+o(k)[/math], which can be regarded as an asymptotic version of the Aharoni-Berger conjecture. Additional results can be found in ^{[7]}. The following matroidal generalization is also open:

**Conjecture ^{[3]}.** Let [math]M_1=(S,r_1)[/math] and [math]M_2=(S,r_2)[/math] be two matroids of rank

*k+1*on

*S*, such that

*S*can be partitioned into

*k*common bases [math]B_1, \dots, B_k[/math]. Then the family [math]B_1, \dots, B_k[/math] has a transversal that is independent in both matroids.

There are two related results; the first one is a weaker version of the conjecture, while the second one is a complementary result (its special case involving bipartite graphs is Drisko's Theorem ^{[8]}).

**Theorem ^{[9]}.** Let [math]M_1=(S,r_1)[/math] and [math]M_2=(S,r_2)[/math] be two matroids of rank

*k*on

*S*, such that

*S*can be partitioned into

*k*common bases [math]B_1, \dots, B_k[/math]. Then the family [math]B_1, \dots, B_k[/math] has a partial transversal of size [math]k-\sqrt{k}[/math] that is independent in both matroids.

**Theorem ^{[10]}.** Let [math]M_1=(S,r_1)[/math] and [math]M_2=(S,r_2)[/math] be two matroids of rank

*k*on

*S*, such that

*S*can be partitioned into

*2k-1*common bases [math]B_1, \dots, B_{2k-1}[/math]. Then the family [math]B_1, \dots, B_{2k-1}[/math] has a partial transversal of size [math]k[/math] that is a common base.

## References

- ↑ R. A. Brualdi and H. J. Ryser,
*Combinatorial Matrix Theory*, Cambridge University Press, Cambridge, UK, 1991, Google Books link - ↑ S. K. Stein,
*Transversals of Latin squares and their generalizations*, Pacific J. Math. 59 (1975), 567–575, pdf link - ↑
^{3.0}^{3.1}R. Aharoni, P. Charbit and D. Howard,*On a Generalization of the Ryser-Brualdi-Stein Conjecture*, DOI link, arXiv link - ↑ D. Kotlar, R. Ziv,
*Large matchings in bipartite graphs have a rainbow matching*, DOI link, arXiv link - ↑ D. Clemens, J. Ehrenmüller,
*An improved bound on the sizes of matchings guaranteeing a rainbow matching*, arXiv link - ↑ A. Pokrovskiy,
*An approximate version of a conjecture of Aharoni and Berger*, arXiv link - ↑ J. Barát, A. Gyárfás, G.N. Sárközy,
*Rainbow matchings in bipartite multigraphs*, arXiv link - ↑ A.A. Drisko,
*Transversals in row-Latin rectangles*, DOI link - ↑ R. Aharoni, D. Kotlar, R. Ziv,
*Rainbow sets in the intersection of two matroids*, DOI link, arXiv link - ↑ D. Kotlar, R. Ziv,
*Rainbow sets in the intersection of two matroids: A generalization of results of Drisko and Chappell*, DOI link, preliminary arXiv version