Chair of the colloquium: Prof. Jaikumar Radhakrishnan (TIFR Mumbai)
Release of the lecture video on YouTube: August 20, 2021 at 18:00 hrs Indian time
Interactive session on Zoom: September 20, 2021 at 18:00 hrs Indian time
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.