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.