Computer Science/Discrete Mathematics Seminar I | |

Topic: | Rainbow fractional matchings |

Speaker: | Ron Holzman |

Affiliation: | Technion |

Date: | Monday, December 2 |

Time/Room: | 11:00am - 12:00pm/Simonyi Hall 101 |

Video Link: | https://video.ias.edu/csdm/2019/1202-RonHolzman |

Given a family of m matchings in a graph G (where each matching can be thought of as a color class), a rainbow matching is a choice of edges of distinct colors that forms a matching. How many matchings of size n are needed to guarantee the existence of a rainbow matching of size n? If G is bipartite, a theorem of Drisko generalized by Aharoni and Berger says that m = 2n - 1 suffices (and is best possible). In a general graph G, this is not the case, but m = 2n is conjectured to be enough. We prove a fractional version of this conjecture, not only for graphs but also for r-uniform hypergraphs. The main tool is a topological result of Kalai and Meshulam. This is joint work with Ron Aharoni and Zilin Jiang.