Splitting necklaces

Abstract: It is known that one can cut any opened necklace with beads of $n$ types in at most $(k-1)n$ 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 problem focusing on its algorithmic aspects and on the case of random necklaces.

Based on joint work with Anrdei Graur and on joint work in progress with Janos Pach and Gabor Tardos.

discrete mathematicscombinatorics

Audience: researchers in the topic

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).