Colloquium: Tuesday, March 12, 2019. Speaker: Eli Berger (Haifa). Title: “Hypergraph matching, rainbow matching, topology and games”.
Place: Room 614 in the Education & Sciences Building
Consider a 3-partite hypergraph with three sides V1, V2, V3. We want to find sufficient conditions for the existence of a matching in which all vertices of V1 are matched. Obviously, this can be translated into the language of finding a rainbow matching in a bipartite graph, i.e., given an edge-colored bipartite graph, we want to find a matching in which each color appears once. It is much less obvious that this problem can be translated into the language of topological connectivity, and from there, to the language of games. In the talk, I will show how all these notions connect and use this machinery to deal with the case m=2k-1, where m is the minimal degree in V1 and k is the maximal degree in V2UV3.
Tea will be served before the talk (at 13:50).