Rainbow matchings in bipartite graphs

From Egres Open
Jump to: navigation, search

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

  1. R. A. Brualdi and H. J. Ryser, Combinatorial Matrix Theory, Cambridge University Press, Cambridge, UK, 1991, Google Books link
  2. S. K. Stein, Transversals of Latin squares and their generalizations, Pacific J. Math. 59 (1975), 567–575, pdf link
  3. 3.0 3.1 R. Aharoni, P. Charbit and D. Howard, On a Generalization of the Ryser-Brualdi-Stein Conjecture, DOI link, arXiv link
  4. D. Kotlar, R. Ziv, Large matchings in bipartite graphs have a rainbow matching, DOI link, arXiv link
  5. D. Clemens, J. Ehrenmüller, An improved bound on the sizes of matchings guaranteeing a rainbow matching, arXiv link
  6. A. Pokrovskiy, An approximate version of a conjecture of Aharoni and Berger, arXiv link
  7. J. Barát, A. Gyárfás, G.N. Sárközy, Rainbow matchings in bipartite multigraphs, arXiv link
  8. A.A. Drisko, Transversals in row-Latin rectangles, DOI link
  9. R. Aharoni, D. Kotlar, R. Ziv, Rainbow sets in the intersection of two matroids, DOI link, arXiv link
  10. 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