October 22, 3:30pm, https://cmu.zoom.us/j/98951280265

Matt Superdock, Carnegie Mellon University

The necklace splitting problem and robot motion planning

Matt Superdock, Carnegie Mellon University

The necklace splitting problem and robot motion planning

Abstract:

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**.