Representation of large matchings in bipartite graphs

Abstract

Let $f(n)$ be the smallest number such that every collection of $n$ matchings, each of size at least $f(n)$, in a bipartite graph, has a full rainbow matching. Generalizing famous conjectures of Ryser, Brualdi and Stein, Aharoni and Berger conjectured that $f(n)=n+1$ for every $n>1$. Clemens and Ehrenm{ü}ller proved that $f(n)\le \frac{3}{2}n+o(n)$. We show that the $o(n)$ term can be reduced to a constant, namely $f(n)\le \lceil \frac{3}{2}n\rceil +1$.

References in corpus (2)

• Extremal Hypergraphs for Ryser's Conjecture: Home-Base Hypergraphs
• Extremal Hypergraphs for Ryser's Conjecture: Connectedness of Line Graphs of Bipartite Graphs