You are here

Computer Science/Discrete Mathematics Seminar I

Rainbow fractional matchings

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.

Featuring

Ron Holzman

Speaker Affiliation

Technion

Affiliation

Mathematics

Event Series

Video

https://video.ias.edu/csdm/2019/1202-RonHolzman
Date & Time
December 02, 2019 | 11:00am12:00pm

Location

Simonyi Hall 101

Categories