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