R A N D O M     M A T R I C E S,    R A N D O M      G E O M E T R Y

A joint Harvard-MIT probability afternoon, organized with A. Borodin, I. Corwin, A. Guionnet, H.-T. Yau.

Friday April 26th, Harvard Science Center, room 309

• 2.30pm   Mark Rudelson (Michigan).   Permanent estimators via random matrices.
  The permanent of a square matrix is defined similarly to the determinant. It is the sum of products of entries over all ``generalized diagonals'', only without signs in front of the products. The evaluation of the determinant is computationally efficient, while the evaluation of the permanent is an NP-hard problem. Since the deterministic methods are not available, permanents are estimated probabilistically. One of such estimators constructed by Barvinok evaluates the permanent of a deterministic matrix via the determinant of a random matrix associated to it. Barvinok proved that the multiplicative error of this estimator is at most exponential, and this result cannot be improved for general matrices. We provide conditions on the matrix, under which the Barvinok estimator yields a subexponential error. Joint work with Ofer Zeitouni.


• 3.30pm   Nikolai Makarov (Caltech).   The support of the equilibrium measure in the random normal matrix model.
  The talk will be about the shapes of local droplets in the case of an algebraic external potential. There are several interesting connections with different areas of analysis. Based on joint work with S.-Y. Lee.


• 5pm          Jean-François Le Gall (Orsay).   The Brownian map: A universal model of random geometry.
  Planar maps are graphs embedded in the plane, considered up to continuous deformation. They have been studied extensively in combinatorics, and they are also used in theoretical physics, where they serve as models of random geometry, in particular in two-dimensional quantum gravity. Special cases of planar maps are p-angulations, where each face (meaning each component of the complement of edges) has exactly p adjacent edges. Our goal is to discuss the convergence in distribution of rescaled random planar maps viewed as random metric spaces. More precisely, we consider a random planar map M(n), which is uniformly distributed over the set of all p-angulations with n vertices. We equip the set of vertices of M(n) with the graph distance rescaled by the factor n to the power -1/4. Both in the case p=3 and when p>3 is even, we prove that the resulting random metric spaces converge as n tends to infinity to a universal object called the Brownian map. This convergence holds in the sense of the Gromov-Hausdorff distance between compact metric spaces. In the particular case of triangulations (p=3), this solves an open problem stated by Oded Schramm in his 2006 ICM paper. As a key tool, we use bijections between planar maps and various classes of labeled trees. If time permits, we will also discuss possible connections between our work and the different approach to quantum gravity developed by Duplantier and Sheffield.