Bulletin T.CXXVII de l’Académie Serbe des Sciences et des Arts - 2003 Classe des Sciences mathématiques et naturelles Sciences mathématiques, N\underline{o} 28

UNIVERSAL MINIMAL FLOWS OF AUTOMORPHISM GROUPS

A. S. KECHRIS^{1}, V. PESTOV^{2}, S. TODORČEVIĆ^{3}

(Presented at the 3rd Meeting, held on May 9, 2003)

A b s t r a c t. We investigate some connections between the Fraïssé theory of amalgamation classes and ultrahomogeneous structures, Ramsey theory, and topological dynamics of automorphism groups of countable structures. We show, in particular, that results from the structural Ramsey theory can be quite useful in recognizing the universal minimal flows of this kind of groups. As result we compute universal minimal flows of several well known topological groups such as, for example, the automorphism group of the random graph, the automorphism group of the random triangle-free graph, the automorphism group of the ∞-dimensional vector space over a finite field, the automorphism group of the countable atomless Boolean algebra,etc. So we have here a reversal in the traditional relationship between topological dynamics and Ramsey theory, the Ramsey-theoretic results are used in proving theorems of topological dynamics rather than vice versa.

AMS Mathematics Subject Classification (2000): 05D10, 05C55, 22A10, 22A05, 22F05, 37B05, 37F20, 54H20.

Key Words: group actions, universal minimal flows, Fraïssé theory, structural Ramsey theory.

1partially supported by NSF Grant DMS-9987437, the Fields Institute, Toronto, and a Guggenheim Fellowship

2partially supported by the Marsden Fund of the Royal Society of New Zeeland, and the NSERC of Canada

3partially supported by CNRS, Paris and the Fields Institute, Toronto

0. Introduction

A prime concern of topological dynamics in the study of continuous actions of topological groups G on compact spaces X. These are usually referred to as (compact) G-flows. Of particular interest is the study of minimal G-flows, those for which every orbit is dense. Every G-flow contains a minimal subflow. A general result of topological dynamics asserts that every topological group G has a universal minimal flow M(G), a minimal Gflow which can be homomorphically mapped onto any other minimal G-flow. Moreover, this is uniquely determined, by this property, up to isomorphism. (As usual a homomorphism π : X → Y between G-flows is a continuous G-map and an isomorphism is a bijective homomorphism.) For separable, metrizable groups G, which are the ones that we are interested in here, the universal minimal flow of G is an inverse limit of manageable, i.e., metrizable G-flows, but itself may be very complicated, for example non-metrizable. In fact, for the “simplest” G, i.e., the countable discrete ones, M(G) is a very complicated compact G-invariant subset of the space βG of ultrafilters on G and is always non-metrizable.

Rather remarkably, it turned out that there are topological groups G for which M(G) is actually trivial, i.e., a singleton. This is equivalent to saying that G has a very strong fixed point property, namely every G-flow has a fixed point (i.e., a point x such that g · x = x, ∀g ∈ G). (For separable, metrizable groups this is also equivalent to the fixed point property restricted to metrizable G-flows.) Such groups are said to have the fixed point on compacta property or be extremely amenable. The latter name comes from one of the standard characterizations of second countable locally compact amenable groups. A second countable locally compact group G is amenable iff every metrizable G-flow has an invariant (Borel probability) measure. However, no locally compact group can be extremely amenable, because, by a theorem of Veech [77], every such group admits a free G-flow (i.e., a flow for which g · x = x ⇒ g = 1_{G}). This probably explains the rather late emergence of extreme amenability. In retrospect, the first examples of extremely amenable groups were constructed by Herer-Christensen [75]. They found Polish abelian so-called pathological groups, i.e., topological groups with no non-trivial unitary representations. Remarkably though it turned out that a lot of important (non-locally compact) Polish groups are indeed extremely amenable. Gromov-Milman [83] showed that the unitary group of infinite dimensional separable Hilbert space is extremely amenable, Furstenberg-Weiss and Glasner [98] showed that the group of measurable maps from I = [0, 1] to the unit circle 𝕋 is extremely amenable, Pestov [98] showed that the groups H_{+}(I), H_{+}(ℝ) of orientation preserving homeomorphisms of I, ℝ, resp., are extremely amenable, and Pestov [98a] showed that the group Aut(⟨ℚ, <⟩) of automorphisms of the rationals is extremely amenable. More recently, Pestov [02] proved that the universal Polish group Iso(U), of all isometries of the Urysohn space U is extremely amenable, and Giordano-Pestov [02] showed that the groups Aut(I, λ) (resp., Aut^{∗}(I, λ)) of measure preserving automorphisms of I with Lebesgue measure λ (resp., measure-class preserving automorphisms of I, λ) is extremely amenable.

