The ACO Seminar (2020–2021)

In the necklace splitting problem, two thieves steal a necklace with k types of jewels and want to partition the necklace so that each thief gets half the jewels of each type, using the minimum number of cuts. At most k cuts are required; this result has a nice topological proof via the Borsuk–Ulam theorem, which involves representing the configuration space of possible cuts as a sphere. I will present several combinatorial results using similar techniques.

Recently, Lazarev and Lieb proved a smooth variant of the necklace splitting result. I will explain how the same technique, of representing the configuration space as a sphere and applying the Borsuk–Ulam theorem, can be used to generalize their result and improve the best-known quantitative bounds. Our approach also yields a result on motion planning algorithms; a motion planning algorithm is a continuous choice of paths for a robot to travel from any starting point to any ending point in a space.

Please email Boris Bukh (bbukh ~at~ math) for a password.