One of the great classical conundra of twentieth-century mathematics is the Hausdorff-Banach-Tarski Paradox. This result states that one can take a unit ball in 3-dimensional Euclidean space, break it into 7 pieces, and reassemble those 7 pieces into two unit balls. See Figure 1.

Figure 1

Felix Hausdorff (1868-1942) originally proved this result--as stated here--for the ball. Stefan Banach (1892-1945) and Alfred Tarski (1902-1983), in a joint work in 1942, extended the result to more general domains.

The Hausdorff-Banach-Tarski Paradox is startling and remarkable. Some explanation of its context is in order. Henri Lebesgue (1875-1941) formulated in 1901 his theory of measure. This idea profoundly generalized the classical Riemann integral that we learn about in calculus. Lebesgue's notion of measure assigns a generalized "length" or measure to each set in the reals. But one thing that Lebesgue realized is that it is logically impossible to assign a measure to every set. Any attempt to do so leads to logical contradictions. Thus there are certain sets that are termed measurable--these are the sets that we may safely manipulate and use in the theory of the integral. And there are certain other sets that are non-measurable--these are the sets that are "forbidden", and can lead to trouble. The 7 sets constructed in the Hausdorff-Banach-Tarski Paradox are non-measurable, and that is why they behave so strangely.

We cannot provide here all the details of the Hausdorff-Banach-Tarski construction, but refer the interested reader to the book Set Theory by Thomas Jech. We make these remarks. First, the Hausdorff-Banach-Tarski construction is impossible in dimension 2. The reason is that the rotation group in 2 dimensions is too simple; in fact it is topologically and algebraically isomorphic to the circle. The rotation group in Euclidean dimension 3 is much more interesting. First of all, it is non-abelian (i.e., non-commutative). Second, it has two independent generators which generate a free group (i.e., a group with no relations).

John von Neumann (1903-1957) studied the Hausdorff-Banach-Tarski Paradox and isolated the importance of the group structure. He defined a concept of a measurable group, which is one for which the Hausdorff-Banach Tarski Paradox phenomenon fails. He showed that if the group has a free subgroup with two generators then it is not measurable. Today measurable groups are called amenable. Amenable and nonamenable groups were the subject matter of this workshop.

Finite groups and abelian groups are amenable--this is why the rotation group in dimension 2 is amenable. According to mathematician Mahlon Day, von Neumann conjectured that a group is amenable if and only if it does not contain a copy of the free group F₂ on two generators. In 1980, long after von Neumann's conjecture, Olshanskii constructed an example of a nonamenable group that does not contain a copy of F₂.

Amenability is important in part because of its roots, and in part because of its connections with so many other parts of mathematics. There are about twenty different equivalent definitions of the concept of "amenable". The theory of amenability is connected to graph theory, random walks, fixed-point theory, Hilbert spaces, and the theory of invariant means--to name just a few.

One of the really interesting connections, which we briefly describe here, is with graph theory. Let G be a group and S a generating set. A Cayley graph for G has one vertex for each element of G. Also two vertices g₁ and g₂ are connected by an edge if there is an element s ∈ S such that g₁ = s g₂. Figure 2 illustrates part of a Cayley graph. Let us call the graph G. We let E(G) denote the collection of edges of the graph and V(G) denote the collection of vertices of the graph. We note that a given group could have several different Cayley graphs, as the construction of the graph depends on the generating set.

Figure 2

Now let A be any subset of V(G). We define the boundary ∂ A of A to be the collection of those edges which have just one endpoint in A. The isoperimetric number i(G) is then defined to be

i(G) = inf_S |∂ A|/|A| . (*)

We use here the custom of letting |X| denote the number of elements in the finite set X. Also the infimum is taken over all finite subsets A of V(G).

It is useful to note here the ontology of the word "isoperimetric". In classical geometry there was interest in determining the planar region of given perimeter and greatest area. Jakob Steiner (1796-1863) showed that if a solution exists then it must be a disc. Later mathematicians disposed of the question of a solution existing; there are now dozens of proofs of the so-called isoperimetric inequality. In any event, it makes sense that one would be interested in considering the ratio

length(∂ U)/area(U)

for planar regions U. This is why we call (*) the isoperimetric number for the graph.

We call a Cayley graph for a group G amenable if its isoperimetric number i(G) equals 0. It can be shown that the original group is amenable if and only if all the Cayley graphs of G are amenable.

Infinite graphs are frequently used to model various problems of interest in statistical physics and applications. Given a graph G, and a probability p with 0 < p < 1, let us suppose that each edge of the graph is either "open" (i.e., permits passage) with probability p or "closed" (i.e., denies passage) with probability 1-p. We may examine the collection of all open edges and ask how many connected components this set has. In particular, one may consider whether there is an infinite connected component. If the answer to this last question is "yes" with probability 1, then we say that percolation occurs. The idea of percolation can be used to study the spread of disease, or of forest fires. It turns out that amenability of a graph can be formulated in terms of percolation properties of the graph.

The AIM workshop on amenability/nonamenability explored a number of exciting directions in group theory, graph theory, and functional analysis. Workers from many different subject areas interacted to establish new research directions and begin new collaborations.