Beyond the extremely amenable groups there were very few cases of metrizable universal minimal flows that had been computed. The first such example is in Pestov [98a], where the author shows that the universal minimal flow of H_{+}(𝕋), the group of orientation preserving homeomorphisms of the circle, has as a universal minimal flow its natural (evaluation) action on 𝕋. Then Glasner-Weiss [02] showed that the universal minimal flow of S_{∞}, the infinite symmetric group of all permutations of ℕ, is its canonical action on the space of all linear orderings on ℕ. Finally, we have recently received a preprint of Glasner-Weiss [03], that shows that the universal minimal flow of H(2^{ℕ}), the group of homeomorphisms of the Cantor space, is its canonical action on the space of maximal chains of compact subsets of 2^{ℕ}, a space introduced in Uspenskij [00].

Motivated by these results we develop a general framework, in which such results can be viewed as special instances. In particular, this gives many new examples of automorphism groups that are extremely amenable and calculations of universal minimal flows. There are two main ingredients that come into play here. The first is the Fraïssé theory of amalgamation classes and ultrahomogeneous structures, and the second is the structural Ramsey theory that arises in the works of Graham, Leeb, Rothchild, Nešetřil and Rödl, and others. Once things are put in the proper context, extreme amenability of automorphism groups and calculation of universal minimal flows turn out to have equivalent formulations in terms of concepts that have arisen in structural Ramsey theory.

1. Topological Dynamics

In this section we survey some basic definitions and facts needed for stating our main results. Recall that an action (g, x) ∈ G × X ↦ g · x ∈ X of a topological group G on a topological space X is continuous if it is continuous as a map from G × X into X. We will consider continuous actions of Hausdorff topological groups G on (non-∅) compact, Hausdorff spaces X. Actually we are primarily interested in metrizable topological groups G and in fact only separable metrizable one, although we will state in this survey several standard results for general topological groups.

Let G be a topological group and X a compact, Hausdorff space. If we equip H(X), the group of homeomorphisms of X, with the compact-open topology, i.e., the topology with subbasis {f ∈ H(X) : f(K) ⊆ V }, with K ⊆ X compact, V ⊆ X open, then H(X) is a topological group, and a continuous action of G on X is simply a continuous homomorphism of G into H(X). We will also refer to a continuous action of G on X as a G-flow on X. If the action is understood, we will often simply use X to refer to the flow. Given a G-flow on X and a point x ∈ X, the orbit of x is the set

G · x = {g · x : g ∈ G}

and the orbit closure of x, the set

\overline{G · x}.

This is a G-invariant, compact subset of X. In general, a (non-∅) compact, G-invariant subset Y ⊆ X defines a subflow by restricting the G-action to Y. A G-flow on X is minimal if it contains no proper subflows, i.e., there is no (non-∅) compact G-invariant set other than X. Thus X is minimal iff every orbit is dense. A simple application of Zorn’s Lemma shows that every G-flow X contains a minimal subflow Y ⊆ X. Among minimal flows of a given group G, there is a largest (universal) one, called the universal minimal flow. To define this, we first need the concept of homomorphism of G-flows. Let X, Y be two G-flows. A homomorphism of the G-flow X to the G-flow Y is a continuous map π : X → Y, which is also a G-map, i.e.,

π(g · x) = g · π(x), x ∈ X, g ∈ G.

Notice that if Y is minimal, then any homomorphism of X into Y is surjective. An isomorphism of X to Y is a bijective homomorphism π : X → Y (notice then that π^{−1} is also a homomorphism). We now have the following basic fact in topological dynamics. (For a proof see Auslander [88, Ch. 8], or Uspenskij [02, §3].)

