# MIT Probability Seminar - Fall 2010

### Monday 4.15 - 5.15 pm Room 2-136

Organizers: Olivier Bernardi, Alexei Borodin, Lionel Levine, Asaf Nachmias, Scott Sheffield.

### Schedule:

• September 20: Asaf Nachmias (MIT)

Random walks on random fractals and the Alexander-Orbach conjecture

A simple random walk on the Euclidean lattice reaches distance of about n^{1/2} after n steps. On a (discrete) fractal, we expect the random walker to spend most of its time on the "dangling ends" of the fractal and hence to slow down significantly. Alexander and Orbach (1982) conjectured that on fractals obtained from critical percolation on a lattice, the random walker reaches distance of about n^{1/3} after n steps. In this work we prove this conjecture when the dimension of the lattice is larger than 6.
Based on joint work with Gady Kozma.

• September 27: David Jerison (MIT)

Internal Diffusion-Limited Aggregation.

Internal diffusion limited aggregation (IDLA) is a random growth model on the lattice defined for each integer time $n \geq 0$ by an {\bf occupied set} $A(n) \subset \mathbb Z^2$ as follows: begin with $A(0) = \emptyset$, $A(1) = \{0\}$, and then for each $n$ add to $A(n)$ the first point at which a random walk from the origin hits $\Z^2 \setminus A(n)$. IDLA was introduced by Meakin and Deutch in 1986 as a model for chemical processes such as electopolishing, corrosion and etching. We discuss joint work with Lionel Levine and Scott Sheffield in which we show that the deviation of $A(n)$ from the disk is logarithmic in the radius, $r = \sqrt{n/\pi}$: There is an absolute constant $C$ such that almost surely for sufficiently large $n$, $B_{r - C\log r} \subset A(n) \subset B_{r+ C\log r}$ Moreover, the fluctuations can be described by a variant of the Gaussian Free Field. This allows us to confirm numerical predictions made by Meakin and Deutch.

• October 4: Horng-Tzer Yau (Harvard)

Universality of random matrices and Dyson Brownian Motion.

Random matrices were introduced by E. Wigner to model the excitation spectrum of large nuclei. The central idea is based on the hypothesis that the local statistics of the excitation spectrum for a large complicated system is universal in the sense that it depends only on the symmetry class of the physical system but not on other detailed structures. Dyson Brownian motion is the flow of eigenvalues of random matrices when each matrix element performs independent Brownian motions. In this lecture, we will explain the connection between the universality of random matrices and the approach to local equilibrium of Dyson Brownian motion. The main tools in our approach are an estimate on the flow of entropy in Dyson Brownian motion and a local semicircle law.

• October 11: Columbus Day.

• October 18: Curtis McMullen (Harvard)

Barycentric subdivision and random walks on the hyperbolic plane.

• October 25: Jacob Fox (MIT)

Dependent Random Choice.

We describe a simple and yet surprisingly powerful probabilistic technique which shows how to find in a dense graph a large subset of vertices in which all (or almost all) small subsets have many common neighbors. Recently this technique has had several striking applications to Extremal Graph Theory, Ramsey Theory, Additive Combinatorics, and Combinatorial Geometry. In this talk, which is based on a survey with Benny Sudakov, we discuss some of these applications.

• November 1: Alexei Borodin (MIT)

Growth of random surfaces

We describe a class of exactly solvable random growth models of one and two-dimensional interfaces. The growth is local (distant parts of the interface grow independently), it has a smoothing mechanism (fractal boundaries do not appear), and the speed of growth depends on the local slope of the interface. The models enjoy a rich algebraic structure that is reflected through closed determinantal formulas for the correlation functions. Large time asymptotic analysis of such formulas reveals asymptotic features of the emerging interface in different scales. Macroscopically, a deterministic limit shape phenomenon can be observed. Fluctuations around the limit shape range from universal laws of Random Matrix Theory to conformally invariant Gaussian processes in the plane. On the microscopic (lattice) scale, certain universal determinantal random point processes arise.

• November 8: Jason Miller (Microsoft research)

CLE(4) and the Gaussian Free Field

The discrete Gaussian free field (DGFF) is the Gaussian measure on functions $h \colon D \to \R$, $D \subseteq \Z^2$ bounded, with covariance given by the Green's function for simple random walk. The graph of $h$ is a random surface which serves as a physical model for an effective interface. We show that the collection of random loops given by the level sets of the DGFF for any height $\mu \in \R$ converges in the fine-mesh scaling limit to a family of loops which is invariant under conformal transformations when $D$ is a lattice approximation of a non-trivial simply connected domain. In particular, there exists $\lambda > 0$ such that the level sets whose height is an odd integer multiple of $\lambda$ converges to a nested conformal loop ensemble with parameter $\kappa=4$ [so-called $\CLE(4)]$, a conformally invariant measure on loops which locally look like $\SLE(4)$. Using this result, we give a coupling of the continuum Gaussian free field (GFF), the fine-mesh scaling limit of the DGFF, and $\CLE(4)$ such that the GFF can be realized as a functional of $\CLE(4)$ and conversely $\CLE(4)$ can be made sense as a functional of the GFF. This is joint work with Scott Sheffield.

