Prof. Noga Alon

Title: The Necklace Theorem: challenges, variants and algorithms

Abstract: It is known that one can cut any open necklace with beads of t types in at most (k-1)t points and partition the resulting intervals into k collections, each containing the same number of beads of each type (up to 1). This number of cuts is optimal. I will discuss some recent advances in the study of this result focusing on its algorithmic aspects and on the case of random necklaces.

Based on joint work with Anrdei Graur and with Dor Elboim, Janos Pach and Gabor Tardos.