# Gravitational matching and allocation for uniform points on the sphere

Speaker
Prof. Yuval Peres, Microsoft Research
Date
14/10/2018 - 13:00 - 12:00Add to Calendar 2018-10-14 12:00:00 2018-10-14 13:00:00 Gravitational matching and allocation for 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/publications/journals/notices/201705/rnoti-cvr1.pdf or the PNAS article 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 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).  The talk will conclude with open problems on the behavior of greedy matching schemes. Joint work with Nina Holden and Alex Zhai. Room 201, Building 216. אוניברסיטת בר-אילן - המחלקה למתמטיקה mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Room 201, Building 216.
Abstract

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/publications/journals/notices/201705/rnoti-cvr1.pdf or the PNAS article 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 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).  The talk will conclude with open problems on the behavior of greedy matching schemes. Joint work with Nina Holden and Alex Zhai.

תאריך עדכון אחרון : 07/10/2018