Noga Alon "Splitting Random Necklaces"
Noga Alon from Princeton and Tel Aviv will give the talk "Splitting Random Necklaces" on the labs' Big Seminar.
▶ Please note the unusual time and day for our Big Seminar. The talk is a part of the online event Round the World Relay in Combinatorics - follow the link to see the schedule, there are a lot of other interesting talks.
Abstract:
Let N be a random necklace with km beads of each of t types. What is the typical minimum number of points in which one can cut N so that it will be possible to partition the resulting intervals of beads into k collections, each containing exactly m beads of each type? It is known that this number is at most (k-1)t with probability 1; is it typically significantly smaller?
I will discuss a recent joint work with Dor Elboim, Janos Pach and Gabor Tardos addressing this problem and showing that it is connected to several seemingly unrelated topics, including matchings in nearly regular hypergraphs and random walks in Euclidean spaces.
Watch the video:
Everyone is invited to attend. The language of the lecture is English. The event is aimed at master and graduate students, as well as researchers in the field of combinatorics.