CoSP REU lecture June 22 2021 by Martin Tancer

Title: Necklace splitting on trees

Martin Tancer, Charles University Prague 

video available here

In the classical necklace splitting problem k thieves steal an open-ended necklace with t different types of gems. The number of gems of each type is divisible by k. The target of the thieves is to split the necklace with as few cuts as possible so that they can distribute the pieces so that each thief gets the same number of gems of each type as the other thieves. In this variant, it is well known that (k-1)t cuts are sufficient and for some necklaces also necessary.

During the talk, I will discuss the variant of this problem when the necklace is arranged along the tree. This setting offers several variants of the problem. I will show a combinatorial solution and a geometric solution of some of the variants. The talk is based on joint discussions with Martin Loebl.