Computer Science/Discrete Mathematics Seminar I

Topic: Rainbow fractional matchings

Speaker: Ron Holzman

Affiliation: Technion

Date & Time: Monday December 2nd, 2019, 11:00am - 12:00pm

Location: Simonyi Hall 101

Video: 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.