Almost highly transitive

I want to discuss a concept I have known about for quite a long time, but never found any real use for. Suggestions welcome!

Highly transitive groups

A permutation group is n-transitive if it has a single orbit on the set of n-tuples of distinct elements from its domain; it is highly transitive if it is n-transitive for all natural numbers n. (This concept, of course, applies only to infinite permutation groups.)

Apart from the symmetric group, and the finitary symmetric group, there are very many examples; many additional properties can also be required.

Almost highly transitive groups

The context is measure theory: we have a probability space X (a measure space of total measure 1). As usual, we say that something happens “almost everywhere” if it is true on a set of measure 1 (that is, everywhere except for a null set).

We say that a group G of measure-preserving transformations of X is almost transitive if it has an orbit (necessarily unique) of measure 1. More generally, G is almost n-transitive if it has an orbit of measure 1 on Xn (the set of n-tuples of elements of X, with the product measure); and G is almost highly transitive if it is almost n-transitive for all natural numbers n.

First example: graphs

There is a natural measure on the set of all graphs on a given countable vertex set V, described by the phrase “choose edges independently with probability 1/2”. More formally, we give measure 1/2n(n−1)/2 to the set of graphs which induce a given finite graph on a given n-element subset of V, and extend to the Borel sets (or the Lebesgue-measurable sets) in the standard way. The symmetric group on the set V acts as a group of order-preserving transformations of this space.

The Erdős–Rényi theorem (see here), asserting that a specific graph R (the “random graph” or “Rado graph”) occurs – up to isomorphism – with probability 1, shows that Sym(V) is almost transitive: isomorphisms are induced by elements of the symmetric group.

Now choose n graphs independently at random from this probability distribution. There are 2n possibilities for the structure of a pair of vertices, since they may be an edge or a non-edge in each of the n chosen graphs. The Erdős–Rényi argument, almost unchanged, says that a unique structure arises with probability 1.

Thus the action os Sym(V) on the space of graphs is almost n-transitive for all n, that is, almost highly transitive.


Now consider the same group Sym(V) for a countable set V, acting on the set of total orders of V.

How do we choose a total order at random? One way is to enumerate the points of V, as v1, v2, …, and order them in stages. Suppose that, after n stages, the first n points have been ordered. Then they give n+1 “intervals”: before the smallest, between the smallest and the second smallest, …, after the largest; assign the (n+1)st point randomly to one of these intervals, all intervals equally likely.

A calculation shows that this measure can also be described by saying that, given any n points, all n! orderings are equally likely. (There is something to prove since the n points may not be the first in the enumeration.) This description shows that Sym(V) does indeed act as a group of measure-preserving transformations.

Perhaps not surprisingly, a random order is isomorphic to the order of the rational numbers with probability 1. By Cantor’s theorem, this is the unique dense order without endpoints on a countable set, so it suffices to show that the random order is dense and without endpoints with probability 1. By the usual argument invoking the fact that a countable union of null sets is null, it suffices for density to prove that given two points y and z, conditional on y < z, the probability that no point lies between y and z is zero.

But we can compute this probability. Starting at stage n (assuming that by this stage we know that y is smaller than z and no point lies between), the probability that no subsequent point is put into this gap is

(1-1/(n+1))(1-1/(n+2))… = 0

(the infinite product diverges).

The proof that there is no least or greatest element is similar.

So we have established that Sym(V) is almost transitive on the set of orders.

The proof that it is almost n-transitive involves a small subtlety, which held me up for a while. The object we should get if we choose n orders independently is the unique countable homogeneous universal n-order (described here). But the calculation similar to the one I did above is much more difficult.

The trick is as follows. I describe the case n = 2 (biorders) here; the general case is similar.

Another way to describe the countable dense order without endpoints is as follows. Sample countably many points from the uniform distribution on the open unit interval. The denseness and absence of endpoints are easily shown by simple arguments involving geometric probability.

Now we see that choosing two such orders is equivalent to sampling countably many points from the open unit square. Once again the defining property of the universal homogeneous biorder is easily verified.

So, indeed, Sym(V) is almost highly transitive on the set of orders on V.

Triangle-free graphs

There is a nice triangle-free graph (countable, universal, homogeneous), namely Henson’s graph. I struggled for years to find a similarly nice measure which gives the isomorphism class of Henson’s graph measure 1; the difficulty arises because triangle-free graphs have a very strong tendency to be bipartite (the Erdős–Kleitman–Rothschild theorem). The problem was solved by Petrov and Vershik, as I described here.

So Sym(V) acts as measure-preserving transformations of the space of all graphs on the vertex set V, with the Petrov–Vershik measure, and the action is almost transitive; the unique orbit of measure 1 is the isomorphism class of Henson’s graph.

Problem: Is this action almost highly transitive?

Footnote: Baire category

If G acts by isometries on a complete metric space, there is an analogous notion of “almost transitive”: G is almost transitive if it has an orbit which is residual (contains a countable intersection of open dense sets). Then we can make a similar definition of “almost highly transitive”.

As usual in this game, the Baire category notion is much better explored than the probabilistic notion. In particular, many closed permutation groups (such as the symmetric group, and the automorphism group of the random graph) have the property that their actions on themselves by conjugation is almost highly transitive: that is, there is a generic element (whose conjugacy class is residual), and indeed, for any n, a generic n-tuple of elements. These facts play an important role in the proof of the strong index property for these groups.


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in Uncategorized and tagged , , , , , , , . Bookmark the permalink.

One Response to Almost highly transitive

  1. Colin says:

    The Baire category business also applies to locally compact Hausdorff spaces, which would include a lot of natural examples of measure spaces. Also, there is no need to assume that G acts by isometries/homeomorphisms, only that it preserves Baire category, so there is a lot of flexibility here. (Likewise in the measure theory setting, you can generalise from ‘measure-preserving’ to ‘null-measure-preserving’.)

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s