Algorithms, Combinatorics and Optimization Seminar Zilin Jiang
Technion
Title: Rainbow fractional matchings

Abstract: Given sets E₁, ..., E_n, a rainbow set consists of at most 1 element from each E_i. Bárát, Gyárfas and Sárkozy conjectured that 2n matchings of size n (on a common vertex set) have a rainbow matching of size n. The conjecture can be thought as a generalization of Drisko's theorem: 2n-1 perfect matchings of size n have a rainbow perfect matching. In this talk, we will present a short proof of Drisko's theorem using Bárány's colorful Carathéodory theorem. This new 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.

Joint work with Ron Aharoni and Ron Holzman.

Date: Thursday, May 17, 2018
Time: 3:30 pm
Location: Wean Hall 8220
Note: Before the talk, at 3:10 pm, there will be tea and cookies in Wean Hall 6220.