Rainbow independent sets and collapsibility

Rainbow independent sets and collapsibility

Ron Aharoni, Technion, Haifa
Fine Hall 224

Conjecture: Any 2n matchings of size n in any graph have a rainbow matching of size n. 

("Rainbow" means choosing at most one edge from each of the given matchings). 

We prove a fractional version, using a topological tool called "d-collapsibility". I will also discuss  the more general problem, of finding rainbow independent sets for given independent sets in general graphs (the above problem being the case of independent sets in line graphs). 

Based on joint work with Ron Holzman, Zilin Jiang, Joseph Briggs and Minki Kim.The visit of the speaker is supported by the H2020-MSCA-RISE project CoSP- GA No. 823748.