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.
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.
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.
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.
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.
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.
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').
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
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).