**Title of presentation: **“Fair division of graphs and of tangled cakes” **Ayumi Igarashi* **and **William S. Zwicker****

*National Institute of Informatics (Japan), Principles of Informatics Research Division

**Union College, Department of Mathematics

**Date, Time and Venue**: 2 June 11AM GMT – **online (see separate email invite)**

**Abstract**: Recent work by Bilò et al [2019] concerns allocating graph vertices (treated as indivisible objects) so that each share forms a connected subgraph, and so that no agent x envies another’s share “up to one outer good.” They obtain positive results that apply to arbitrarily many agents, but these are limited to Hamiltonian (aka traceable) graphs. What of the non-Hamiltonian case? We show that among topological classes of graphs, any non-Hamiltonian class has an upper bound on the number of agents for which fair shares are guaranteed. On the other hand, for the case of exactly 3 agents, positive results exist for some infinite, non-Hamiltonian graph classes. Our results – positive and negative – are obtained via transfer from related theorems in continuous fair division, but we must go beyond the standard model, which employs the unit interval [0,1] as the continuously divisible “cake.” Instead, we use several copies of [0,1] glued at their endpoints, to form the letter Y, or the figure 8, or the outline of a kiss . . . a “tangle.”

Everyone Welcome!