Percolation theory was developed to find a mathematical language for dealing with disordered media. [Put in other language, percolation deals with fluid flow (or a similar process) in random media.] Here "disorder" is defined by a random variation in the degree of connectivity. Certainly one of the primary examples of percolation is water flowing through a porous medium. One of the big ideas in this subject is the concept of percolation threshhold, which may be thought of in the following way.

Let p be a parameter which defines the average degree of connectivity between various sub-units of some arbitrary system (we often think of p as a probability). When p = 0, all sub-units are completely isolated from each other. When p = 1, all sub-units are connected to some maximum number of neighboring sub-units. In this latter situation, the system is connected from one side to the other, since there are paths that traverse the system, from one side to the other, linking one sub-unit to the next along the spanning cluster. If we begin to randomly break connections, then p decreases (because p measures the average connectivity). The percolation threshhold is the value of p, usually denoted by p_c, at which there is no longer an unbroken path from one side of the system to the other.

It is often easier to examine infinite networks rather than just very large ones. In this case the right question is: Does an infinite open cluster exist? Here a cluster is a contiguous collection of nodes that may be reached one-to-the-other. So we want to know whether there is a path of connected points of infinite length through the network. Kolmogorov's zero-one law tells us that, for any given p, the probability that an infinite cluser exists is either zero or one.

Percolation has been studied for a long time by physicists, who want to understand the physical phenomena that inspire the mathematical theory. In the past 20 years mathematicians have become interested in the subject area. Oded Schramm, Greg Lawler, Wendolin Werner, Harry Kesten, and many others (including several participants in the AIM workshop) have made important contributions to the subject.

One critical question in the subject is whether infinite clusters exist. As p varies, how does this affect the existence of infinite clusters? In physical problems, conformal mappings are important because they infinitesimally preserve angles and stretch equally in all directions (they can be used, for example, to model incompressible fluid flow). It is natural to ask whether percolation is preserved under conformal mapping. This is still an open problem.

This AIM workshop concentrated on percolation on transitive graphs, particularly Cayley graphs. A Cayley graph is a graph generated by a finitely presented group, with each group element and its inverse corresponding to an edge of the graph. Figure 1 exhibits the beginnings of a graph generated by the group Z² in the plane. Note that the group element (1,0) corresponds to motion one unit to the right, the group element (0,1) corresponds to motion one unit up, and so forth.

Figure 1: A Cayley graph.

Percolation on a Cayley graph can be studied using techniques of probability theory, geometric group theory, and algebra. It is a rich and diverse subject with many surprising twists and turns. The AIM workshop brought together experts from all over the world, from many different subject areas, to exchange ideas, to find some common language, and to develop new approaches to the subject. The problems here have considerable mathematical interest, but their applications are important too. Connections to the theory of random walks offer potential connections to many different parts of physics, engineering, and applied science.