The octahedral recurrence, or Hirota equation, is a well-known integrable
discrete dynamical system, related to alternating sign matrices and
domino tilings
of Aztec diamonds.
Surprisingly, there is an underlying completely integrable Hamiltonian system.
Formulas relating it to the octahedral recurrence
can be written explicitly in terms of dimers.
Similar systems exist for any periodic planar bipartite graph.
This is joint work with A. Goncharov.
Liouville quantum gravity and the Schramm-Loewner evolution (SLE) rank
among the great mathematical physics discoveries of the last few
decades. Liouville quantum gravity is a canonical model of a random
two dimensional Riemannian manifold. It was introduced by Polyakov in
1981 as a model for the intrinsic geometry on the space-time
trajectory of a string. The Schramm-Loewner evolution, introduced by
Schramm in 1999, is a canonical model of a random path in the plane
that doesn't cross itself. Each of these models is the subject of a
large and active literature spanning physics and mathematics.
We will connect these two objects to each other in the simplest
possible way. Roughly speaking, we will show that if one glues
together two independent Liouville quantum gravity random surfaces
along boundary segments (in a boundary-length-preserving way) --- and
then conformally maps the resulting surface to a planar domain ---
then the interface between the two surfaces is an SLE.
In a sense, the welding/subdivision of random surfaces (which
parameterize string trajectories) is analogous to the
concatenation/subdivision of one-dimensional time intervals (which
parameterize point-particle trajectories).
We show that the threshold for a subset sampled uniformly from the
range of a random walk on $\Z_n^d$, $d \geq 3$, to become
indistinguishable from a uniformly chosen subset of $\Z_n^d$ is $1/2$
the cover time. As a consequence of our methods, we show that the
total variation mixing time of the random walk on the lamplighter
graph $\Z_2 \wr \Z_n^d$, $d \geq 3$, has a cutoff with threshold at
$1/2$ the cover time. We given a general criterion under which both
of these results hold; other examples for which this applies include
bounded degree expander families, the intersection of an infinite
supercritical percolation cluster with an increasing family of balls,
the hypercube, and the Caley graph of the symmetric group generated by
transpositions. The proof also yields precise asymptotics for the
decay of correlation in the uncovered set.
This is joint work with Yuval Peres
The GOE, or Gaussian Orthogonal Ensemble, is a Gaussian measure on the set of orthogonal matrices. We consider the problem of finding the nth moment of the eigenvalues of the matrices in the GOE. It turns out that this problem is closely related to a question about the different ways of gluing the edges of a 2n-gon in pairs so as to create a surface without boundary. More precisely, among the (2n)!/n! possible gluings, how many times does one get each surface (considered up to homeomorphism)?
In this talk, I will recall the connection between the two questions, and present a bijective solution.
Our results are analogous to the one obtained by Harer and Zagier (1986) about the gluings of a 2n-gon giving an orientable surface (or in matrix terms, about the Gaussian Unitary Ensemble). Our solution is partly inspired by a combinatorial proof due to Bodo Lass of the Harer-Zagier formula.
Schramm-Loewner evolution (SLE) describes a single random
curve growing in a plane domain. A number of critical two-dimensional
lattice models have SLE as their scaling limits. In this talk, I will
explain a probability tool called stochastic coupling technique, which
is used to grow two SLE curves simultaneously in a single domain, so
that the two curves commute with each other. I will also explain the
application of this technique in proving the following problems: 1.
Reversibility of chordal SLE for $\kappa\leq 4$; 2. Duality of SLE; 3.
Reversibility of whole-plane SLE for $\kappa\leq 4$; and 4. SLE$_2$
could be obtained by erasing loops on a planar Brownian motion.
Interior point methods are deterministic algorithms that
optimize convex functions over high dimensional convex sets. An
interior point method
first equips a convex set with a Riemannian metric that sends its
boundary to infinity (thus avoiding boundary effects)
and then performs a steepest descent to minimize the objective on the
resulting Riemannian manifold. We will describe a randomized variant
of an interior point
method known as ``the affine scaling algorithm" introduced by
I.I.Dikin in 1967. This variant, which we term Dikin walk, corresponds
to a natural random walk on the same manifold on which affine scaling
would perform steepest descent. We discuss applications to sampling
and
optimization and prove polynomial bounds on the
mixing time of the associated Markov Chain. For
n-dimensional polytopes with O(n^{2-\epsilon}) faces, the bounds on
the mixing time are better than the bounds of previous Markov Chains for
sampling from high dimensional convex sets. Finally, we will discuss
how some of these ideas can be used to approximately count certain
representation theoretic multiplicities known as
Littlewood-Richardson coefficients in randomized strongly polynomial time.
This talk includes work done in collaboration with Ravi Kannan and
Alexander Rakhlin.
I'll present a generalization Krieger's finite generation
theorem, giving conditions for an ergodic system to be generated by
two partitions, each required to be measurable with respect to a given
sub-algebra, and also required to have a fixed size. This is a joint
work with Benjamin Weiss.
In parallel chip firing, we start with some number of chips on each
vertex of a graph, and evolve by parallel firing: in each time step,
every vertex that has at least as many chips as neighbors, fires one
chip to each neighbor. It has been observed that if we start with the
chips uniformly at random placed on a large graph, then the 'density'
(average number of chips per vertex) suffices to predict with high
accuracy the 'activity' (average number of firing vertices per time
step). A plot of the activity as a function of the density reminds one
of a staircase. I will show several examples and the proof of our
staircase theorem for the flower graph.
The second part of the talk will be about a popular theory of
self-organized criticality, that relates the critical behavior of
driven dissipative systems to that of systems with conservation. In
particular, this theory predicts that the stationary density of the
driven abelian sandpile model should be equal to the threshold density
of the corresponding parallel chip firing model. This "density
conjecture" has been proved for the underlying graph Z. Research into
this conjecture has focused mainly on the underlying graph Z^2: the
stationary density was proved to be equal to 17/8 to at least twelve
decimals, while the threshold density was simulated to be 2,125 to
three decimals.
We have investigated both the driven sandpile model and the parallel
chip firing model for several graphs, and we show (by large-scale
simulation or by proof) that the stationary density is not equal to
the threshold density when the underlying graph is any of Z^2, the
complete graph K_n, the Cayley tree, the ladder graph, the bracelet
graph, or the flower graph.
Joint work with Lionel Levine and David Wilson.
We propose and study a random graph model on the
hypercubic lattice that interpolates between models
of scale-free random graphs and long-range percolation.
In our model, each vertex x has a weight W_x, where the weights
of different vertices are i.i.d. random variables. Given the weights, the
edge between x and y is, independently of all other edges,
occupied with probability 1-e^{-\lambda W_xW_y/|x-y|^{\alpha}},
where
(a) \lambda is the percolation parameter,
(b) |x-y| is the Euclidean distance between x and y, and
(c) \alpha is a long-range parameter.
The most interesting behavior can be observed when
the random weights have a power-law distribution, i.e.,
when P(W_x>w) is regularly varying with exponent 1-\tau
for some \tau>1. In this case, we see that the degrees are infinite
a.s. when \gamma =\alpha(\tau-1)/d <1, while the degrees
have a power-law distribution with exponent \gamma
when \gamma>1.
Our main results describe phase transitions in the
positivity of the critical value and in the graph distances
in the percolation cluster as \gamma varies.
Let \lambda_c denote the critical value of
the model. Then, we show that \lambda_c=0 when
\gamma<2, while \lambda_c>0 when \gamma>2.
Further, conditionally on 0 and x being connected,
the graph distance between 0 and x is of order \log\log|x|
when \gamma<2 and at least of order \log|x| when \gamma>2.
These results are similar to the ones in inhomogeneous
random graphs, where a wealth of further results is known.
We also discuss many open problems, inspired both by
recent work on long-range percolation (i.e., W_x=1 for every x),
and on inhomogeneous random graphs (i.e., the model on the
complete graph of size n and where |x-y|=n for every x\neq y).
[This is joint work with Mia Deijfen and Gerard Hooghiemstra.]
We consider the Glauber dynamics for the 3D Ising model at
zero temperature, with "+" boundary conditions. We prove that the time
which an initial domain of linear size L of "-" spins requires to
become entirely "+" is of order $L^2$ (as predicted by the mean
curvature motion heuristics), apart from logarithmic corrections. The
proof involves the mapping of monotone discrete surfaces into dimer
coverings of the infinite hexagonal lattice, plus a coupling argument
to estimate the mixing time of a stochastic dynamics for finite
monotone surfaces with fixed boundary. This monotone surface dynamics
has an interst by itself, since it corresponds to the zero temperature,
3D Ising dynamics with Dobrushin-type boundary conditions which impose
the presence
of a single interface between "+" and "-" spins. (Talk based on: P.
Caputo, F. Martinelli, F. Simenhaus, F. Toninelli, CPAM 2011 and on
Caputo-Martinelli-Toninelli, arXiv:1101.4190v1)