Theorem 1.1 Given a topological group G, there is a minimal G-flow M(G) with the following property: For any minimal G-flow X there is a homomorphism π : M(G) → X. Moreover, M(G) is uniquely determined up to isomorphism by this property.

The space M(G) is called the universal minimal flow of G. The space M(G) can be extremely complicated, e.g., non-metrizable, even when the group G is very “small”, e.g., a countable discrete G. For example, we will show that M(G) is not metrizable whenever G is a locally compact noncompact group. In particular, and this is a well known result of Veech [77], when G is locally compact, then G acts freely on some compact space and thus on M(G). This implies that when G is second countable, then G admits a free metrizable G-flow. (See Adams-Stuck[93] for an alternate proof of this case.) Rather remarkably, there are groups G for which M(G) trivializes, i.e., consists of a single point. Such groups are called extremely amenable. Thus a topological group is extremely amenable if any G-flow X has a fixed point, i.e., there is x ∈ X with g · x = x, ∀g ∈ G. (For this reason, sometimes extremely amenable groups are described as groups having the fixed point on compacta property; see Pestov [02a] and Uspenskij [02].) By Veech’s Theorem such groups cannot be locally compact. As mentioned earlier, it turned out, a number of important, non-locally compact Polish groups are extremely amenable such as for example the unitary group U(H) of the infinite dimensional separable Hilbert space H and the group of measurable maps from I = [0, 1] to 𝕋, with pointwise multiplication, and the topology of convergence in measure. Except for the case of extremely amenable groups, there were very few cases where the universal minimal flow M(G) was computed and shown to be metrizable.

2. Fraïssé theory

We will review here some basic ideas of model theory concerning the Fraïssé construction and ultrahomogeneous countable structures (see, Fraïssé [54]) Our main reference here is Hodges [93, Ch. 7]. See also Cherlin [98] and Cameron [90].

A countable signature consists of a set of symbols L = {R_{i}}_{i∈I} ∪ {f_{j}}_{j∈J} (I, J countable), to each of which there is an associated arity

n(i) ∈ {1, 2, …} (i ∈ I) and m(j) ∈ ℕ (j ∈ J).

We call R_{i} the relation symbols and f_{j} the function symbols of L. A structure for L is of the form A = ⟨A, {R_{i}^{A}}_{i∈I}, {f_{j}^{A}}_{j∈J}⟩, where A ≠ ∅, R_{i}^{A} ⊆ A^{n(i)}, f_{j}^{A} : A^{m(j)} → A. The set A is called the universe of the structure. An embedding between structures A, B for L is an injection π : A → B such that R_{i}^{A}(a_{1}, …, a_{n(i)}) ⇔ R_{i}^{B}(π(a_{1}), …, π(a_{n(i)})) and π(f_{j}^{A}(a_{1}, …, a_{m(j)})) = f_{j}^{B}(π(a_{1}), …, π(a_{m(j)})). If π is the identity, we say that A is a substructure of B. An isomorphism is an onto embedding. We write A ≤ B if A can be embedded in B and A ≅ B if A is isomorphic to B. A class K of finite structures for L is hereditary if A ≤ B ∈ K implies A ∈ K. It satisfies the joint embedding property if for any A, B ∈ K there is C ∈ K with A ≤ C, A ≤ C. Finally, it satisfies the amalgamation property if for any embeddings f : A → B, g : A → C, with A, B, C ∈ K, there is D ∈ K and embeddings r : B → D and s : C → D, such that r ∘ f = s ∘ g. We call K a Fraïssé class if it is hereditary, satisfies joint embedding and amalgamation, and contains structures of arbitrarily large (finite) cardinality. If now A is a countable structure, which is locally finite (i.e., finitely generated substructures are finite), its age, Age(A), is the class of all finite structures which can be embedded in A. We call A ultrahomogeneous if every isomorphism between finite substructures of A can be extended to an automorphism of A. We call a locally finite, countably infinite, ultrahomogeneous structure a Fraïssé structure.

There is a canonical 1-1 correspondence between Fraïssé classes and structures, discovered by Fraïssé. If A is a Fraïssé structure, then Age(A) is a Fraïssé class. Conversely, if K is a Fraïssé class, then there is a unique Fraïssé structure, the Fraïssé limit of K, denoted by Flim(K), whose age is exactly K. Here are a couple of examples: the Fraïssé limit of the class of finite linear orderings is ⟨ℚ, <⟩, and the Fraïssé limit of the class of finite graphs is the random graph.

