Mathematics Colloquium

Tel Aviv University

Monday, May 22, 2017
Schreiber 006
Yuval Peres
Microsoft Research
Gravitational allocation to uniform points on the sphere

Given n uniform points on the surface of a two-dimensional sphere, how can we partition the sphere fairly among them in an equivariant way? "Fairly" means that each region has the same area. "Equivariant" means that if we rotate the sphere, the solution rotates along with the points. It turns out that if the given points apply a two-dimensional gravity force to the rest of the sphere, then the basins of attraction for the resulting gradient flow yield such a partition, with exactly equal areas, no matter how the points are distributed. (See the cover of the AMS Notices.) Our main result is that this partition minimizes, up to a bounded factor, the average distance between points in the same cell. I will also present an application to almost optimal matching of n uniform blue points to n uniform red points on the sphere, connecting to a classical result of Ajtai, Komlós and Tusnády (Combinatorica 1984).

This is joint work with Nina Holden and Alex Zhai, inspired by earlier works of Sodin and Tsirelson (Israel J. 2006), Nazarov, Sodin and Volberg (GAFA 2007) and Chatterjee, Peled, Romik and the speaker (Annals Math. 2010).

Colloquium's homepage : www  |  Yuval Peres' homepage : www