MIT Probability Seminar

Schedule:

• September 14: Bertrand Duplantier (Institute for Theoretical Physics, Saclay)

A Rigorous Perspective on Liouville Quantum Gravity and KPZ

(joint work with Scott Sheffield, MIT)

Liouville quantum gravity in two dimensions is described by the "random Riemannian manifold" obtained by changing the Lebesgue measure $dz$ in the plane by a random conformal factor $\exp [\gamma h(z)]$, where $h(z)$ is a random function called the Gaussian Free Field, and $\gamma$ a parameter.

This "random surface" is believed to be the continuum scaling limit of certain discretized random surfaces that can be studied with combinatorics and random matrix theory.

A famous formula, due to Knizhnik, Polyakov and Zamolodchikov in '88, relates standard critical exponents in the Euclidean plane to their counterparts on the random surfaces mentioned above. We describe a recent proof of the KPZ formula in the probabilistic setting given above.

• September 16: Elchanan Mossel (Weizmann Institute and U.C. Berkeley)
  -joint MIT probability seminar and Microsoft Research colloquium, 4pm Wednesday, first floor conference center, One Memorial Drive, Cambridge-

Quantitative Social Choice Theory

Results in economics established in 50s-70s imply that there is no rational way to rank or elect a winner when there are 3 or more alternatives.

We will consider the following question: Is it possible to rank or elect a winner in a way that is typically rational even if for some specific unlikely preferences of the voters it is not.

The talk will provide historical background on the topic as well as hints to some of the exotic mathematical tools that are used in this theory. These include inverse hyper-contractive estimates, non-linear invariance and a new isoperemetric theory involving interfaces between 3 bodies.

• September 21: David Wilson (Microsoft Research)

Double-dimer pairings and skew Young diagrams

We study the number of tilings of skew Young diagrams by ribbon tiles shaped like Dyck paths, in which the tiles are ``vertically decreasing''. We use these quantities to compute pairing probabilities in the double-dimer model. Given a planar bipartite graph G with special vertices, called nodes, on the outer face, the double-dimer model is formed by the superposition of a uniformly random dimer configuration (perfect matching) of G together with a random dimer configuration of the graph formed from G by deleting the nodes. The double-dimer configuration consists of loops, doubled edges, and chains that start and end at the boundary nodes. We are interested in how the chains connect the nodes. An interesting special case is when the graph is epsilon (Z x N) and the nodes are at evenly spaced locations on R as the grid spacing epsilon goes to 0.

Joint work with Rick Kenyon.

• September 28: No seminar. But...

• September 29: Stochastic Seminar Evarist Giné (University of Connecticut)
  -4:30pm Tuesday, 2-147-

Adaptive confidence bands for densities.

