Thema der Dissertation:
Applications of Topology, Combinatorics and Algorithms to Discrete Geometry Thema der Disputation:
Thieves and Necklaces
Applications of Topology, Combinatorics and Algorithms to Discrete Geometry Thema der Disputation:
Thieves and Necklaces
Abstract: Can a necklace with ka_i beads of colour i be fairly divided among k thieves by at most (k-1)n cuts?
This problem is simple to state, but has two interesting perspectives:
The answer is yes by a classical application of the Borsuk-Ulam theorem for two thieves and a generalization for more thieves. However, this non-constructive proof does not determine the solution. In general, finding the solution can be challenging. This observation has been formalized recently by Filos-Ratsikas and Goldberg by showing that the task of splitting a necklace among 2 thieves with ncuts is a PPA-complete problem.
We will gather some notions and techniques used for the above results.
This problem is simple to state, but has two interesting perspectives:
The answer is yes by a classical application of the Borsuk-Ulam theorem for two thieves and a generalization for more thieves. However, this non-constructive proof does not determine the solution. In general, finding the solution can be challenging. This observation has been formalized recently by Filos-Ratsikas and Goldberg by showing that the task of splitting a necklace among 2 thieves with ncuts is a PPA-complete problem.
We will gather some notions and techniques used for the above results.
Zeit & Ort
14.07.2022 | 11:00