The ACO Seminar (2017–2018)

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.

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.