4
$\begingroup$

Please give me some hints for the following problems. Many thanks in advance.

Problem 1. Let $T_1,\cdots, T_n$ be a finite set of subtrees of a tree $X$ and let $T_i\cap T_j\ne\emptyset$ for all $i$ and $j$. Then $\cap_{i=1}^nT_i\ne\emptyset$.

Problem 2. Let $G$ be a finite automorphism group of a tree $T$, acting on $T$ without inversion of edges. Then there exists a vertex of $T$ fixed by each element of $G$.

  • 0
    Problem 1 is http://math.stackexchange.com/questions/857698/for-all-1-leq-i-j-leq-k-the-subtrees-t-i-and-t-j-have-a-vertex-in-com .2017-02-23

2 Answers 2

3

Problem 2)

The height of a node is the length of the shortest path from that node to a leaf vertex. Given a finite tree $T$ it is clear that any automorphism $\phi = Aut(T)$ of $T$ sends nodes of height $0$ (leaves) to nodes of height $0$ and one can show that $\phi$ takes nodes at height $h$ to nodes with height $h$. Denote the height of vertex $v$ by $h(v)$.

Let $V$ be the set of nodes such that given any node $w \notin V$ and $v \in V$ then $h(w) < h(v)$. Since $T$ is connected the induced subtree of $T$ with vertices in $V$ must be connected and $|V| = 1$ or $|V| = 2$. Since we do not allow inversions of edges all $v \in V$ are fixed points of $\phi$.

For a more geometric proof that $\phi$ has at least one fixed point we appeal to a theorem of P\'{o}lya which says that the automorphism group $Aut(T)$ admits a direct product decomposition : $Aut(T) \cong G_1 \times G_2 \times \dots \times G_k$ such that either $G_i \cong S_m$ a symmetric group or $G_i$ is isomorphic to a wreath product of symmetric groups. This decomposition has a pleasing geometric decomposition where each symmetric $S_m$ acts on an induced subtree of $T$ which consists of a hub vertex adjacent to $m$ paths of the same length. Each wreath product is associated to a hub vertex of a more complicated extended symmetric branch. The hubs associated with each $G_i$ are fixed by every element of $Aut(T)$.

0

Problem 1. The general statement may be deduced by induction from the case $n=3$, so let $T_1$, $T_2$ and $T_3$ be three subtrees satisfying $T_i \cap T_j \neq \emptyset$. Let $x \in T_1 \cap T_2$, $y \in T_2 \cap T_3$ and $z \in T_3 \cap T_1$. The geodesics between $x,y,z$ define a tripod with $[x,y] \cap [y,z] \cap [z,x]= \{w\}$. By connectedness, $w \in T_1 \cap T_2 \cap T_3$ hence $T_1 \cap T_2 \cap T_3 \neq \emptyset$.

In fact, the same argument works for median graphs. More generaly, there is an analogue of Helly's theorem: A family of pairwise intersecting convex subsets has a non-empty intersection. (See Roller's dissertation for more information.)

Problem 2. I gave two solutions to this problem in the other post Actions of Finite Groups on Trees; one may be based on CAT(0) geometry, and the other uses Bass-Serre theory.