1
$\begingroup$

Let $\Gamma$ be an infinite, locally finite tree without end points, with the additional property that there exists a positive integer $N$ such that for each occurring valency $v$, we have that $v \leq N$.

What can be said about the symmetry of $\Gamma$ ?

Due to its defining properties, it must contain many isomorphic (finite) subtrees, but can one conclude anything about its automorphism group ?

$\endgroup$
1
  • 2
    $\begingroup$ Here's another recipe to get trivial Aut: start from a trivalent regular tree, enumerate its edges as $(e_n)_{n\ge 1}$ and replace $e_n$ with $n$ consecutive edges. The resulting tree has a trivial Aut (and each vertex has valency $2$ or $3$). $\endgroup$
    – YCor
    Sep 30, 2022 at 18:03

1 Answer 1

4
$\begingroup$

Here is an example of such a tree with no non-trivial isomorphisms. It is constructed randomly and iteratively in the following way: it has a so-called root $p$ with 5 children, and each of the descendants can have either 2 or 3 children, randomly and independently of the others. In particular, it is an infinite tree with maximal degree 5 and no leaves.

Let us make this construction more precise. We consider first the deterministic tree $T_0=(V_0,E_0)$, where

  • the vertices of $V_0$ are the finite words $a_0a_1\cdots a_k$ with $a_0\in\{1,\ldots,5\}$ and $a_i\in\{1,2,3\}$ for $i>0$, including the empty word $\varepsilon$;
  • the edges are all pairs of 1-step prefixes in $V_0$, i.e. elements of the form $\{a_0\ldots a_k,a_0\ldots a_ka_{k+1}\}$.

Now consider $E'$ a random subset of $E$ where the events $\{e\in E\}$ are jointly independent, with probability $1/2$ in the case $e=\{a_0\ldots a_k,a_0\ldots a_k3\}$, $k>0$, and with probability $1$ otherwise. Now $T=(V,E)$ is the connected component of $\varepsilon$ in $(V_0,E_0)$.

We need to show that an isomorphism of $T$ has to be trivial (almost surely). We base the approach on the following lemma.

Lemma. Let $S$ and $S'$ be two independent rooted trees, where each individual has either 2 or 3 children with probabilities 1/2, independently of the others. Then the probability that they are isomorphic is zero.

Assume the lemma for now, and take an isomorphism of the tree. The root has to be sent to itself, because it is the only vertex of degree 5. The 5 rooted subtrees branching from it cannot be isomorphic using the lemma, which forces the children to be fixed. For the same reason, the rooted subtrees branching from a given child are also not isomorphic, so the grand-children have to be fixed, and iteratively all descendants are the same and the isomorphism is trivial.

To prove the lemma, let us find functions $f_n(S)$ invariant under tree isomorphisms, such that the probability of each possible value goes to zero, i.e. $\limsup_n\sup_k\mathbb P(f_n(S)=k)=0$. Indeed, in this case the probability of $f_n(S)=f_n(S')$ is at most $\sup_k\mathbb P(f_n(S)=k)$ hence goes to zero, and on the almost-sure event that at least one of the functions evaluates to different values the trees are not isomorphic.

I am sure there are easier examples, but I came up with the following one. Let $g_n(S)$ be the number of $\text{grand}^{n-1}\text{children}$. By some quantitative version of the central limit theorem (say Berry-Esseen), $$ f_n(S)=\frac{g_{n+1}(S)-\frac52g_n(S)}{\sqrt{g_n(S)/4}}$$ converges in distribution to a standard Gaussian, hence the probability of a given value cannot stay large in the limit, and $(f_n(S))_{n\geq0}$ satisfies the expected properties.

$\endgroup$
1
  • 1
    $\begingroup$ Using the same ideas, one can see that any automorphism group of a (possibly finite) vertex-coloured tree of bounded degree arises as some $\operatorname{Aut}(\Gamma)$. My example is the case of the tree with one vertex. $\endgroup$
    – Pierre PC
    Sep 30, 2022 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.