Schedule

• October 14

  Peter Winkler (Dartmouth)

  Coordinate Percolation

  Abstract: In coordinate percolation, i.i.d. random variables are associated with the lines of a grid, and the life or death of each vertex depends on the values assigned to the lines that cross there. Coordinate percolation arises in scheduling problems (in contrast to independent percolation, intended originally as a model for porous material). The main example we will talk about arose in joint work with Lizz Moseman (USMA). Lines on the positive quadrant of the plane grid are assigned uniformly random values from [0,1], and those vertices whose two coordinate values sum to more than some threshold t are killed. We are able to derive a simple closed-form expression for the probabity Theta(t) that there is an infinite open path (directed or not) from the origin, exhibiting a phase transition similar to what is believed to occur for independent percolation on the plane.

• October 21

  Sami Assaf (MIT)

  A rule of thumb for riffle shuffles

  Abstract: In this talk we study the Gilbert-Shannon-Reeds model for riffle shuffles and ask 'How many times must a deck of cards be shuffled for the deck to be in close to random order?'. In 1992, Bayer and Diaconis gave an elegant solution which gives exact and asymptotic results for all decks of practical interest, e.g. a deck of 52 cards. But what if one only cares about the colors of the cards or disregards the suits focusing solely on the ranks? More generally, how does the rate of convergence of a Markov chain change if we are interested in only certain features? Our exploration of this problem takes us for random walks on groups and their cosets, discovering along the way exact formulas leading to interesting combinatorics, an 'amazing matrix', and new analytic methods which produce a completely general asymptotic solution that is remarkable accurate. This is joint work with Persi Diaconis and K. Soundararajan.

• October 28

  Horng-Tzer Yau (Harvard)

  Local Wigner semicircle law and level repulsion for random matrices

  Abstract: We consider $N\times N$ Hermitian random matrices with independent identically distributed entries (Wigner matrices). The matrices are normalized so that the average spacing between consecutive eigenvalues is of order $1/N$. Under suitable assumptions on the distribution of the single matrix element, we first prove that, away from the spectral edges, the empirical density of eigenvalues concentrates around the Wigner semicircle law on energy scales $\eta \gg N^{-1}$. We then prove that the eigenvalues of a Wigner matrix repel each other, in agreement with the universality conjecture.

• November 4

  Todd Kemp (MIT)

  Chaos and the Fourth Moment

  Abstract: The $L^2$ space of a Brownian filtration has a natural orthogonal decomposition known as the Wiener chaos. For example, the first layer of the chaos consists of Gaussian random variables (and, in a sense, all higher layers are polynomials in these). No random variable in any higher chaos is normal. But that doesn't prevent a sequence of them from converging in distribution to a normal random variable.

  In several recent papers, Nualart et al. have shown the surprising result that a sequence of random variables $X_n$ in a fixed layer of the chaos converges to a Gaussian in distribution if and only if the fourth moments $E|X_n|^4$ converge to $3$. The proof uses Malliavin calculus.

  In this talk, I will discuss recent work with Roland Speicher, where we give a combinatorial proof of this theorem. We also prove the free probability version of the theorem: if $X_n$ are random variables in a fixed layer of the Wigner chaos (the orthogonal decomposition of a free Brownian filtration), they converge to a semi-circular random variable in distribution iff their fourth moments converge to $2$.

• November 14

  Friday, at 2pm in room 2-131

  Bálint Virág (U. Toronto)

  Random matrix eigenvalues and Gaussian analytic functions

  Abstract: There are two natural ways of producing repelling random point-clouds on the complex plane: either by taking the eigenvalues of some random matrix or by considering the zeros of a random (Gaussian) analytic function. I will explain some old and new connections between the two worlds.

• November 18

  Masha Gordina (University of Connecticut)

  Gaussian type measures on infinite-dimensional Heisenberg groups

  Abstract: The groups in question are modeled on an abstract Wiener space. Then a group Brownian motion is defined, and its properties are studied in connection with the geometry of this group. The main results include quasi-invariance of the Gaussian (heat kernel) measure, log Sobolev inequality (following a bound on the Ricci curvature), and the Taylor isomorphism to the corresponding Fock space. The latter map is a version of the Ito-Wiener expansion in the non-commutative setting. This is a joint work with B. Driver.

