Δευτέρα 16 Ιουνίου. Ώρα 12:10 μμ.

Αίθουσα: Γ31

Ομιλητής: Yuval Peres, Beijing Institute of Math Sciences and Applications (BIMSA)

Τίτλος: 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 ? "Fairly" means that each region has the same area. 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 at [http://www.ams.org/.../jour.../notices/201705/rnoti-cvr1.pdf](http://www.ams.org/.../jour.../notices/201705/rnoti-cvr1.pdf) or the PNAS article [http://www.pnas.org/content/early/2018/09/06/1720804115](http://www.pnas.org/content/early/2018/09/06/1720804115) ). 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, Komlos and Tusnady (Combinatorica 1984). I will emphasize open problems on the diameters of the basins and the behavior of greedy matching schemes.

Joint work with Nina Holden and Alex Zhai.