3. Ramsey Theory and Extreme Amenability

Let K be a hereditary class of finite structures in a signature L. For A ∈ K, B ∈ K with A ≤ B, we denote by ( B ) A the set of all substructures of B isomorphic to A. If A ≤ B ≤ C are in K and n = 2, 3, …, we write

C → (B)_{n}^{A},

if for every coloring c : ( C ) A → {1, …, n}, there is B′ ∈ ( C ) B which is homogeneous, i.e., ( B )′ A is monochromatic. We say that K satisfies the Ramsey property if for every A ≤ B in K and n ≥ 2, there is C ∈ K with B ≤ C such that C → (B)_{n}^{A}. For example, the classical finite Ramsey theorem is equivalent to the statement that the class of finite linear orderings has the Ramsey property. Also Nešetřil and Rödl [77] and [83] showed that the class of finite ordered graphs has the Ramsey property, and Graham-Leeb-Rothchild [72] showed that the class of finite-dimensional vector spaces over a finite field has the Ramsey property.

Consider now automorphism groups Aut(A) of countably infinite structures A, for which we may as well assume that A = ℕ. Thus, with the pointwise convergence topology, Aut(A) is a closed subgroup of S_{∞}, the infinite symmetric group. Conversely, given a closed subgroup G ≤ S_{∞}, G is the automorphism group of some structure on A = ℕ (in some signature). Given a closed subgroup G ≤ S_{∞} and F ⊆ ℕ a finite set, we call the G-orbit G · F = {g · F : g ∈ G}, where g · F = {g(i) : i ∈ F }, the G-type of F. A G-type σ is the G-type of some finite set. If ρ, σ are G-types we write

ρ ≤ σ ⇔ ∃F′ ∈ ρ∃F ∈ σ(F′ ⊆ F).

If ρ ≤ σ, F ∈ σ, put

( F ) ρ = {F′ ⊆ F : F′ ∈ ρ}.

Finally, if ρ ≤ σ ≤ τ are G-types, we put

τ → (σ)_{n}^{ρ},

for n = 2, 3, …, if for every F ∈ τ and coloring c : ( F ) ρ → {1, …, n}, there is F_{0} ∈ ( F ) σ which is homogeneous, i.e., ( F )_{0} ρ is monochromatic. If for every n = 2, 3, …, and G-types ρ ≤ σ, there is a G-type τ with σ ≤ τ and τ → (σ)_{n}^{ρ}, we say that G has the Ramsey property. We also say that G ≤ S_{∞} preserves an ordering if there is a linear ordering on ℕ, ≺, such that for all g ∈ G,

m ≺ n ⇔ g(m) ≺ g(n).

We now have

Theorem 1. Let G ≤ S_{∞} be a closed subgroup. Then the following are equivalent: (i) G is extremely amenable. (ii) (a) G preserves a linear ordering and (b) G has the Ramsey property.

Assume now that L is a signature containing a distinguished binary relation symbol <. An order structure A for L is a structure A for which <^{A} is a linear ordering. An order class K for L is one for which all A ∈ K are order structures. Using Theorem 1 we now obtain

Theorem 2. The extremely amenable closed subgroups of S_{∞} are exactly the groups of the form Aut(F), where F is the Fraïssé limit of a Fraïssé order class with the Ramsey property.

