# 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.