***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Shira Zerbib (Michigan)

Thursday 1st March, 3:00 in Fine Hall 224.

Title: Envy-free division of a cake without the "hungry players"
assumption

Consider n players having preferences over a rectangular cake,
identified with the interval [0,1]. A classical theorem due to
Stromquist ensures that under some conditions it is possible to
divide the cake into n interval pieces and assign one piece to
each player in an envy-free manner, such that no player strictly
prefers a piece that has not been assigned to him. One of these
conditions, which has been always considered as crucial, is that
the players are "hungry": in every partition of the cake, every
player prefers a non-empty piece. We prove that it is still
possible to get an envy-free division even if this condition is
not satisfied. This was conjectured by Erel Segal-Halevi, who
proved it for at most 3 players. The main step in our proof is a
new combinatorial lemma in topology, which is reminiscent of the
Sperner lemma: Instead of restricting the labels that can appear
on each face of the simplex, the lemma considers labelings that
enjoy a certain symmetry on the boundary. Joint with
Frederic Meunier.


		---------------------------------------------

Next week: Oliver Schaudt

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)