• November 15: Fredrik Johansson Vilkund (Columbia University)

Convergence rates for loop-erased random walk

Loop-erased random walk (LERW) is a self-avoiding random walk obtained by chronologically erasing the loops of a simple random walk. In the plane, the lattice size scaling limit of LERW is known to be SLE(2), a random fractal curve constructed by solving the Loewner differential equation with a Brownian motion input. In the talk, we will discuss recent joint work with C. Benes (CUNY) and M. Kozdron (U. of Regina) on obtaining a rate for the convergence of LERW to SLE(2). More precisely, we will outline our derivation of a rate for the convergence of the Loewner driving function for LERW to Brownian motion with speed 2 on the unit circle, the Loewner driving function for SLE(2). We will then show how to use this to obtain a rate for the convergence of the paths with respect to Hausdorff distance. Time permitting, we will also indicate how some of these results can be extended to certain other models known to converge to SLE.

• November 22: Tim Austin (Brown University)

Compression exponents for finitely generated groups.

One key insight behind geometric group theory is that some algebraic properties of infinite discrete groups can be understood by considering them more coarsely as discrete metric spaces with their word metrics. One invariant for such groups arising in this way is their compression exponent, an indicator of how badly that metric must be distorted if the group is embedded into various classes of Banach space. I will review this definition and some results relating it to the algebraic structure of the group, and then discuss some examples of groups for which the exact values of these exponents are known, and in particular the (usually less obvious) arguments that go into bounding them from above (i.e., `putting an upper bound on the quality of an arbitrary embedding').

• November 29: Clement Hongler (Columbia University)

Critical Ising crossing probabilities and SLE

We study the Ising model at criticality from an SLE point of view. The interfaces between + and - spins of the Ising model with Dobrushin +/- boundary conditions have been shown to converge to SLE(3) by Smirnov (on the square lattice) and Chelkak and Smirnov (on more general lattices), thanks to the introduction and proof of convergence of a discrete holomorphic martingale observable in this setup. We show conformal invariance of the Ising interfaces in presence of free boundary conditions. In particular we prove the conjecture of Bauer, Bernard and Houdayer about the scaling limit of interfaces arising in a so-called dipolar setup. The limiting process is a Loewner chain guided by a drifted Brownian motion, known as dipolar SLE or SLE(3,-3/2) in the literature. This case is made harder by the absence of natural discrete holomorphic martingales, requiring us to introduce "exotic" martingale observables. The study of these observables is performed by Kramers-Wannier duality and Edwards-Sokal coupling, and the computation of the scaling limit is made by appealing to discrete complex analysis methods, to three existing convergence results about discrete fermions, to the scaling limit of critical Fortuin-Kasteleyn model interfaces and to the introduction of Coulomb gas integrals. Our result allows to show conjectures by Langlands, Lewis and Saint-Aubin about conformal invariance of crossing probabilities for the Ising model. Based on joint work with Kalle Kytölä and work in progress with Hugo Duminil-Copin

• December 6: James Lee (University of Washington)

Cover times, blanket times, and the Gaussian free field

The cover time of a finite graph (the expected time for the simple random walk to visit all the vertices) has been extensively studied, yet a number of fundamental questions concerning cover times have remained open. Winkler and Zuckerman (1996) defined the blanket time (when the empirical distribution if within a factor of 2, say, of the stationary distribution) and conjectured that the blanket time is always within O(1) of the cover time. Aldous and Fill (1994) asked whether there is a deterministic polynomial-time algorithm that computes the cover time up to an O(1) factor. The best approximation factor found so far for both these problems was (log log n)^2 for n-vertex graphs, due to Kahn, Kim, Lovasz, and Vu (2000). We show that the cover time of a graph, appropriately normalized, is proportional to the expected maximum of the (discrete) Gaussian free field on G. We use this connection and Talagrand's majorizing measures theory to deduce a positive answer to the question of Aldous and Fill and to establish the conjecture of Winkler and Zuckerman. These results extend to arbitrary reversible finite Markov chains. This is joint work with Jian Ding (U. C. Berkeley) and Yuval Peres (Microsoft Research).

Probability seminars in past semesters: Fall 2008 : Spring 2009 : Fall 2009 : Spring 2010