שלחו לחבר

From fractional to integral matchings in d-partite hypergraphs

Seminar
Speaker
Erel Segal-Halevi (Ariel University)
Date
01/11/2020 - 15:30 - 14:00
Place
Zoom
Abstract

A d-partite hypergraph is called *fractionally balanced* if there exists a non-negative function on its edge set that has constant degrees in each vertex side. Using a topological version of Hall's theorem, we prove new lower bounds on the matching number of such hypergraphs. Our bounds yield results on envy-free division of multiple cakes, covering colorful families of d-intervals, and rental harmony with multiple houses.

Joint work with Ron Aharoni, Eli Berger, Joseph Briggs and Shira Zerbib.

תאריך עדכון אחרון : 27/10/2020