"The" random tree

Question

One time I heard a talk about "the" random tree. This tree has one vertex for each natural number, and the edges are constructed probabilistically. Connect vertex $2$ to vertex $1$. Connect vertex $3$ to vertex $1$ or $2$ with probability $\frac{1}{2}$. Connect vertex $n+1$ to exactly one of vertices $1,\dots, n$ with equal probability $\frac{1}{n}$. This procedure will construct an infinite tree. The theorem is that with probability $1$, any tree constructed this way will be the same (up to permutation of the vertices).

My question is, does anyone know of a reference for this result? What is the automorphism group of this tree? Can anyone draw a picture of it?

I don't have any reason for knowing about this, just curiosity, and I wasn't able to turn up anything with a (not too extensive) internet/mathscinet search.

Answer 1

I learned about The random graph a week ago from the blog post on n-cafe (thanks to Andrew and sdcvvc for the links!).

Your construction, while slightly different, can be examined in the same way as the Rado graph. Note, by the way, that expected number of edges meeting at each point is infinity, as is with Rado's graph.

The lemma you want to prove is, I think, this:

Fix an isomorphism between two finite sets $A\to B$ and number $a\notin A$. Take random trees $X$, $Y$ having property that $X|_A = Y|_B$. Then with probability 1 there exists $b\notin B$ such that the isomorphism can be extended to $A\cup\{a\}$ and $B\cup\{b\}$.

A repeated application of this (or very similar) lemma should yield your result: there is an isomorphism between two random trees with probability 1.

---

Your trees have actually quite simple structure: with probability 1 all vertices have infinite degree. Any two connected trees with this property can be drawn starting from one point and adding infinitely many edges to it, then to leaves, then adding infinitely edges to each leaves and so on.

Sorry, the quality of the picture isn't good:

+ --- + --- + ...
|     |
|     + --- + ...
|
+ --- + --- + ...
|     |
|     + --- + ...
|
+ --- + --- + ...
|     |
|     + --- + ...

Since the trees you descrived are always connected (see comments), this is "the canonical drawing".

In particular, the stabilizer of a point has a filtration by groups of the form $S_\infty$ and $(S_\infty)^\infty$ (interchanging the "outer" edges of a given leaf is $S_\infty$).

Answer 2

There is a paper in JSTOR, The continuum random tree, I, by David Aldous, that is similar to your question. That is the first of a three part series of papers. However, it doesn't seem like Aldous' tree (or tree ensemble) can be the same as your tree. Your tree would have infinite valence everywhere, because the harmonic series diverges.

---

To expand a little on this alternate answer that was studied by David Aldous: Suppose that, instead of the process that Ian suggested, you take a random spanning tree of the complete graph on $n$ vertices. Or more properly, you take the ensemble of spanning trees of the complete graph, and then attempt a limit of those ensembles as $n \to \infty$. You can obtain a good ensemble in that limit by looking, for each $k$, at the $k$-neighborhood (in the tree) of a marked vertex, and then sending $k$ to infinity after $n$ is sent to infinity. Then you get a well-defined ensemble of infinite rooted trees, which is hopefuless the same as what Aldous studies. I think that it is a valid model of what is sometimes called "the" random tree.

For instance, what is the probability that the root is a leaf? Using the formula that there are $n^{n-2}$ labelled trees on $n$ vertices, you can compute that it is $1/e$. If I set up the tree properly, then it would mean that $1/e$ of the vertices are leaves, almost surely.

"The" random tree in this sense is statistically the same everywhere, to every finite size of neighborhood. However, I think that it can't be the same tree out to infinity every time, because it contains an infinite amount of data to distinguish samples. For instance the spacing between leaves is an infinite amount of data. I'm not expert enough to arrive at this rigorously, but I believe that a "translation invariant" random process that really gives you the same tree every time would have to give you a boring tree with the same valence everywhere. (This is what I meant by my joke that it would be barking up the wrong tree.) On the other hand, if you do make a "translation invariant" ensemble of trees, then it could be "the" tree in the sense that you might recover all of the local statistics of the entire ensemble just by average over one typical sample.

An analogue that I understand rather better is the Penrose tiling. It is "the" Penrose tiling in the sense that any one Penrose tiling has the local statistics of all Penrose tilings. On the other hand, there are uncountably many different Penrose tilings. (In a natural sense, the Penrose tilings form an ergodic family; they come from a foliation of an $A_4$-shaped torus by parallel planes.)

Answer 3

Since it is regular of countably infinite degree, it is isomorphic to the union of Bruhat-Tits trees for PGL₂(F) as F ranges over unramified extensions of a local field. The automorphism group therefore contains PGL₂(F^nr), but I don't know much more.

Edit: The automorphism group is apparently described in a 1970 paper by Tits: Sur le groupe des automorphismes d'un arbre, which is not available on line. There is a description of its subgroups of index less than continuum cardinality in Moller's paper The automorphism groups of regular trees - any such subgroup is either the simple index 2 subgroup generated by stabilizers of points, or lies between the pointwise stabilizer of a finite (possibly empty) subtree and the setwise stabilizer of the same subtree. The stabilizer of a point is a limit of a system of wreath products of Sym(Aleph₀).

Answer 4

The algorithm you describe is at each stage isomorphic to an algorithm for picking a particular tree from the "Uniform Spanning Tree" (which is THE uniform distribution of all possible spanning trees) when applied to any finite fully connected graph.

One standard method is to iterate choosing new points at random (uniformly from the unconnected ones) and performing a "Loop Erased Random Walk" until "hitting" the existing tree.

The isomorphism of algorithms is because such a fractal growth process is uniform so we can modify it at each LERW by removing the irrelevant intermediate points. This is just shrinking the graph by removing nodes on a line without changing "connected-ness".

The large-scale symmetry under permutations is due to the "uniform probability" property of all finite sub-trees.

Bit of a hand-wavy argument so far I know but UST is the way to go. A fully connected graph is a simpler starting point than the 50% connected Rado graph but .. Corollary .. I imagine any graph with a bounded below probability of connected-ness must almost surely have "THE random tree" as a sub-graph as n grows. Average density of connections of "THE random tree" is $\frac2{n-1}$ and expected neighbours of $k$'th point is $\sum_{i=k+1}^n\frac1i$, so by permuting a large sub-graph of Rado to order the most connected points earliest we can comfortably exceed this everywhere and select at least one tree with probability approaching $1$ as $n\rightarrow\infty$.

Answer 5

Here are some pictures of the random tree reduced over a finite number of nodes.

Over $32$ nodes: The random tree over 32 nodes. http://www.freeimagehosting.net/newuploads/ta8ni.png

Over $96$ nodes: The random tree over 96 nodes. http://www.freeimagehosting.net/newuploads/3yl9z.png

Over $512$ nodes: The random tree over 512 nodes. http://www.freeimagehosting.net/newuploads/qqcm4.png

I employ the following ${\tt Sage}$ code to generate these:

def random_tree(n) :
    tree = Graph()
    tree.add_vertex(1)
    for i in xrange(2, n + 1) :
        tree.add_edge(i, randint(1, i - 1))
    return tree

and the following code to draw these:

tree = random_tree(32)
tree.plot(vertex_size = 24, vertex_labels = False, graph_border = True, iterations = 4096)

Answer 6

Obligatory n-cafe link: David Corfield brought this up recently here and there's quite a discussion about it there.