Schedule

• February 7

  Richard Kenyon (Brown University)

  Dimers and the generalized octahedral recurrence

  Abstract: The octahedral recurrence, or Hirota equation, is a well-known 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 Schramm-Loewner 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 space-timetrajectory of a string. The Schramm-Loewner 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 boundary-length-preserving 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 one-dimensional time intervals (whichparameterize point-particle 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 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.

• March 7

  Dapeng Zhan (MSU)

  A stochastic coupling technique in the study of SLE

  Abstract: Schramm-Loewner evolution (SLE) describes a single random curve growing in a plane domain. A number of critical two-dimensionallattice 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 whole-plane 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. Forn-dimensional 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 asLittlewood-Richardson 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 sub-algebra, and also required to have a fixed size. This is a joint work with Benjamin Weiss.

• April 4

  Anne Fey-den Boer (TU Delft)

  Sandpiles, staircases and self-organized 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 ofself-organized 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 large-scalesimulation 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)

  Scale-free percolation

  Abstract: We propose and study a random graph model on thehypercubic lattice that interpolates between modelsof scale-free random graphs and long-range 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 1-e^{-\lambda W_xW_y/|x-y|^{\alpha}},where

  1. \lambda is the percolation parameter,
  2. |x-y| is the Euclidean distance between x and y, and
  3. \alpha is a long-range parameter.

  The most interesting behavior can be observed whenthe random weights have a power-law 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(\tau-1)/d <1, while the degreeshave a power-law 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\log|x|when \gamma<2 and at least of order \log|x| 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 long-range 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 |x-y|=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 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)