The random graph, 3

We saw that the random graph has a lot of symmetry (it is homogeneous), but so far we have not seen any specific automorphisms. As promised, I begin with cyclic automorphisms.

First, what does a countable graph with a cyclic automorphism look like? The vertices can be indexed by integers (positive, negative and zero), so that the automorphism acts as a shift on the indices: that is, it maps vn to vn+1 for all n. Now let S be the set of all positive integers n such that v0 is joined to vn. Then the set S determines the graph; for vk is joined to vl if and only if |k–l| belongs to S, as we see by shifting by the negative of the smaller of k and l.

But the set S tells us more. The same graph may have many cyclic automorphisms; each one gives rise to a set of positive integers in the manner described. Now a fairly simple calculation establishes that, if σ and τ are cyclic automorphisms of the same graph X, then σ and τ are conjugate in the automorphism group of X if and only if the corresponding sets of natural numbers are equal.

Hence we have a bijection between, on one hand, the set of all sets of positive integers, and on the other, the set of ordered pairs consisting of a countable graph (up to isomorphism) and a cyclic automorphism of it (up to conjugacy in the automorphism group of the graph).

Recall that a set S of positive integers, whose characteristic function is the zero-one sequence s, is universal if every finite zero-one sequence occurs in s as a consecutive subsequence. Now it is straightforward to show:

The set S is universal if and only if the corresponding graph X is isomorphic to R.

Since universal sets exist, (e.g. one can make one by simply concatenating all the finite zero-one sequences), we see that R does indeed have a cyclic automorphism.

In fact, as we have seen, almost all sets of positive integers (either in the sense of measure, or in the sense of Baire category) are universal. A collection of almost all sets is certainly uncountable (of the cardinality of the continuum). So we can conclude that R has continuum-many pairwise non-conjugate cyclic automorphisms.

Implicitly we have another construction of R: Choose your favourite universal set S of positive integers, and build the graph whose vertex set is the set of all integers, two vertices joined if their difference belongs to S.

Here is a old problem which I recalled while writing these notes. We already saw a construction of R using prime numbers; here, perhaps, is another. Consider the zero-one sequence s whose nth term is 0 if the nth odd prime is congruent to 1 (mod 4), or 1 if the nth odd prime is congruent to 3 (mod 4). Is s universal? Unless I am missing something obvious, this seems to be a hard problem; but in view of the theorem of Green and Tao, perhaps it is time to revisit it!

This method can be extended to find all the possible cycle structures for automorphisms of R. For example, there cannot be an automorphism which has one fixed point and permutes the others in a single cycle, since this would force the fixed point to be joined to all or no other vertices. However, there is an automorphism which fixes a point and permutes the remaining vertices in two cycles (one for neighbours, and one for non-neighbours, of the fixed point).

From the construction of cyclic automorphisms, we see that R has a two-way infinite Hamiltonian path. (Choose a universal set containing 1; then vn is joined to vn+1 for all n.) We’ll see that much stronger properties hold!

Since R is the random graph, it should be unaffected by a small amount of tinkering. One can see that each of the following operations gives a graph which is still isomorphic to R:

  • Removing a finite number of vertices.
  • Adding or removing a finite number of edges.
  • Switching with respect to a finite set of vertices. (The operation of switching with respect to a set A replaces edges between A and its complement by non-edges, and non-edges by edges, while leaving adjacency within or outside A unchanged.)

The second property can be strengthened. Recall that R is universal, that is, it embeds every countable graph as an induced subgraph. Another sort of embedding is as a spanning subgraph, where we are required to use all the vertices, and some of the edges, of the target graph. The following result is easy to show.

  • Let Y be a countable graph having the property that, for every finite set V of vertices of Y, there is a vertex z joined to no vertices in V. Then Y can be embedded as a spanning subgraph of R. (This condition is necessary as well as sufficient.)
  • Let Y be locally finite, that is, any vertex has only finitely many neighbours. Embed Y as a spanning subgraph of R (this is possible by the preceding assertion). Then, on removing all the edges of Y, we obtain a graph isomorphic to R.

The first statement is proved by “back-and-forth”. We construct a bijection from Y to R such that edges map to edges, and the inverse image of a non-edge is a non-edge (this is where the stated property is required). The second statement is straightforward: just show that property (*) can be verified without using any of the removed edges.

The result about Hamiltonian paths is a simple special case.

From this we can prove a remarkable decomposition theorem for R:

Let Y1, Y2, … be a sequence of locally finite graphs, each with at least one edge. Then we can decompose R into spanning subgraphs isomorphic to Y1, Y2, … .

To see this, we first enumerate all the edges of R. Since the automorphism group of R is edge-transitive, we can find a spanning subgraph isomorphic to Y1 containing the first edge in the enumeration. Remove it; the resulting graph is still isomorphic to R, so we can find a spanning subgraph isomorphic to Y2 containing the first unused edge in the enumeration. Continue: at the end of the process, every edge has been used.

So in particular, R has a 1-factorisation, a Hamiltonian decomposition, etc.

Of course, if we alter an arbitrary set of edges, or switch with respect to an arbitrary set of vertices, the result is not always isomorphic to R; but it turns out that it is so “almost always”, in either sense of the word.

All these properties are quite straightforward to prove; in the next post I will turn to properties which lie somewhat deeper.

Previous | Next


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition. Bookmark the permalink.

4 Responses to The random graph, 3

  1. Apart from the countable random graph one can also construct the countable k-partite random graph. I haven’t thought too much about it but it seems that many of the properties of the random graph should hold for the k-partite versions as well.
    Has this already been explored by someone?

    • Yes, especially the bipartite case. One can also consider the random k-edge-coloured complete graph (the random graph corresponds to the case k=2). I decided to focus just on the random graph, at least to begin; I might get onto variants later on…

  2. Pingback: The random graph, 2 « Peter Cameron's Blog

  3. Pingback: The pigeonhole property « Peter Cameron's Blog

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