Berger–Aharoni conjecture on rainbow matchings

Let GG be a bipartite graph, and let M1,,MnM_1,\ldots,M_n be matchings in GG, each of size nn. A partial rainbow matching is a matching containing at most one edge from each MiM_i. Berger–Aharoni conjecture. The matchings M1,,MnM_1,\ldots,M_n have a partial rainbow matching of size n1n-1. This conjecture is closely related to open problems on transversals of Latin squares, including conjectures of Ryser, Brualdi, and Stein.

Sources & referencesView supporting material

Primary source

Eli Berger and Daniel McGinnis, “A common generalization to strengthenings of Drisko's Theorem for intersections of two matroids”, arXiv:2511.03135 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.