Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department
Alumni |
Algorithms, Combinatorics and Optimization Seminar
Technion Title: Rainbow fractional matchings Abstract: Given sets E1, ..., En, a rainbow set consists of at most 1 element from each Ei. 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. |