MATH Seminar

Title: Rainbow fractional matchings
Seminar: Combinatorics
Speaker: Zilin Jiang of The Massachusetts Institute of Technology
Contact: Dwight Duffus, dwightduffus@emory.edu
Date: 2018-10-19 at 4:00PM
Venue: MSC W301
Download Flyer
Abstract: Given edge sets E_1, ..., E_n, a rainbow set consists of at most 1 element from each E_i. Drisko's theorem says that any family of 2n-1 perfect matchings of size n in a bipartite graph has a rainbow perfect matching. In this talk, we will present a connection, found by Alon, to the well-known result of Erdos, Ginzburg and Ziv in additive number theory, and we will give a short proof of Drisko's theorem using Barany's colorful Caratheodory theorem from Discrete Geometry. If the bipartiteness assumption is removed, Drisko's result is no longer true. However, it may well be the case that 2n matchings suffice. Our new discrete-geometric proof leads to the discovery of a fractional version of the conjecture: Let n be an integer or a half integer. If the fractional matching number of each of the 2n graphs is at least n, then there is a rainbow edge set of fractional matching number at least n. This is joint work with Ron Aharoni and Ron Holzman.