From fractional to integral matchings in d-partite hypergraphs
Seminar
Speaker
Erel Segal-Halevi (Ariel University)
Date
01/11/2020 - 15:30 - 14:00Add to Calendar
2020-11-01 14:00:00
2020-11-01 15:30:00
From fractional to integral matchings in d-partite hypergraphs
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.
Zoom
אוניברסיטת בר-אילן - Department of Mathematics
mathoffice@math.biu.ac.il
Asia/Jerusalem
public
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.
Last Updated Date : 27/10/2020
