***********************************
* Princeton Discrete Math Seminar *
***********************************
Speaker: Eli Berger (U. Haifa)
Thursday 15th April, 3:00 via Zoom.
Title: Cake cutting, balanced hypergraphs and topology
The problem of "envy-free" cake cutting deals with n
agents who need to share r cakes between them, where cake number i
is sliced into a_i slices. For each agent, each possible slicing,
and each choice of one slice from each cake, this choice is defined
to be either "acceptable" or "unacceptable" for this agent. We ask
questions such as whether it is always (under some natural
assumptions) possible to choose a slicing of the cakes and assign an
acceptable set of slices for each of the agents, or alternately to m
of the agents, where m \le n is some given number. This turns out
to be linked to the problem of finding a matching in hypergraphs
known as balanced r+1-partite hypergraphs, which in turn is linked
to the notion of topological connectivity of the matching complex of
r-partite hypergraphs. In my talk, I will show how these notions
are related, and how these methods are used to generalize some known
results and prove some new ones.
This is joint work with Ron Aharoni, Joseph Briggs, Erel Segal-Halevi
and Shira Zerbib.
----------------------------------
Next week: Rose McCarty
Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)