It is shown that a version of the Bickel-Rosenblatt (1973) distributional limit theorem for the supremum over an interval of the discrepancy between a density and its kernel density estimator extends to some linear wavelet estimators (with some changes). This is then used in the construction of adaptive confidence bands that are honest for all densities in a `generic' subset of the union of t-Holder balls, 0 This talk is based on joint work with Richard Nickl.

• October 5: Olivier Bernardi (MIT)

Correspondences between subgraphs, orientations and sandpile configurations

Any graph has the same number of spanning trees, recurrent sandpile configurations and root-connected score vectors. In this talk, I will present bijections between these structures. We will also present a bijection between connected subgraphs and root-connected orientations, and a bijection between spanning forests and score vectors.

All these bijections are obtained as specializations of a general correspondence between spanning subgraphs and orientations. The definition and analysis of this correspondence are related to a characterization of the Tutte polynomial using an embedding of the graph.

• October 8: Gil Kalai (Hebrew University of Jerusalem & Yale University)
  -4:30pm Thursday, 4-270-

Noise Sensitivity, Noise Stability, Percolation and some connections to TCS.

Noise sensitivity was defined in a paper by Benjamini, Kalai, and Schramm (1999). A closely related notion was considered by Tsirelson and Vershik. I will describe the notion of noise sensitivity of Boolean functions and some basic results and problems related to it. A fun way to explain it (especially after 2000) is in terms of the probability that small mistakes in counting the votes in an election will change the outcome. We will consider the following:

1) The definition of noise sensitivity, and how it is described in terms of the Fourier transform.

2) Noise sensitivity of the crossing event in Percolation (BKS 99, Schramm and Steiff 2005, and finally Garban, Pete, Schramm 2008), the scaling limit for the Spectral distribution (Schramm and Smirnov, 2007, GPS 2008), and dynamic percolation. (ScSt (2005), GPS (2008)). Other cases of noise sensitivity.

3) Noise stability of the majority function, of weighted majority. A conjecture regarding the situation for functions described by monotone depth monotone threshold circuits.

4) The "majority is stablest theorem" (Mossel, O'Donnell, Oleszkiewicz 05) and the connection to hardness of approximation.

(Some more related things can be found here: http://gilkalai.wordpress.com/2009/03/06/noise-sensitivity-lecture-and-tales/ )

• October 13: Fan Chung (UC San Diego)
  -Tuesday, but MIT schedule = Monday; regular time and room: 2-190 3-4pm-

Percolation on general graphs

We will discuss several problems with a percolation flavor while the given host graphs can be non-regular and sparse in general. To control the percolation, some old and new graph invariants play crucial roles. We will describe some of these graph invariants including the hitting time, the Green's function and the PageRank of graphs. Some related applications in epidemiology and approximation algorithms will also be mentioned.

• October 19: Jian Ding (Berkeley)

Near-critical random graph: its structure, diameter and mixing time

For a .pdf of this abstract, click here.

In this talk, I will present a complete description of the giant component of the Erd\H{o}s-R\'enyi random graph $G(n,p)$ as soon as it emerges from the scaling window, i.e., for $p = (1+\epsilon)/n$ where $\epsilon^3 n \to \infty$ and $\epsilon=o(1)$.

Our description is particularly simple for $\epsilon = o(n^{-1/4})$, where the giant component $C_1$ is contiguous with the following model (i.e., every graph property that holds with high probability for this model also holds w.h.p. for $C_1$). Let $Z$ be normal with mean $\frac23 \epsilon^3 n$ and variance $\epsilon^3 n$, and let $K$ be a random 3-regular graph on $2[Z]$ vertices. Replace each edge of $K$ by a path, where the path lengths are i.i.d. geometric with mean $1/\epsilon$. Finally, attach an independent Poisson($1-\epsilon$)-Galton-Watson tree to each vertex.

A similar picture is obtained for larger $\epsilon=o(1)$, in which case the random 3-regular graph is replaced by a random graph with $N_k$ vertices of degree $k$ for $k\geq 3$, where $N_k$ has mean and variance of order $\epsilon^k n$.

Based on this description, we show that for any $\epsilon=o(1)$ with $\epsilon^3n\to\infty$, the diameter of $C_1$ is w.h.p. asymptotic to $D (\epsilon,n)=(3/\epsilon)\log(\epsilon^3 n)$. Furthermore, we prove that the mixing time for the random walk on $C_1$ is w.h.p. of order $\epsilon^{-3}\log^2 (\epsilon^3 n)$. Based on joint work with J.H. Kim, E. Lubetzky and Y. Peres.

• October 26: Stephanie Somersille (U. Texas)

Biased Tug of War, The Biased Infinity Laplacian and Comparison with Exponential Cones

We use the game Biased Tug of War to prove results for a degenerate elliptic second order partial differential equation involving the infinity Laplacian operator and the norm of the gradient. We extend the ideas of Peres, Schramm, Sheffield and Wilson and use the game random turn tug of war but instead consider a biased coin. We will discuss the differences that arise in the proofs of the existence and uniqueness of the corresponding partial differential equation. This talk is based on joint work with Yuval Peres and Gabor Pete.

• November 2: Oren Louidor (Courant Institute)

Finite connections for supercritical Bernoulli bond percolation in 2D

Two vertices are said to be finitely connected if they belong to the same cluster and this cluster is finite. We derive sharp asymptotics for finite connection probabilities for supercritical Bernoulli bond percolation on Z^2.

• November 9: Ionel Popsecu (Georgia Tech)

Analyticity and the Planar Limit

The planar limit is a combinatorial generating function which counts the number of planar graphs of arbitrary valency and this is very closely connected to random matrix calculations. On the other hand an analytic treatment of the random matrix reduces the problem to studying the minimizer of the so called logarithmic energy with external field.

We will show an elementary way of dealing with the minimizer of the logarithmic energy with external fields. This is based on manipulations of Chebyshev polynomials and combinatorial identities which give a nice new formula for the minimum of the energy. This indicates why the analyticity claim of the planar limit holds true.

We also were able to compute some of the various planar limit in closed form.

This is joint work with Stavros Garoufalidis and Marcos Marinio.

• November 16: Laurent Saloff-Coste (Cornell)

Dirichlet heat kernel estimates in Euclidean domains

For what type of Euclidean domains can one derive precise two-sided Dirichlet heat kernel estimates that capture both the usual diffusion effects and the killing at the boundary? We shall see how a combination of interesting techniques allows to obtain such estimates for a large (and, in a sense, optimal) class of domains called inner uniform domains.

• November 23: Ivan Corwin (NYU)

Fluctuations in traffic flow, crystal growth and random matrices

Analogous to the central limit theorem, we study the asymptotic behavior of the fluctuations of traffic flow, crystal growth height and eigenvalues of random matrices around their expectations. We show how the fluctuation limits of these random processes are related to their respective expectations (hydrodynamic limits).

• November 30: Mihyun Kang (Technische Universitaet Berlin)

Critical behaviour of random planar graphs

Since the seminal work of Erd"os and R'enyi the phase transition of the largest components in random graphs became one of the central topics in random graph theory and discrete probability theory. In this talk we discuss the critical behaviour of the largest components in a uniform random planar graph. (Joint work with Tomasz Luczak.)

• December 7: Rick Kenyon (Brown University)