Let g(n) be the least number such that every collection of n matchings, each of size at least g(n), in a bipartite graph, has a full rainbow matching. Aharoni and Berger (2009) conjectured that g(n) = n + 1 for every n > 1. This generalizes famous conjectures of Ryser, Brualdi and Stein. Recently, Aharoni et al. proved that g(n) ≤ [7/4n]. We prove that g(n) ≤ [5/3 n].
展开▼
机译：令g（n）为最小数，以使二部图中n个匹配的每个集合（大小至少为g（n））都具有完整的Rainbow匹配。 Aharoni和Berger（2009）推测每n> 1时g（n）= n +1。这概括了Ryser，Brualdi和Stein的著名猜想。最近，Aharoni等。证明g（n）≤[7 / 4n]。我们证明g（n）≤[5/3 n]。
展开▼
