Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department
Alumni |
Algorithms, Combinatorics and Optimization Seminar
Zilin Jiang Technion Title: Rainbow fractional matchings Abstract: Given sets E, ..., _{1}E, a rainbow set consists of at most _{n}1 element from each E. Bárát, Gyárfas and Sárkozy conjectured that _{i}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, 2018Time: 3:30 pmLocation: Wean Hall 8220Note: Before the talk, at 3:10 pm, there will be tea and cookies in Wean Hall 6220. |