Aharoni-Berger strong conjecture for bipartite graphs

Let M1,,MnM_1,\dots,M_n be matchings of size n+1n+1 in a bipartite graph. A rainbow matching is a matching whose edges can be assigned distinct indices ii so that each edge belongs to MiM_i.

Aharoni-Berger strong conjecture. Every collection of nn matchings of size n+1n+1 in a bipartite graph admits a rainbow matching of size nn.

The extra edge in each matching permits a full rainbow matching and implies the preceding bipartite n1n-1 conjecture by adjoining a common dummy edge. The bound n+1n+1 is best possible, while the conjecture remains open in the supplied text.

Sources & referencesView supporting material

Primary source

Candida Bowtell, Andrea Freschi, Gal Kronenberg and Jun Yan, “A note on improved bounds for hypergraph rainbow matching problems”, arXiv:2501.03216 (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.