April 24, 2014

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.