We can now use this, and known results of structural Ramsey theory, to find many new examples of extremely amenable automorphism groups. Notice that, by the preceding result, the extreme amenability of these groups is in fact equivalent to the corresponding Ramsey theorem. Consider the class of finite ordered graphs. Its Fraïssé limit is the random graph with an appropriate linear ordering. We call it the random ordered graph. Let K_{n} be the complete graph with n elements, n = 3, 4, . . .. Consider the class of K_{n}-free finite ordered graphs, whose Fraïssé limit we call the random K_{n}- free ordered graph. Next consider the class of finite ordered graphs which are equivalence relations (i.e., it can be written as a disjoint union of K_{n}’s). Its Fraïssé limit is the rationals with the usual order and an equivalence relation with infinitely many classes, which are all dense in ℚ. Finally consider the class of finite linear orderings. Its Fraïssé limit is ⟨ℚ, <⟩. All of the above classes satisfy the Ramsey property. This is due to Nešetřil-Rödl [77],[83] (see also Nešetřil [89] and [95]) for the graph cases, and it is of course the classical Finite Ramsey Theorem for the last case. So all the corresponding automorphism groups of their Fraïssé limits are extremely amenable. This can be generalized to hypergraphs. Let L_{0} = {R_{i}}_{i∈I} be a finite relational signature. A hypergraph of type L_{0} is a structure A_{0} = ⟨A_{0}, {R_{i}^{A_{0}}}_{i∈I}⟩ in which (a_{1}, … a_{n(i)}) ∈ R_{i}^{A} ⇒ a_{1}, …, a_{n(i)} are distinct, and R_{i}^{A_{0}} is closed under permutations. Thus, essentially, R_{i}^{A_{0}} ⊆ [A_{0}]^{n(i)} = the set of subsets of A_{0} of cardinality n(i). Consider the class of all finite ordered hypergraphs of type L_{0}, whose Fraïssé limit we call the random ordered hypergraph of type L_{0}. More generally, for every class A of finite irreducible hypergraphs of type L_{0} (where A_{0} is irreducible if it has at least two elements and for every x ≠ y in A_{0} there is i ∈ I with {x, y} ⊆ R_{i}^{A_{0}}), let F≀∇⌊(A) be the class of all finite ordered hypergraphs of type L_{0} which omit A (i.e., no element of A can be embedded in them). We call the Fraïssé limit of F≀∇⌊(A) the random A-free ordered hypergraph of type L_{0}. Again Nešetřil-Rödl [77], [83] showed that these classes have the Ramsey property, so the corresponding automorphism groups are extremely amenable.

There are similar results for metric spaces. Consider the class of finite ordered metric spaces. Its Fraïssé limit is the so-called rational Urysohn space with an appropriate ordering. We call it the ordered rational Urysohn space. In response to an inquiry by the authors, Nešetřil [03] verified that the class of finite ordered metric spaces has the Ramsey property. Thus the automorphism group of the ordered rational Urysohn space is extremely amenable. We also show how this result can be used to give a new proof of the result of Pestov [02] that the isometry group of the Urysohn space is extremely amenable.

We next consider some other kinds of examples. We first look at the class of all finite convexly ordered equivalence relations, where convexly ordered means that each equivalence class is convex (whenever two elements are in it every element between them is also in it). Their Fraïssé limit is the rationals with the usual ordering and an equivalence relation whose classes are convex, order isomorphic to the rationals, and moreover the set of classes itself is ordered like the rationals. We show that the automorphism group of this structure is extremely amenable. This implies that the corresponding class has the Ramsey property, a fact that can also be proved directly. Next we consider finite-dimensional vector spaces over a fixed finite field F. A natural ordering on such a vector space is one induced antilexicographically by an ordering of a basis. These were considered in Thomas [86], who showed that the class of naturally ordered finite-dimensional spaces over F form a Fraïssé class. We call its limit the ℵ_{0}-dimensional vector space over F with the canonical ordering. The Ramsey property for the class of naturally ordered finite-dimensional vector spaces over F is easily seen to be equivalent to the Ramsey property for the class of finite-dimensional vector spaces over F, which was established in Graham-Leeb-Rothchild [72]. So the corresponding automorphism group of the Fraïssé limit is extremely amenable. Finally, we consider the class of naturally ordered finite Boolean algebras, where a natural ordering on a finite Boolean algebra is one antilexicographically induced by an ordering of its atoms. By analogy with Thomas’ result, we show that this is also a Fraïssé class, and we call its limit the countable atomless Boolean algebra with the canonical ordering. The Ramsey property for the class of naturally ordered finite Boolean algebras is again easily seen to be equivalent to the Ramsey property for the class of finite Boolean algebras and this is trivially equivalent to the Dual Ramsey Theorem of Graham-Rothchild [71]. Thus the corresponding automorphism group is extremely amenable. We summarize

Theorem 3. The automorphism groups of the following structures are extremely amenable:

