grandparented tree

An example of a nonamenable and nonunimodular graph, attained by "decorating" a regular tree.

Let T be a (d+1)-regular tree. That is, T is an infinite tree where each vertex has degree d+1, for some d≥2. The best-known example is when d=2, when T can be drawn as a binary tree which has no root and continues infinitely "upwards":

                  |
                  A
               _,-^-._
              B       C
             ,^.     ,^. 
            D   E   F   G
            ^   ^   ^   ^

Diagram of a small segment of a 3-regular tree. A,B,C,D,E,F,G are all vertices; A has a parent (not shown) and D,E,F,G each have 2 children (also not shown).

T is unimodular: For any x and y at distance k from each other, there are automorphisms σ of T which fix x (σ(x)=x) and transfer y to any other z at distance k from x. For instance, an automorphism fixing A can transfer D to itself, or to E,F,G or to the grandparent of A. And an automorphism fixing D can transfer A to itself, or to any of D's four grandchildren. Fixing A, we have 5 possible images of D, and fixing D, we have 5 possible images of A.

T is also nonamenable -- all trees are(n't).

To get a nonunimodular graph T' out of T, we connect each vertex to its grandparent:

                  |
            _,----A----._
           /   _,-^-._   \
           |  B  | |  C  |
           ( ,^. / \ ,^. )
            D   E   F   G 
            ^   ^   ^   ^

Diagram of a small segment of a "grandparented" 3-regular tree. Edges have been added between each of D,E,F,G and A. Edges from B,C to the parent of A are not shown, nor are the edge from A to its grandparent and the 4 edges from each of D,E,F,G to their 4 grandchildren.

How to orient a tree

We orient the tree as follows. First we choose an infinite simple path from some O (a sequence of edges starting from O, which never visits a vertex a second time). This path will be called "up", and we orient each edge on it away from O. To orient every other edge on the tree, we note that there is only one simple path connecting it to our chosen path; the orientation of the edge is towards that path.

The details are unimportant, really. Just assume we draw out the tree and label a particular direction UP. This has the effect of creating parents and children -- edges are from children upwards to their parents. Now we can add edges from grandchildren to their grandparents.

It also shows that the tree is unimodular.

Note that if we allowed only orientation-preserving automorphisms of T, then an automorphism fixing A can transform D onto each of D,E,F,G (4 possibilities), but an automorphism fixing D must also fix A. Our aim is to add edges to T to do just that.

The resulting graph is no longer a tree (for instance, ABDA in the example above is a cycle). It remains nonamenable: adding edges can only increase the isoperimetric constant, and that is already >1 for any tree.

But it is no longer unimodular. In fact, it's possible to show that any automorphism must preserve the parent-child relationship in the original tree (before we added the grandparenting edges, automorphisms could swap parents with a child). To that end, let α:T'→T' be an automorphism of T':

α cannot map a child-parent edge to a grandchild-grandparent edge:

Suppose the edge αA,αB connected a grandchild with a grandparent. Then edge AB participates in d+1 triangles: ABD, ABE and XAB, where X is the parent of A. But αA,αB would only participate in one triangle: αA,Y,αB, where Y is a child of one of αA or of αB and the parent of the other. Since automorphisms map triangles to triangles, this would be impossible.

α cannot reverse a child-parent edge:

Suppose αA were the child of αB. Then the αC must be a child of αA. But now αB,αA,αC must be a triangle -- αB and αC are grandparent and grandchild, and these have an edge between them! There is no edge between B and C, so there cannot be an edge between their images.

So αA must be the parent of αB.

So (at last!) T' is nonunimodular: For suppose σB=B for some automorphism B. Then σA must be the parent of σB, so σ also fixes A (and every ancestor of A). An automorphism fixing B can only assign 1 value to A.

On the other hand, an automorphism fixing A can transfer B either to itself or to C. So

2 = |(Stab(A))(B)| ≠ |(Stab(B))(A)| = 1