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.
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
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.
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$.
Friday, November 14 at 2pm in room 2-131 (**Note
change of day/time):
Random matrix eigenvalues and Gaussian analytic functions
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
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.
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.
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.
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)}.
The Metric Scaling Limit of Critical Random
Graphs
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.