Noga Alon "Fair partitions: questions, results and algorithms"
Noga Alon from Princeton and Tel Aviv University will give the talk "Fair partitions: questions, results and algorithms" on the labs' Big Seminar.
Password: first 6 decimal places of $\pi$ after the decimal point
A substantial number of results and conjectures deal with the existence of a set of prescribed type which contains a fair share from each member of a finite collection of objects in a space, or the existence of partitions in which this is the case for every part. Examples include the Ham-Sandwich Theorem in Measure Theory, the Hobby-Rice Theorem in Approximation Theory, the Necklace Theorem and the Ryser Conjecture in Discrete Mathematics, and more. The techniques in the study of these results combine combinatorial, topological, geometric and algebraic tools.
I will describe the topic, focusing on several recent existence results and their algorithmic aspects.
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.