Virtual colloquium by

Prof. Noga Alon

(Princeton University and Tel Aviv University)

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.