(i) The random ordered graph.

(ii) The random K_{n}-free ordered graph, n = 3, 4, …

(iii) The rationals with the usual ordering and an equivalence relation with infinitely many classes, all of which are dense.

(iv) The rationals with the usual ordering.

(v) The random ordered hypergraph of type L_{0} and more generally the random A-free ordered hypergraph of type L_{0}, for any class A of irreducible finite hypergraphs of type L_{0}.

(vi) The ordered rational Urysohn space.

(vii) The rationals with the usual ordering and an equivalence relation whose classes are convex, ordered like the rationals, and moreover the set of classes itself is ordered like the rationals.

(viii) The ℵ_{0}-dimensional vector space over a finite field with the canonical ordering.

(ix) The countable atomless Boolean algebra with the canonical ordering.

As mentioned earlier the result (iv) already appears in Pestov [98a].

4. Representing Universal Minimal Flows

We now use the results of previous sections, and some additional considerations, to compute universal minimal flows. In (E) we have seen a host of examples of Fraïssé order classes K in a signature L ⊇ {<}. Let L_{0} = L \ {L}, the signature without the distinguished symbol for the ordering. For any structure A for L, we denote by A_{0} = A|L_{0} its reduct to L_{0}, i.e., A_{0} is the structure A with <^{A} dropped. Denote also by K_{0} = K|L the class of all reducts A_{0} = A|L_{0} for A ∈ K. When K satisfies a mild (and easily verified in every case we are interested in) condition, in which case we call K reasonable (see 5.1 below for the precise definition), then K_{0} is a Fraïssé class, whose limit is the reduct of the Fraïssé limit of K. Put F_{0} = Flim(K_{0}), F = Flim(K), so that F_{0} = F|L_{0}, i.e., F = ⟨F_{0}, <^{F}⟩. In particular, F_{0} = F. Put <^{F}=<_{0}. It is natural now to look at the action of Aut(F_{0}) on the space of all linear orderings on F_{0}. Denote then by X_{K} the orbit closure \overline{G· <_{0}} of <_{0} in this action. It is easy to see that X_{K} is the space of all linear orderings ≺ on F_{0} which have the property that for any finite substructure B_{0} of F_{0}, B = ⟨B_{0}, ≺ |B_{0}⟩ ∈ K. We call these K-admissible orderings. This is clearly a compact Aut(F_{0})-invariant subset of 2^{F_{0}×F_{0}} in the natural action of Aut(F_{0}) on 2^{F_{0}×F_{0}}, so X_{K} is an Aut(F_{0})- flow. If K has the Ramsey property, it turns out that it is the universal minimal flow of Aut(F_{0}) precisely when K additionally satisfies a natural property called the ordering property, which plays also an important role in structural Ramsey theory (see Nešetřil-Rödl [78] and Nešetřil [95]). We say that K satisfies the ordering property if for every A_{0} ∈ K_{0}, there is B_{0} ∈ K_{0} such that for every linear ordering ≺ on A_{0} and every linear ordering ≺′ on B_{0}, if A = ⟨A_{0}, ≺⟩ ∈ K and B = ⟨B_{0}, ≺′⟩ ∈ K, then A ≤ B. Then we have

Theorem 4. Let L ⊇ {<} be a signature, L_{0} = L \ {<}, K a reasonable Fraïssé order class in L, K_{0} = K|L_{0}, F = Flim(K), F_{0} = Flim(K_{0}) = F|L_{0}. Put G_{0} = Aut(F_{0}). Let X_{K} be the G_{0}-flow of K-admissible orderings on F_{0} (= F). Then the following are equivalent:

(i) X_{K} is a minimal G_{0}-flow,

(ii) K satisfies the ordering property, and when K satisfies the Ramsey property, these are also equivalent to:

(iii) X_{K} is the universal minimal G_{0}-flow.

Now all the classes K, considered in (E) above, except for the class of finite ordered equivalence relations, satisfy the ordering property. This is due to Nešetřil-Rödl [78] for the case of graphs and hypergraphs, Nešetřil [03] for metric spaces, and is easily verified in all the other cases. Therefore, we have the following computations of universal minimal flows:

Theorem 5. (i) Consider the automorphism groups of the following structures:

