Rainbow fractional matchings

Computer Science/Discrete Mathematics Seminar I
Topic:Rainbow fractional matchings
Speaker:Ron Holzman
Affiliation:Technion
Date:Monday, December 2
Time/Room:11:00am - 12:00pm/Simonyi Hall 101
Video Link:https://video.ias.edu/csdm/2019/1202-RonHolzman

Given a family of m matchings in a graph G (where each matching can be thought of as a color class), a rainbow matching is a choice of edges of distinct colors that forms a matching. How many matchings of size n are needed to guarantee the existence of a rainbow matching of size n? If G is bipartite, a theorem of Drisko generalized by Aharoni and Berger says that m = 2n - 1 suffices (and is best possible). In a general graph G, this is not the case, but m = 2n is conjectured to be enough. We prove a fractional version of this conjecture, not only for graphs but also for r-uniform hypergraphs. The main tool is a topological result of Kalai and Meshulam. This is joint work with Ron Aharoni and Zilin Jiang.