Cooperative conditions for the existence of rainbow matchings

Abstract

© The authors.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.