(a) The random graph.

(b) The random K_{n}-free graph, n = 2, 3, …

(c) S_{∞}

(d) The automorphism group of the random hypergraph of type L_{0}.

(e) The automorphism group of the random A-free hypergraph of type L_{0}, where A is a class of irreducible finite hypergraphs of type L_{0}.

(f) The rational Urysohn space.

Then their actions on the space of linear orderings on the universe of each structure is the universal minimal flow.

(ii) The universal minimal flow of the automorphism group of the equivalence relation on a countable set with infinitely many classes, each of which is infinite, is its action on the space of all linear orderings on that set for which each equivalence class is convex.

(iii) The universal minimal flow of the automorphism group GL(V_{F}) of the ℵ_{0}-dimensional vector space V_{F} over a finite field F, is its action on the space of all orderings on V_{F}, whose restrictions to finite-dimensional subspaces are natural.

(iv) The universal minimal flow of the automorphism group of the countable atomless Boolean algebra B_{∞}, is its action on the space of all linear orderings on B_{∞}, whose restrictions to finite subalgebras are natural.

In particular, in all these cases, the universal minimal flow is metrizable. Of course (i), (c) is the result of Glasner-Weiss [02]. Pestov and Uspenskij asked whether the group in (iii) has metrizable universal minimal flow. Finally, very recently, Glasner-Weiss [03] computed the universal minimal flow of H(2^{ℕ}), the homeomorphism group of the Cantor space 2^{ℕ}, as the space of maximal chains of compact subsets of 2^{ℕ}, which is metrizable. Since the group in (iv) above is, by Stone duality (see Halmos [63]), isomorphic to H(2^{ℕ}), we have another proof that the universal minimal flow is metrizable and a different description of this flow. Of course these two flows are isomorphic and in fact an explicit isomorphism can be found.

REFERENCES

[1] J. A u s l a n d e r [88], Minimal Flows and Their Extensions, North Holland, 1988.

[2] S.K. B e r b e r i a n [74], Lectures in Functional Analysis and Operator Theory, Springer-Verlag, 1974.

[3] P.J. C a m e r o n [90], Oligomorphic Permutation Groups, London Math. Society Lecture Note Series, 152, 1990.

[4] G.L. C h e r l i n [98], The Classification of Countable Homogeneous Directed Graphs and Countable Homogeneous n-tournaments, Memoirs of the Amer. Math. Soc., 131, No. 621, 1998.

[5] C. C o n s t a n t i n e s c u [01], C^{∗}-algebras, Vol. 2: Banach Algebras and Compact Operators, North Holland, 2001.

[6] J. d e V r i e s [93], Elements of Topological Dynamics, Kluwer, 1993.

[7] R. E l l i s [60], Universal minimal sets, Proc. Amer. Math. Soc. 11, 540–543, 1960.

[8] R. E l l i s [69], Lectures on Topological Dynamics, W.A. Benjamin, 1969.

[9] R. F r a ï s s é [54], Sur l’extension aux relations de quelques proprietés des ordres, Ann. Sci. École Norm. Sup. 71, 363-388, 1954.

[10] T. G i o r d a n o and V. P e s t o v [02], Some extremely amenable groups, C.R. Math. Acad. Sci. Paris 334 (4), 273–278, 2002.

[11] E. G l a s n e r [98], On minimal actions of Polish groups, Top. Appl. 85, 119–125, 1998.

[12] E. G l a s n e r and B. W e i s s [02], Minimal actions of the group S(ℤ) of permutations of the integers, Geom. and Funct. Anal. 12, 964–988, 2002.

[13] E. G l a s n e r and B. W e i s s [03], The universal minimal system for the group of homeomorphisms of the Cantor set, preprint, 2003.

[14] R.L. G r a h a m, K. L e e b, and B.L. R o t h c h i l d [72], Ramsey’s theorem for a class of categories, Adv. in Math, 8, 417–433, 1972.

[15] R.L. G r a h a m and B.L. R o t h c h i l d [71], Ramsey’s theorem for n-parameter sets, Trans. Amer. Math. Soc. 159, 257–292, 1971.

