Program in Probability and Its Applications
Fall Kolmogorov Lecture Series
Harry Kesten (Cornell University)
Percolation of arbitrary words in {0,1}N
Friday, September 18, 1998
Let G be a (possibly directed) locally finite graph with
countably infinite vertex set V. Assign to each vertex a 0 or a 1,
with probability p or 1-p, respectively, and take all vertices
independent of one another. We want to know which sequences of zeroes and
ones occur (with positive probability) along some selfavoiding path on G.
The traditional problem in (site) percolation is whether the sequence (1,1,1,…)
occurs on some path starting at a fixed vertex v 0. So -
called AB-percolation occurs if the sequence (1,0,1,0,1,0,…) occurs
with positive probability on some path starting at v0. We
concentrate here on the questions (a): whether (with positive probability)
all words are seen from v0 and (b): whether all words are
seen somewhere on G with probability 1. We also consider similar questions
with "all words" replaced by "almost all words".
Béla Bollobás (University of Memphis and
Cambridge University)
Colourings and Hereditary Properties of Graphs
Tuesday, October 13, 1998
A property P of graphs is hereditary if it is
invariant under vertex deletions. A hereditary property that is invariant
under edge deletions is said to be monotone. Much of classical graph
theory is concerned with the maximal number of edges of a graph with n
vertices having a specified monotone property. For well over a decade, much
attention has been paid to general hereditary properties: their asymptotic
enumeration, their global structure, the `largest' graphs with the property,
and colouring random graphs with the property. Somewhat surprisingly, the
asymptotic density of general hereditary properties exhibits a certain phase
transition, and the P-chromatic number of a random graph Gn,p
is highly concentrated for every fixed p and every hereditary property
P
In the talk we shall review a number of beautiful results of
Kleitman, Rothschild, Erdös, Frankl, Rödl, Scheinerman, Prömel, Steger, and
others, and we shall present the latest developments, most of which were obtained
jointly with Andrew Thomason. One of our tools is an extension of the classical
Loomis-Whitney isoperimetric inequality.
Charles Newman (Courant Institute for
Mathematical Sciences, NYU)
Stochastic Dynamics at Zero Temperature
Tuesday, November 17, 1998
At zero temperature, the natural Markov process of Ising spin
configurations on Zd (or other lattices) is that each spin
flips with rate 1 or 0 or 1/2 according to whether the flip would lower the
energy or raise it or leave it unchanged. What happens as time t tends
to infinity when the initial state is chosen by independent tosses of a fair
coin? Do spins flip finitely or infinitely many times? Does the state after
a large time depend more on the initial state or on the realization of the
dynamics ("nature vs. nurture")? Do the answers to such questions depend on
the dimension, on the lattice, on whether the Ising model is disordered?
Geoffrey Grimmitt (University of Cambridge)
An Epidemic with Removal
Tuesday, December 8, 1998
The contact process is an interesting model for the spread of
disease through space. Susceptibles are placed at the vertices of a lattice,
and infection is introduced at the origin. The process has a rich theory,
which is greatly facilitated by the fact that it is stochastically monotone
in the rate of infection. Minor variants of the contact model lack this property.
A simple such extension is obtained by allowing "removal periods"' before
a cured individual becomes available for reinfection. Such systems are much
more challenging.
We discuss the phase diagram of such a model, together with
some applications of techniques first developed for percolation. There are
open problems, such as to prove the uniqueness of the phase transition. The
analysis includes an "essential" application of Reimer's inequality.
