Schedule

• September 14

  Bertrand Duplantier (Institute for Theoretical Physics, Saclay)

  A Rigorous Perspective on Liouville Quantum Gravity and KPZ

  Abstract: Liouville quantum gravity in two dimensions is described by the "random Riemannian manifold" obtained by changing the Lebesgue measure $dz$ in the plane by a random conformal factor $\exp [\gamma h(z)]$, where $h(z)$ is a random function called the Gaussian Free Field, and $\gamma$ a parameter.

  This "random surface" is believed to be the continuum scaling limit of certain discretized random surfaces that can be studied with combinatorics and random matrix theory.

  A famous formula, due to Knizhnik, Polyakov and Zamolodchikov in '88, relates standard critical exponents in the Euclidean plane to their counterparts on the random surfaces mentioned above. We describe a recent proof of the KPZ formula in the probabilistic setting given above.

  (joint work with Scott Sheffield, MIT)

• September 16

  Joint MIT probability seminar and Microsoft Research colloquium, 4pm Wednesday, first floor conference center, One Memorial Drive, Cambridge

  Elchanan Mossel (Weizmann Institute and U.C. Berkeley)

  Quantitative Social Choice Theory

  Abstract: Results in economics established in 50s-70s imply that there is no rational way to rank or elect a winner when there are 3 or more alternatives.

  We will consider the following question: Is it possible to rank or elect a winner in a way that is typically rational even if for some specific unlikely preferences of the voters it is not.

  The talk will provide historical background on the topic as well as hints to some of the exotic mathematical tools that are used in this theory. These include inverse hyper-contractive estimates, non-linear invariance and a new isoperemetric theory involving interfaces between 3 bodies.

• September 21

  David Wilson (Microsoft Research)

  Double-dimer pairings and skew Young diagrams

  Abstract: We study the number of tilings of skew Young diagrams by ribbon tiles shaped like Dyck paths, in which the tiles are "vertically decreasing". We use these quantities to compute pairing probabilities in the double-dimer model. Given a planar bipartite graph G with special vertices, called nodes, on the outer face, the double-dimer model is formed by the superposition of a uniformly random dimer configuration (perfect matching) of G together with a random dimer configuration of the graph formed from G by deleting the nodes. The double-dimer configuration consists of loops, doubled edges, and chains that start and end at the boundary nodes. We are interested in how the chains connect the nodes. An interesting special case is when the graph is epsilon (Z x N) and the nodes are at evenly spaced locations on R as the grid spacing epsilon goes to 0.

  Joint work with Rick Kenyon.

• September 28

  No seminar

• September 29

  Tuesday at 4:30 in 2-147

  Stochastic Seminar Evarist Giné (University of Connecticut)

  Adaptive confidence bands for densities.

  Abstract: It is shown that a version of the Bickel-Rosenblatt (1973) distributional limit theorem for the supremum over an interval of the discrepancy between a density and its kernel density estimator extends to some linear wavelet estimators (with some changes). This is then used in the construction of adaptive confidence bands that are honest forall densities in a 'generic' subset of the union of t-Holder balls, 0 < t < r, for some fixed but arbitrary integer r.

  This talk is based on joint work with Richard Nickl.

• October 5

  Olivier Bernardi (MIT)

  Correspondences between subgraphs, orientations and sandpile configurations

  Abstract: Any graph has the same number of spanning trees, recurrent sandpile configurations and root-connected score vectors. In this talk, I will present bijections between these structures. We will also present a bijection between connected subgraphs and root-connected orientations, and a bijection between spanning forests and score vectors.

  All these bijections are obtained as specializations of a general correspondence between spanning subgraphs and orientations. The definition and analysis of this correspondence are related to a characterization of the Tutte polynomial using an embedding of the graph.

