Fall 2008
Tuesday 4:30  5:30 pm
Room 2143
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 closedform 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 GilbertShannonReeds 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
HorngTzer 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 $EX_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 semicircular random variable in distribution iff their fourth moments converge to $2$.

November 14
Friday, at 2pm in room 2131
Bálint Virág (U. Toronto)
Random matrix eigenvalues and Gaussian analytic functions
Abstract: There are two natural ways of producing repelling random pointclouds 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 infinitedimensional 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 quasiinvariance 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 ItoWiener expansion in the noncommutative 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 blackbox method for generating projection bounds and to show some applications by giving new bounds on the sizes of Abelian and nonAbelian sumsets.

December 2
Two 45minute talks, 4:306
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 boundeddepth and boundeddiameter 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 boundeddepth spanning tree still has weight tending to zeta(3) as n > infinity, and that if k < log_2 log n, then the weight is doublyexponentially large in log_2 log n  k. It is NPhard to find the minimum boundeddepth 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 boundeddepth 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 boundeddepth Steiner tree on the complete graph has asymptotically the same weight as the minimum Steiner tree, and if 1 <= k <= log_2 log nomega(1), the weight tends to (12^{k}) sqrt{8m/n} [sqrt{2mn}/2^k]^{1/(2^k1)} in both expectation and probability. The same results hold for minimum boundeddiameter 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^k1)}.
Joint work with Omer Angel and Abie Flaxman.

December 9
Louigi AddarioBerry (University of Montreal)
The Metric Scaling Limit of Critical Random Graphs
Abstract: Let G_{n,1/n} be the critical ErdosRenyi 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 sizeordered sequence of components of G_{n,1/n} converges in distribution with respect to the GromovHausdorff (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 nondegenerate random variable D which is almost surely finite. This strengthens previous results of AddarioBerry, 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.
Fall 2008 Organizers
 Lionel Levine
 Scott Sheffield
 Dan Stroock