Aharoni-Berger strong conjecture for bipartite graphs

About 1 year old · traced to

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 n−1n-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.

References

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.