2020/03/18 by Aharoni, Ron, Briggs, Joseph, Cho, Minho +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2003.08247
Let k>1, and let F be a family of 2n+k-3 non-empty sets of edges in a bipartite graph. If the union of every k members of F contains a matching of size n, then there exists an F-rainbow matching of size n. Replacing 2n+k-3 by 2n+k-2, the result is true also for k=1, and it can be proved (for all k) both topologically and by a relatively simple combinatorial argument. The main effort is in gaining the last 1, which makes the result sharp.