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.
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.
The seminar dinner after the talks will take place at 7.15pm at Grafton St restaurant.