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
    What does "without inversion of edges" mean ?2012-11-10
  • 0
    Can you be more specific about what you mean by tree and what you mean by automorphism of trees? (In other words, in which category of trees are you working?). Also what do you mean by subtree?2012-11-10
  • 0
    @Amr: "without inversion of edges" means $ge\ne\bar e$ for all $g\in G$ and all edges $e$ of $X$. Here $\bar e$ is the inverse edge of $e$, in the sense that : the initial vertex of $e$ is the terminal vertex of $\bar e$ and vice versa.2012-11-10
  • 0
    @IttayWeiss : A tree is a connected graph without circuits, and I mean by an automorphism of a tree $X$ is a bijective map $p$ from the set of vertices and edges of $X$ to the set of vertices and edges of $X$ sending vertices to vertices, edges to edges, satisfying $p(i(e))=i(p(e))$, $p(t(e))=t(p(e))$ and $p(\bar e)=\overline{p(e)}$, where $i(e)$ and $t(e)$ are the initial vertex and terminal vertex of $e$ respectively.2012-11-10
  • 0
    and what is meant by subtree?2012-11-10
  • 0
    @IttayWeiss : a subtree of a tree $X$ is a tree whose vertices and edges form a subset of the set of vertices and edges of $X$.2012-11-10
  • 1
    For Problem 1, the case $n=3$ is critical, so let $A,B,C$ be subtrees. If false, then you get a circuit going from $A \cap B$ to $B \cap C$ to $A \cap C$. Problem 2 is reduced by Problem 1 to finite cyclic groups.2012-11-11
  • 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.