Involution-free Trees are Asymmetric: Reference request - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T00:03:57Z http://mathoverflow.net/feeds/question/63171 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/63171/involution-free-trees-are-asymmetric-reference-request Involution-free Trees are Asymmetric: Reference request John Faben 2011-04-27T13:41:44Z 2011-04-27T15:27:48Z <p>I am currently writing a proof in which I need to use the fact that if a tree has no involutions, its automorphism group is trivial (ie, if a tree has any non-trivial automorphisms, then it has at least one automorphism of order 2). Equivalently, the order of the automorphism group of a tree is either equal to 1 or it is even.</p> <p>I can prove this fact directly myself, but I assume I'm not the first person to have noticed it - does anyone know where I can find a published proof - I've tried a few graph theory text books, but I'm not really sure where to look in the literature.</p> http://mathoverflow.net/questions/63171/involution-free-trees-are-asymmetric-reference-request/63176#63176 Answer by Igor Rivin for Involution-free Trees are Asymmetric: Reference request Igor Rivin 2011-04-27T14:23:26Z 2011-04-27T14:23:26Z <p>Look for "Automorphisms of Graphs" by P. J. Cameron (google finds the pdf), and look at the result of Polya on page 8 -- it states that the class of automorphism groups of trees is the smallest class containing the trivial group and closed under the operations of "direct product" and "wreath product with the symmetric group $S_n$ for each $n>1.$" Since symmetric groups have even order, your result follows.</p> http://mathoverflow.net/questions/63171/involution-free-trees-are-asymmetric-reference-request/63185#63185 Answer by darij grinberg for Involution-free Trees are Asymmetric: Reference request darij grinberg 2011-04-27T15:06:29Z 2011-04-27T15:27:48Z <p>In the following, all trees are finite trees.</p> <p>First a lemma:</p> <p><strong>Lemma 1.</strong> Let $T$ be a tree, and $f:T\to T$ be an automorphism of this tree. Then, either there exists a vertex of $T$ fixed by $f$, or there exist two vertices of $T$ mutually mapped to each other by $f$.</p> <p><em>First proof of Lemma 1.</em> We prove Lemma 1 by strong induction over the number of vertices of $T$. Here is the induction step:</p> <p>Let $v_0$ be a vertex of $T$ which has only one neighbour (such a vertex clearly exists). The automorphism $f$ maps it to a vertex $v_1$ which also has only one neighbour. This vertex is, in turn, mapped to a new vertex $v_2$ which also has only one neighbour. And so on, until we find an $n$ such that $v_n=v_0$. Consider this $n$.</p> <p>WLOG assume that our tree $T$ has more than two vertices (else, Lemma 1 is trivial). Then, if we remove the vertices $v_0$, $v_1$, ..., $v_{n-1}$ from $T$, we are still left with a tree; denote this tree by $T^{\prime}$. (The only thing we need to care about is that this tree is nonempty, but if it is empty, then every vertex of $T$ must have had one neighbour only, meaning that $T$ is the tree on two vertices.)</p> <p>The automorphism $f$ of $T$ restricts to an automorphism $f^{\prime}$ of $T^{\prime}$.</p> <p>Now, apply Lemma 1 to the tree $T^{\prime}$ with the automorphism $f^{\prime}$ instead of the tree $T$ with the automorphism $f$ (here, we use the fact that $T^{\prime}$ is a tree with less vertices than $T$, so we can apply Lemma 1 to it by our induction assumption). Thus the induction step is done, and Lemma 1 is proven.</p> <p><em>Second proof of Lemma 1.</em> Consider the tree $T$ as a topological space $X$, and extend $f$ to an automorphism $g$ of this space $X$ (by setting $g\left(v\right) = f\left(v\right)$ for any vertex $v$ of $T$, and extending to each edge by linearity). Then, we want to show that this topological automorphism $g$ has a fixed point (because if such a fixed point is a vertex of the tree, we get a fixed vertex, while if it is an interior point of an edge, we get a fixed edge). By the <a href="http://en.wikipedia.org/wiki/Lefschetz_fixed-point_theorem" rel="nofollow">Lefschetz fixed-point theorem</a>, this will be immediate once we succeed to show that $\sum_{k\geq 0}\left( - 1\right)^k\mathrm{Tr}\left(g_*\mid H_k\left(X,\mathbb{Q}\right)\right)\neq 0$. This simplifies to $\mathrm{Tr}\left(g_*\mid H_0\left(X,\mathbb{Q}\right)\right)\neq \mathrm{Tr}\left(g_*\mid H_1\left(X,\mathbb{Q}\right)\right)$ (because the space $X$ is $1$-dimensional). Now, $\mathrm{Tr}\left(g_*\mid H_1\left(X,\mathbb{Q}\right)\right) = 0$ (since $H_1\left(X,\mathbb{Q}\right) = 0$, because $X$ is contractable), but $\mathrm{Tr}\left(g_*\mid H_0\left(X,\mathbb{Q}\right)\right)\neq 0$ (because $H_0\left(X,\mathbb{Q}\right)$ is $\mathbb{Q}$ (since the space $X$ has one connected component), and $g_*$ is an automorphism of $H_0\left(X,\mathbb{Q}\right)$ (because $g$ is an automorphism of $X$)), thus $\mathrm{Tr}\left(g_*\mid H_0\left(X,\mathbb{Q}\right)\right)\neq \mathrm{Tr}\left(g_*\mid H_1\left(X,\mathbb{Q}\right)\right)$, and we are done.</p> <p>Next, we show:</p> <p><strong>Lemma 2.</strong> Let $T$ be a <em>rooted</em> tree. If $T$ has a nontrivial automorphism, then $T$ has an automorphism of order $2$.</p> <p>Note that an automorphism of a <em>rooted</em> tree means an automorphism which keeps the root fixed!</p> <p><strong>EDIT:</strong> See the comments below for a short proof of Lemma 2.</p> <p><em>Proof of Lemma 2.</em> We prove Lemma 2 by strong induction over the number of vertices of $T$. Here the induction step:</p> <p>Assume that $T$ has a nontrivial automorphism. Let $f$ be such an automorphism. Then, $f\neq\mathrm{id}$. Let $p$ be the root of $T$. Then, $f\left(p\right)=p$.</p> <p>Let $d_1$, $d_2$, ..., $d_k$ be the children (= <em>direct</em> descendants) of $p$. For every vertex $d$ of T, let $T_d$ be the subtree of $T$ formed by all descendants of $d$ (which means $d$ itself, its children, the children of its children, etc.). Clearly, every vertex of $T$ except of $p$ is a vertex of one and only one of the subtrees $T_{d_1}$, $T_{d_2}$, ..., $T_{d_k}$.</p> <p>Now, we see that:</p> <p>(1) For every vertex $d$ of $T$, we have $f\left(T_d\right)\subseteq T_{f\left(d\right)}$.</p> <p>This is because the vertices of $T_d$ can be characterized as those vertices of $T$ which have $d$ among their ancestors, and thus their images under $f$ must have $f\left(d\right)$ among their ancestors (because the relation "being an ancestor of" is invariant under any automorphism of a <em>rooted</em> tree).</p> <p>Here is a stronger result:</p> <p>(2) For every vertex $d$ of $T$, we have $f\left(T_d\right)= T_{f\left(d\right)}$.</p> <p>In fact, let us apply the relation (1) to $f^{-1}$ and $f\left(d\right)$ instead of $f$ and $d$. Thus we obtain $f^{-1}\left(T_{f\left(d\right)}\right)\subseteq T_{f^{-1}\left(f\left(d\right)\right)}$. Hence, $f\left(f^{-1}\left(T_{f\left(d\right)}\right)\right)\subseteq f\left(T_{f^{-1}\left(f\left(d\right)\right)}\right)$. Since $f$ is bijective (being an automorphism), this becomes $T_{f\left(d\right)}\subseteq f\left(T_d\right)$. Combined with (1), this yields $f\left(T_d\right)= T_{f\left(d\right)}$, and thus (2) is proven.</p> <p>For every vertex $d$ of $T$, we regard $T_d$ as a rooted tree with root $d$. Now we distinguish between two cases:</p> <p><em>Case 1.</em> There exist two distinct elements $i$ and $j$ of $\left\lbrace 1,2,...,k\right\rbrace$ such that $f\left(d_i\right)=d_j$.</p> <p><em>Case 2.</em> Every $i\in\left\lbrace 1,2,...,k\right\rbrace$ satisfies $f\left(d_i\right)=d_i$.</p> <p>Clearly, these two cases cover all possibilities.</p> <p>Consider Case 2 first. In this case, every $i\in\left\lbrace 1,2,...,k\right\rbrace$ satisfies $f\left(d_i\right)=d_i$. Thus, (2) yields that every $i\in\left\lbrace 1,2,...,k\right\rbrace$ satisfies $f\left(T_{d_i}\right)=T_{f\left(d_i\right)}=T_{d_i}$. Therefore, the automorphism $f$ of $T$ can be decomposed into automorphisms of the rooted subtrees $T_{d_1}$, $T_{d_2}$, ..., $T_{d_k}$. At least one of these automorphisms is nontrivial (because $f$ is nontrivial). That is, there exists some $i\in\left\lbrace 1,2,...,k\right\rbrace$ such that the rooted tree $T_{d_i}$ has a nontrivial automorphism. For this $i$, we can then conclude that there exists an automorphism of order $2$ of the rooted tree $T_{d_i}$ (by Lemma 2, applied to the smaller tree $T_{d_i}$ instead of $T$, which is legitimate since we are doing a strong induction). This automorphism can obviously be extended to an automorphism of order $2$ of the rooted tree $T$ (just let it act as identity on the $T_{d_j}$ for all $j\in\left\lbrace 1,2,...,k\right\rbrace\setminus\left\lbrace i\right\rbrace$ as well as on $p$), and the induction step is complete in Case 2.</p> <p>Now let us study Case 1. In this case, there exist two distinct elements $i$ and $j$ of $\left\lbrace 1,2,...,k\right\rbrace$ such that $f\left(d_i\right)=d_j$. Consider these $i$ and $j$. By (2) we have $f\left(T_{d_i}\right)=T_{f\left(d_i\right)}=T_{d_j}$, so that $f$ induces an isomorphism $g:T_{d_i}\to T_{d_j}$ of rooted trees. Now, we can define an endomorphism $h$ of the rooted tree $T$ as follows:</p> <ul> <li><p>let $h\left(u\right)=g\left(u\right)$ for every $u\in T_{d_i}$;</p></li> <li><p>let $h\left(u\right)=g^{-1}\left(u\right)$ for every $u\in T_{d_j}$;</p></li> <li><p>let $h\left(u\right)=u$ for every $u\in T_{d_r}$ for any $r\in\left\lbrace 1,2,...,k\right\rbrace\setminus\left\lbrace i,j\right\rbrace$;</p></li> <li><p>let $h\left(p\right)=p$.</p></li> </ul> <p>This definition is legitimate since the set of the vertices of $T$ is the disjoint union of the sets of the vertices of $T_{d_1}$, $T_{d_2}$, ..., $T_{d_k}$ and the one-element set $\left\lbrace p\right\rbrace$.</p> <p>Clearly, $h$ is an automorphism of order $2$ of the rooted tree $T$, so we have shown the assertion of Lemma 2 for our $T$, and the induction step is complete in Case 1.</p> <p>We have thus completed the induction step in both cases, and therefore proven Lemma 2.</p> <p><strong>Theorem 3.</strong> Let $T$ be a (non-rooted) tree. If $T$ has a nontrivial automorphism, then $T$ has an automorphism of order $2$.</p> <p><em>Proof of Theorem 3.</em> Assume that $T$ has a nontrivial automorphism. Let $f$ be such an automorphism. Then, $f\neq\mathrm{id}$. Lemma 1 yields that either there exists a vertex of $T$ fixed by $f$, or there exist two vertices of $T$ mutually mapped to each other by $f$. But in the latter case, we are done (because if there exist two vertices of $T$ mutually mapped to each other by $f$, then $f$ must have an even order, and thus some power of $f$ has order $2$). So let us consider the former case only. In this case, there exists a vertex of $T$ fixed by $f$. Let $p$ be such a vertex. Then, considering $p$ as a root, we make $T$ into a rooted tree, and $f$ becomes a nontrivial automorphism of this <em>rooted</em> tree. Thus, by Lemma 2, the rooted tree $T$ has an automorphism of order $2$. Theorem 3 is proven.</p>