[16] R.L. G r a h a m, B.L. R o t h c h i l d, and J.H. S p e n c e r [90], Ramsey Theory, 2nd Edition, Wiley, 1990.

[17] M. G r o m o v and V.D. M i l m a n [83], A topological application of the isoperimetric inequality, Amer. J. Math. 105, 843–854, 1983.

[18] P. H a l m o s [63], Lectures on Boolean Algebras, Van Nostrand, 1963.

[19] W. H e r e r and J.P.R. C h r i s t e n s e n [75], On the existence of pathological submeasures and the construction of exotic topological groups, Math. Ann. 213, 203– 210, 1975.

[20] W. H o d g e s [93], Model Theory, Cambridge Univ. Press, 1993.

[21] A.H. L a c h l a n and R. W o o d r o w [80], Countable ultrahomogeneous undirected graphs, Trans. Amer. Math. Soc. 262, 51–94, 1980.

[22] A.T.-M. L a u, P. M i l n e s, and J. P y m [99], On the structure of minimal left ideals in the largest compactification of a locally compact group, J. London Math. Soc. 59 (2), 133–152, 1999.

[23] J. N e š e tř i l [89], For graphs there are only four types of hereditary Ramsey classes, J. Comb. Theory, Series B 46 (2), 127–132, 1989.

[24] J. N e š e t ř i l [95], Ramsey Theory, Handbook of Combinatorics, R. Graham et al. (Eds.), 1331–1403, Elsevier, 1995.

[25] J. N e š e t ř i l [03], Private communication, 2003.

[26] J. N e š e t ř i l and V. R ö d l [77], Partitions of finite relational and set systems, J. Comb. Theory 22 (3), 289–312, 1977.

[27] J. N e š e t ř i l and V. R ö d l [78], On a probabilistic graph-theoretical method, Proc. Amer. Math. Soc. 72 (2), 417–421, 1978.

[28] J. N e š e t ř i l and V. R ö d l [83], Ramsey classes of set systems, J. Comb. Theory, Series A, 34 (2), 183–201, 1977.

[29] V. P e s t o v [98], Some universal constructions in abstract topological dynamics, Contemporary Math. 215, 83–99, 1998.

[30] V. P e s t o v [98a], On free actions, minimal flows and a problem by Ellis, Trans. Amer. Math. Soc. 350 (10), 4149–4165, 1999.

[31] V. P e s t o v [02], Ramsey-Milman phenomenon, Urysohn metric spaces, and extremely amenable groups, Israel J. Math. 127, 317–357, 2002.

[32] V. P e s t o v [02a], Remarks on actions on compacta by some infinite-dimensional groups, Infinite dimensional Lie groups in geometry and representation theory, (Washington, DC 2000), World Sci., 145–163, 2002.

[33] W. R u d i n [73], Functional Analysis, McGraw-Hill, 1973.

[34] S. T h o m a s [86], Groups acting on infinite dimensional projective spaces, J. London Math. Soc. 34 (2), 265–273, 1986.

[35] P. U r y s o h n [27], Sur un espace métrique universel, Bull. Sci. Math. 51, 43–64, 74–90.

[36] V. U s p e n s k i j [90], On the group of isometries of the Urysohn universal metric space, Comment. Univ. Carolinae 31(1), 181-182, 1990.

[37] V. U s p e n s k i j [00], On universal minimal compact G-spaces, Topology Proc. 25, 301–308, 2000.

[38] V. U s p e n s k i j [02], Compactification of topological groups, Proc. of the 9th Prague Topol. Symp. (Prague 2001), 331–346 (electronic).

[39] W. V e e c h [77], Topological dynamics, Bull. Amer. Math. Soc. 83 (5), 775–830, 1977.

Department of Mathematics Caltech 253-37 Pasadena, CA 91125 kechris@caltech.edu

Department of Mathematics and Statistics University of Ottawa 585 King Edward Avenue Ottawa, Ontario Canada K1N6N5 vpest283@science.ottawa.ca U.F.R. de Mathématiques, U.M.R. 7056 Université Paris 7 2, Pl. Jussieu, Case 7012 75251 Paris Cedex 05 France stevo@math.jussieu.fr

Matematički Istitut, SANU Kneza Mihaila 35 11000 Beograd Srbija stevo@mi.sanu.ac.yu