Spring 2011
Monday 4.15  5.15 pm
Room 2147
Schedule

February 7
Richard Kenyon (Brown University)
Dimers and the generalized octahedral recurrence
Abstract: The octahedral recurrence, or Hirota equation, is a wellknown integrablediscrete dynamical system, related to alternating sign matrices anddomino tilingsof Aztec diamonds.Surprisingly, there is an underlying completely integrable Hamiltonian system.Formulas relating it to the octahedral recurrencecan be written explicitly in terms of dimers.Similar systems exist for any periodic planar bipartite graph.
This is joint work with A. Goncharov.

February 14
Scott Sheffield (MIT)
How do you divide your (two dimensional) time? Zippers, necklaces, and quantum gravity
Abstract: Liouville quantum gravity and the SchrammLoewner evolution (SLE) rankamong the great mathematical physics discoveries of the last fewdecades. Liouville quantum gravity is a canonical model of a randomtwo dimensional Riemannian manifold. It was introduced by Polyakov in1981 as a model for the intrinsic geometry on the spacetimetrajectory of a string. The SchrammLoewner evolution, introduced bySchramm in 1999, is a canonical model of a random path in the planethat doesn't cross itself. Each of these models is the subject of alarge and active literature spanning physics and mathematics.
We will connect these two objects to each other in the simplestpossible way. Roughly speaking, we will show that if one gluestogether two independent Liouville quantum gravity random surfacesalong boundary segments (in a boundarylengthpreserving way)  andthen 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 (whichparameterize string trajectories) is analogous to theconcatenation/subdivision of onedimensional time intervals (whichparameterize pointparticle trajectories).

February 22
Jason Miller (Microsoft Research)
Uniformity of the Uncovered Set of Random Walk and Cutoff for Lamplighter Chains
Abstract: 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 becomeindistinguishable from a uniformly chosen subset of $\Z_n^d$ is $1/2$the cover time. As a consequence of our methods, we show that thetotal variation mixing time of the random walk on the lamplightergraph $\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 bothof these results hold; other examples for which this applies includebounded degree expander families, the intersection of an infinitesupercritical percolation cluster with an increasing family of balls,the hypercube, and the Caley graph of the symmetric group generated bytranspositions. The proof also yields precise asymptotics for thedecay of correlation in the uncovered set.This is joint work with Yuval Peres

February 28
Olivier Bernardi (MIT)
Computing the moments of the GOE bijectively
Abstract: 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 2ngon 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 2ngon 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 HarerZagier formula.

March 7
Dapeng Zhan (MSU)
A stochastic coupling technique in the study of SLE
Abstract: SchrammLoewner evolution (SLE) describes a single random curve growing in a plane domain. A number of critical twodimensionallattice models have SLE as their scaling limits. In this talk, I willexplain a probability tool called stochastic coupling technique, whichis used to grow two SLE curves simultaneously in a single domain, sothat the two curves commute with each other. I will also explain theapplication of this technique in proving the following problems: 1.Reversibility of chordal SLE for $\kappa\leq 4$; 2. Duality of SLE; 3.Reversibility of wholeplane SLE for $\kappa\leq 4$; and 4. SLE$_2$could be obtained by erasing loops on a planar Brownian motion.

March 14
Hariharan Narayanan (MIT)
Randomized Interior Point Methods for Sampling and Optimization
Abstract: Interior point methods are deterministic algorithms that optimize convex functions over high dimensional convex sets. Aninterior point method first equips a convex set with a Riemannian metric that sends itsboundary to infinity (thus avoiding boundary effects)and then performs a steepest descent to minimize the objective on theresulting Riemannian manifold. We will describe a randomized variantof an interior pointmethod known as ``the affine scaling algorithm" introduced byI.I.Dikin in 1967. This variant, which we term Dikin walk, correspondsto a natural random walk on the same manifold on which affine scalingwould perform steepest descent. We discuss applications to samplingandoptimization and prove polynomial bounds on themixing time of the associated Markov Chain. Forndimensional polytopes with O(n^{2\epsilon}) faces, the bounds onthe mixing time are better than the bounds of previous Markov Chains forsampling from high dimensional convex sets. Finally, we will discusshow some of these ideas can be used to approximately count certainrepresentation theoretic multiplicities known asLittlewoodRichardson coefficients in randomized strongly polynomial time.This talk includes work done in collaboration with Ravi Kannan andAlexander Rakhlin.