• November 25

  Adam Marcus (Yale)

  Entropy and Sumsets

  Abstract: The entropy function has a number of nice properties that make it a useful counting tool, especially when one wants to bound a set with respect to the set's projections. In this talk, I will show a method developed by Mokshay Madiman, Prasad Tetali, and myself that builds on the work of Gyarmati, Matolcsi and Ruzsa as well as the work of Ballister and Bollobas. The goal will be to give a black-box method for generating projection bounds and to show some applications by giving new bounds on the sizes of Abelian and non-Abelian sumsets.

• December 2

  Two 45-minute talks, 4:30-6

  Rick Kenyon (Brown)

  Random walks on branched covers of $Z^2$

  Abstract: There are a number of difficult problems in probability and statistical mechanics which can be reduced to understanding the Green's function on a branched cover of $Z^2$.

  ---

  David Wilson (Microsoft Research)

  A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks

  Abstract: In the complete graph on n vertices, when each edge has a weight which is an exponential random variable, Frieze proved that the minimum spanning tree has weight tending to zeta(3)=1/1^3+1/2^3+1/3^3+... as n goes to infinity. We consider spanning trees constrained to have depth bounded by k from a specified root. We prove that if k > log_2 log n+omega(1), where omega(1) is any function going to infinity with n, then the minimum bounded-depth spanning tree still has weight tending to zeta(3) as n -> infinity, and that if k < log_2 log n, then the weight is doubly-exponentially large in log_2 log n - k. It is NP-hard to find the minimum bounded-depth spanning tree, but when k < log_2 log n - omega(1), a simple greedy algorithm is asymptotically optimal, and when k > log_2 log n+omega(1), an algorithm which makes small changes to the minimum (unbounded depth) spanning tree is asymptotically optimal. We prove similar results for minimum bounded-depth Steiner trees, where the tree must connect a specified set of m vertices, and may or may not include other vertices. In particular, when m = const * n, if k > log_2 log n+omega(1), the minimum bounded-depth Steiner tree on the complete graph has asymptotically the same weight as the minimum Steiner tree, and if 1 <= k <= log_2 log n-omega(1), the weight tends to (1-2^{-k}) sqrt{8m/n} [sqrt{2mn}/2^k]^{1/(2^k-1)} in both expectation and probability. The same results hold for minimum bounded-diameter Steiner trees when the diameter bound is 2k; when the diameter bound is increased from 2k to 2k+1, the minimum Steiner tree weight is reduced by a factor of 2^{1/(2^k-1)}.

  Joint work with Omer Angel and Abie Flaxman.

• December 9

  Louigi Addario-Berry (University of Montreal)

  The Metric Scaling Limit of Critical Random Graphs

  Abstract: Let G_{n,1/n} be the critical Erdos-Renyi random graph, in which each edge is independently present with probability 1/n. The largest components of this graph have size of order n^{2/3}. Using a bijective correspondence between graphs and certain "marked random walks", we are able to show that the size-ordered sequence of components of G_{n,1/n} converges in distribution with respect to the Gromov-Hausdorff (GH) distance, a natural measure of similarity for metric spaces. The convergence is to a random sequence of metric spaces obtained from an "exponential tilting" of a Brownian motion, together with a Poisson point process. The GH distance measure is sufficiently strong that we are able to then read off a variety of functionals of the critical random graph process. In particular, letting D_n be the maximum diameter of any component of G_{n,1/n}, we show that D_n/n^{1/3} converges in distribution to a non-degenerate random variable D which is almost surely finite. This strengthens previous results of Addario-Berry, Broutin and Reed (2006) and of Nachmias and Peres (2007). Using a combinatorial approach, we also derive several more explicit results about the behavior of various functionals of the limit object.

  Joint work with Nicolas Broutin and Christina Goldschmidt.