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 (2016), DOI link, arXiv link
- ↑ D. Kotlar, R. Ziv, Rainbow sets in the intersection of two matroids: A generalization of results of Drisko and Chappell (2015), DOI link, preliminary arXiv version