March 28
Nir Avni (Harvard)
Generating Product Systems
Abstract: 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 subalgebra, and also required to have a fixed size. This is a joint work with Benjamin Weiss.

April 4
Anne Feyden Boer (TU Delft)
Sandpiles, staircases and selforganized criticality
Abstract: In parallel chip firing, we start with some number of chips on eachvertex of a graph, and evolve by parallel firing: in each time step,every vertex that has at least as many chips as neighbors, fires onechip to each neighbor. It has been observed that if we start with thechips uniformly at random placed on a large graph, then the 'density'(average number of chips per vertex) suffices to predict with highaccuracy the 'activity' (average number of firing vertices per timestep). A plot of the activity as a function of the density reminds oneof a staircase. I will show several examples and the proof of ourstaircase theorem for the flower graph.The second part of the talk will be about a popular theory ofselforganized criticality, that relates the critical behavior ofdriven dissipative systems to that of systems with conservation. Inparticular, this theory predicts that the stationary density of thedriven abelian sandpile model should be equal to the threshold densityof the corresponding parallel chip firing model. This "densityconjecture" has been proved for the underlying graph Z. Research intothis conjecture has focused mainly on the underlying graph Z^2: thestationary density was proved to be equal to 17/8 to at least twelvedecimals, while the threshold density was simulated to be 2,125 tothree decimals.
We have investigated both the driven sandpile model and the parallelchip firing model for several graphs, and we show (by largescalesimulation or by proof) that the stationary density is not equal tothe threshold density when the underlying graph is any of Z^2, thecomplete graph K_n, the Cayley tree, the ladder graph, the braceletgraph, or the flower graph.
Joint work with Lionel Levine and David Wilson.

April 11
Remco van der Hofstad (Eindhoven University of Technology)
Scalefree percolation
Abstract: We propose and study a random graph model on thehypercubic lattice that interpolates between modelsof scalefree random graphs and longrange percolation.In our model, each vertex x has a weight W_x, where the weightsof different vertices are i.i.d. random variables. Given the weights, theedge between x and y is, independently of all other edges,occupied with probability 1e^{\lambda W_xW_y/xy^{\alpha}},where
 \lambda is the percolation parameter,
 xy is the Euclidean distance between x and y, and
 \alpha is a longrange parameter.
The most interesting behavior can be observed whenthe random weights have a powerlaw distribution, i.e.,when P(W_x>w) is regularly varying with exponent 1\taufor some \tau>1. In this case, we see that the degrees are infinitea.s. when \gamma =\alpha(\tau1)/d <1, while the degreeshave a powerlaw distribution with exponent \gammawhen \gamma>1.
Our main results describe phase transitions in thepositivity of the critical value and in the graph distancesin the percolation cluster as \gamma varies.Let \lambda_c denote the critical value ofthe 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\logxwhen \gamma<2 and at least of order \logx when \gamma>2.These results are similar to the ones in inhomogeneousrandom graphs, where a wealth of further results is known.
We also discuss many open problems, inspired both byrecent work on longrange percolation (i.e., W_x=1 for every x),and on inhomogeneous random graphs (i.e., the model on thecomplete graph of size n and where xy=n for every x\neq y).[This is joint work with Mia Deijfen and Gerard Hooghiemstra.]

April 18
No seminar (Patriots' Day)

April 25
No seminar (Simons Lectures)

May 2
Fabio Toninelli (Ecole Normale SupĂ©rieure de Lyon)
On the zero temperature dynamics of the 3D Ising model
Abstract: 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 Dobrushintype 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 CaputoMartinelliToninelli, arXiv:1101.4190v1)
Spring 2011 Organizers
 Olivier Bernardi
 Alexei Borodin
 Lionel Levine
 Asaf Nachmias
 Scott Sheffield