• October 8

  Gil Kalai (Hebrew University of Jerusalem & Yale University)

  Noise Sensitivity, Noise Stability, Percolation and some connections to TCS.

  Abstract: Noise sensitivity was defined in a paper by Benjamini, Kalai, and Schramm (1999). A closely related notion was considered by Tsirelson and Vershik. I will describe the notion of noise sensitivity of Boolean functions and some basic results and problems related to it. A fun way to explain it (especially after 2000) is in terms of the probability that small mistakes in counting the votes in an election will change the outcome. We will consider the following:

  1. The definition of noise sensitivity, and how it is described in terms of the Fourier transform.
  2. Noise sensitivity of the crossing event in Percolation (BKS 99, Schramm and Steiff 2005, and finally Garban, Pete, Schramm 2008), the scaling limit for the Spectral distribution (Schramm and Smirnov, 2007, GPS 2008), and dynamic percolation. (ScSt (2005), GPS (2008)). Other cases of noise sensitivity.
  3. Noise stability of the majority function, of weighted majority. A conjecture regarding the situation for functions described by monotone depth monotone threshold circuits.
  4. The "majority is stablest theorem" (Mossel, O'Donnell, Oleszkiewicz 05) and the connection to hardness of approximation.

  (Some more related things can be found here: http://gilkalai.wordpress.com/2009/03/06/noise-sensitivity-lecture-and-tales/ )

• October 13

  Tuesday, but MIT schedule = Monday; regular time and room: 2-190 3-4pm

  Fan Chung (UC San Diego)

  Percolation on general graphs

  Abstract: We will discuss several problems with a percolation flavor while the given host graphs can be non-regular and sparse in general. To control the percolation, some old and new graph invariants play crucial roles. We will describe some of these graph invariants including the hitting time, the Green's function and the PageRank of graphs. Some related applications in epidemiology and approximation algorithms will also be mentioned.

• October 19

  Jian Ding (Berkeley)

  Near-critical random graph: its structure, diameter and mixing time

  In this talk, I will present a complete description of the giant component of the Erd\H{o}s-R\'enyi random graph $G(n,p)$ as soon as it emerges from the scaling window, i.e., for $p = (1+\epsilon)/n$ where $\epsilon^3 n \to \infty$ and $\epsilon=o(1)$.

  Our description is particularly simple for $\epsilon = o(n^{-1/4})$, where the giant component $C_1$ is contiguous with the following model (i.e., every graph property that holds with high probability for this model also holds w.h.p. for $C_1$). Let $Z$ be normal with mean $\frac23 \epsilon^3 n$ and variance $\epsilon^3 n$, and let $K$ be a random 3-regular graph on $2[Z]$ vertices. Replace each edge of $K$ by a path, where the path lengths are i.i.d. geometric with mean $1/\epsilon$. Finally, attach an independent Poisson($1-\epsilon$)-Galton-Watson tree to each vertex.

  A similar picture is obtained for larger $\epsilon=o(1)$, in which case the random 3-regular graph is replaced by a random graph with $N_k$ vertices of degree $k$ for $k\geq 3$, where $N_k$ has mean and variance of order $\epsilon^k n$.

  Based on this description, we show that for any $\epsilon=o(1)$ with $\epsilon^3n\to\infty$, the diameter of $C_1$ is w.h.p. asymptotic to $D (\epsilon,n)=(3/\epsilon)\log(\epsilon^3 n)$. Furthermore, we prove that the mixing time for the random walk on $C_1$ is w.h.p. of order $\epsilon^{-3}\log^2 (\epsilon^3 n)$.

  Based on joint work with J.H. Kim, E. Lubetzky and Y. Peres.

• October 26

  Stephanie Somersille (U. Texas)

  Biased Tug of War, The Biased Infinity Laplacian and Comparison with Exponential Cones

  Abstract: We use the game Biased Tug of War to prove results for a degenerate elliptic second order partial differential equation involving the infinity Laplacian operator and the norm of the gradient. We extend the ideas of Peres, Schramm, Sheffield and Wilson and use the game random turn tug of war but instead consider a biased coin. We will discuss the differences that arise in the proofs of the existence and uniqueness of the corresponding partial differential equation. This talk is based on joint work with Yuval Peres and Gabor Pete.

• November 2

  Oren Louidor (Courant Institute)

  Finite connections for supercritical Bernoulli bond percolation in 2D

  Abstract: Two vertices are said to be finitely connected if they belong to the same cluster and this cluster is finite. We derive sharp asymptotics for finite connection probabilities for supercritical Bernoulli bond percolation on Z^2.

• November 9

  Ionel Popsecu (Georgia Tech)

  Analyticity and the Planar Limit

  Abstract: The planar limit is a combinatorial generating functionwhich counts the number of planar graphs of arbitrary valency and thisis very closely connected to random matrix calculations. On theother hand an analytic treatment of the random matrix reduces theproblem to studying the minimizer of the so called logarithmic energywith external field.

  We will show an elementary way of dealing with the minimizer of thelogarithmic energy with external fields. This is based onmanipulations of Chebyshev polynomials and combinatorial identitieswhich give a nice new formula for the minimum of the energy. Thisindicates why the analyticity claim of the planar limit holds true.

  We also were able to compute some of the various planar limit in closed form.

  This is joint work with Stavros Garoufalidis and Marcos Marinio.

• November 16

  (Seminar Canceled)

• November 23

  Ivan Corwin (NYU)

  Fluctuations in traffic flow, crystal growth and random matrices

  Abstract: Analogous to the central limit theorem, we study theasymptotic behavior of the fluctuations of traffic flow, crystalgrowth height and eigenvalues of random matrices around theirexpectations. We show how the fluctuation limits of these randomprocesses are related to their respective expectations (hydrodynamiclimits).

• November 30

  Mihyun Kang (Technische Universitaet Berlin)

  Critical behaviour of random planar graphs

  Abstract: Since the seminal work of Erd"os and R'enyi the phase transition of thelargest components in random graphs became one of the central topics inrandom graph theory and discrete probability theory. In this talk wediscuss the critical behaviour of the largest components in a uniformrandom planar graph. (Joint work with Tomasz Luczak.)

• December 7

  Rick Kenyon (Brown University)

  Connections in spanning trees.

  Abstract: We discuss the uniform spanning tree modelon a planar graph and in particular howto compute certain long-range propertiesusing the vector-bundle laplacian.