24
$\begingroup$

Recently I have been thinking about the following poset: the underlying set is $\mathcal{AFT}$ consisting of all (finite) automorphism-free undirected trees (with at least one edge to exclude the trivial cases pointed out by Joel) and the poset relation $\leq$ is defined by $T \leq U$ if $T$ can be obtained from $U$ by successively deleting one leaf node at a time in such a way that each intermediate tree is also an element of $\mathcal{AFT}$.

The smallest element of $\mathcal{AFT}$ is the seven node tree which is the Dynkin diagram of $E_7$ (and which I will therefore refer to simply as $E_7$ from herein):

Dynkin diagram of E7

So $E_7$ is certainly a minimal element in the above partial order.

Question: Does $(\mathcal{AFT},\leq)$ have a unique minimal element, namely $E_7$?

There are several equivalent formulations of this question which I have considered, hoping one of them might lead somewhere useful:

Question 2: Can every element of $\mathcal{AFT}$ be obtained by starting at $E_7$ and successively adjoining leaf nodes so that we remain in $\mathcal{AFT}$ at every stage?

>

Question 3: Is there an element of $\mathcal{AFT}$ besides $E_7$ such that deleting $any$ single leaf node results in a tree not in $\mathcal{AFT}$.

Question 3 in particular seems simple enough that it must have been answered somewhere before, but alas almost any search for 'automorphism-free' and 'trees' results in papers about the result that almost every tree has an automorphism or results on the fixed vertices/edges of trees under automorphisms.

Trying to construct a minimal example larger than $E_7$ for Question 3 keeps leading to near-misses where all but one leaf nodes' removal takes us outside $\mathcal{AFT}$, but after removing this one leaf node, there is still a sequence of removals remaining in $\mathcal{AFT}$ that leads back to $E_7$ which is the best evidence I have so far that Question 1 is true.

So, does anyone know where this might have been considered already, and if so, if the answer to Question 1 is affirmative?

$\endgroup$
16
  • 1
    $\begingroup$ Why don't you regard the one-point tree in AFT? Or the empty tree? $\endgroup$ Dec 24, 2012 at 17:08
  • 1
    $\begingroup$ Show that every large member has E_7 as a subtree, and then show that every large member is not minimal. Large can probably be taken to mean 10 or more vertices. Finish up with a detailed examination of not large members. Gerhard "Sketches Of Proof Sketches Sketched" Paseman, 2012.12.24 $\endgroup$ Dec 24, 2012 at 17:08
  • 3
    $\begingroup$ Just wanted to say--this is a great question. $\endgroup$ Dec 25, 2012 at 2:58
  • 1
    $\begingroup$ Computer says that, up to 22 vertices, there is no other minimal element in AFT. There is apparently a well-established counting "mechanics" for AFT, see oeis.org/A000220 Perhaps an answer to Q3 can be dug up there. $\endgroup$ Dec 25, 2012 at 16:15
  • 1
    $\begingroup$ Kind of off topic, but: why do people so often say "unique minimal element" when "least element" is shorter and (I would say) more vivid? They're the same, at least under the axiom of choice. But undeniably, the definition of local ring is phrased in terms of a "unique maximal (proper) ideal" waaay more often than "largest (proper) ideal". Why? $\endgroup$ Jan 15, 2013 at 23:54

2 Answers 2

8
$\begingroup$

The answer is yes. With Ringi Kim and Paul Seymour, we proved this a few days ago, and the following is the proof. (I am not sure if this is already known or not. Please let me know if it is.)

Some definitions first. For a tree $T$ and $u,v \in V(T)$, $dist_T(u,v)$ is the length of the (unique) path from $u$ to $v$ in $T$. $T \setminus u$ denotes the forest obtained from $T$ by deleting the vertex $u$ (deleting all the edges incident to $u$ as well). $T \setminus uv$ denotes the forest obtained from $T$ by deleting the edge $uv$ (not deleting the vertices $u$ and $v$). For each $v \in V(T)$, $d_T(v) := \max_{u \in V(T) \setminus \{v\}} dist_T(u,v)$. We say $v \in V(T)$ is a center of $T$ if $d_T(v)$ attains its minimum over all vertices. The following are some easy facts about centers in a tree.

1) There are at most 2 centers in a tree.

2) If there are 2 centers $u$ and $v$, then $uv \in E(T)$. Moreover, every path of length $d_T(u)$ from $u$ passes $v$ and vise versa.

Now, here is our strategy. We are going to look at a minimal tree $T$ in the poset AFT. And we will choose special leaves $l_1$ and $l_2$ by certain methods, and use the fact that both $T \setminus l_1$ and $T \setminus l_2$ are not in AFT. From this, we will prove various properties of $T$. For instance, we will prove that $T$ must have two centers, and $T \setminus l_1$ must have exactly one center, and $T \setminus l_2$ must have two centers, etc. Eventually we will prove that $T$ must be isomorphic to $E_7$.

We first introduce the method of choosing a special leaf. Let $T$ be a tree with $|V(T)| \geq 2$, and let $u$ be a vertex in $T$. We are going to pick a leaf with respect to $u$ and $T$ as follows.

Consider all neighbors of $u$. Each one is in its own component $C_1,\cdots,C_k$ of $T \setminus u$. Among those components, we take one with the least number of vertices. (If there are more than one smallest components, just pick any one of those.) Let $C_1$ be the component we chose and let $w$ be the neighbor of $u$ in $C_1$. Now, look at all children of $w$ (the neighbors of $w$ except $u$). If there are no children of $w$, then we take $w$ as our special leaf. Otherwise we consider components $D_1,\cdots,D_m$ of $C_1 \setminus w$ and again, we pick the smallest component, and we move one step ahead. By this algorithm, we will end up with a leaf and we will take that leaf as our special leaf with respect to $u$ and $T$.

Theorem 1. Let $T$ be a minimal tree in the poset AFT. Then $T$ has exactly two centers.

Proof. For the sake of contradiction, suppose $T$ has a unique center $u$. Let $l_1$ be the special leaf with respect to $u$ and $T$ as described above.

Now, consider the tree $T' = T \setminus l_1$. In $T'$, $u$ is still a center because $d_{T'}(v)$ is either $d_{T}(v)$ or $d_{T}(v) - 1$ for every $v \in V(T) \setminus l_1$, and $d_T(u)$ used to be the unique minimum in $T$. (But there might be another center of $T'$.)

1) There is another center of $T'$.

Suppose $u$ is the unique center of $T'$. Let $\phi$ be a non-trivial automorphism in $T'$. Let $p(l_1)$ be the parent (the unique neighbor) of $l_1$ in $T$. Notice that $\phi$ does not fix $p(l_1)$ because otherwise we can extend $\phi$ to $T$ by assigning $\phi(l_1) = l_1$. On the other hand, $\phi$ fixes $u$ since it is the unique center of $T'$. Let $P$ be the path from $u$ to $p(l_1)$ in $T'$. Then, it is clear that $\phi$ fixes a sub-path $P'$ of $P$ containing $u$, and $\phi$ does not fix the other part of the path containing $p(l_1)$. Let $u'$ be the last vertex of $P'$. ($u'$ might be equal to $u$.) Then, $T' \setminus u'$ has (at least) two components which are isomorphic. And one of them must contain $p(l_1)$ since otherwise we can extend $\phi$ to $T$. Let $C_1$ and $C_2$ be those isomorphic components in $T' \setminus u'$ and say $p(l_1) \in C_1$. In particular $|C_1| = |C_2|$. But in $T$, $C_1 \cup l_1$ and $C_2$ are two components of $T \setminus u'$ and $|C_1 \cup l_1| > |C_2|$. This is a contradiction to our choice of $l_1$. This proves (1).

Let $v$ be the other center of $T'$. $u$ used to be the unique center of $T$, but now $u$ and $v$ are two centers in $T \setminus l_1$. Therefore it must be the case that $$d_{T'}(u) = d_T(u) = d_{T'}(v) = d_T(v) - 1$$

2) $l_1$ is not a neighbor of $u$.

Suppose $l_1$ is a child of $u$. Then, $d_{T'}(v) = d_T(v) - 1 = dist_T(v, l_1) - 1 = 1$. Therefore $T'$ has exactly two vertices $u$ and $v$. This is a contradiction to the fact that $T$ is in AFT. This proves (2).

3) $v$ is not in the component $C_1 \setminus l_1$ of $T' \setminus u$.

The path from $v$ to $l_1$ is the unique path of length $d_T(v)$ starting from $v$ in $T$. In particular, the path from $v$ to $p(l_1)$ is a path of length $d_T(v)-1 = d_{T'}(v)$. Recall that $u$ and $v$ are adjacent. Therefore if $v$ is in $C_1 \setminus l_1$, then the path from $v$ to $p(l_1)$ does not pass $u$. A contradiction. This proves (3).

4) $p(l_1)$ is a leaf in $T'$.

Suppose $p(l_1)$ has a child $w$ other than $l_1$ in $T$. Then, the path from $v$ to $w$ in $T'$ has length $d_{T'}(v)+1$ and this contradicts the definition of $d_{T'}$. This proves (4).

5) $\phi$ switches $u$ and $v$.

Notice that either $\phi$ fixes $u$ and $v$ or switches them since they are centers. But if $\phi$ fixes $u$, then by the same argument as in (1), we get a contradiction to our choice of $l_1$. This proves (5).

Let $T_u$ and $T_v$ be the two components of $T' \setminus uv$. ($T_u$ contains $u$ and $T_v$ contains $v$.) Since $\phi$ switches $u$ and $v$, $T_u$ and $T_v$ must be isomorphic. Note that $\phi$ does not fix any vertex. Recall that $p(l_1)$ is a leaf in $T_u$ from (4). Therefore $\phi(p(l_1))$ is also a leaf in $T_v$. Clearly it is a leaf in $T$ as well. Let $l_2 = \phi(p(l_1))$. (It is easy to see that this $l_2$ is actually the special leaf with respect to $v$ and $T$.)

We now consider $T'' = T \setminus l_2$.

6) $u$ is still a center of $T''$, but $v$ is not.

$u$ is still a center of $T''$ as it was in $T'$. But, $v$ is not a center of $T''$ since $d_{T''}(v) = dist_{T''}(v,l_1) = d_{T}(v) > d_{T}(u) \geq d_{T''}(u)$. This proves (6).

Again, there might be another center of $T''$. And if there is one, then it must be in $T_u$ since $v$ is not a center of $T''$.

Now consider a non-trivial automorphism $\phi'$ of $T''$.

7) $\phi'$ does not fix $v$.

For the sake of contradiction, suppose $\phi'$ fixes $v$. Then $u$ is fixed as well because $u$ is the unique center among the neighbors of $v$ (although $u$ might not be the unique center of $T''$.) By the similar argument as before, the parent of $l_2$ is not fixed by $\phi'$ and this yields a contradiction to the fact that $l_2$ is a special leaf with respect to $v$. This proves (7).

Clearly, $\phi'(v)$ is in $T_u$ since it is adjacent to a center of $T''$ and not equal to $v$. Then, there must be some component $C$ of $T'' \setminus u$ either isomorphic to $T_v \setminus l_2$ or contains it. In any case, $C$ has size at least $|T_v \setminus l_2|$. Let $n = |T_v|$.

8) $|C| = n$ or $n-1$.

$|C| \geq n-1$ since $\phi'(V(T_v) \setminus l_2) \subseteq C$. Recall that $|T_u| = |T_v|$ and $C$ is a subset of $V(T_u) \cup \{l_1\} \setminus \{u\}$. Therefore $|C| \leq |V(T_u) \cup \{l_1\} \setminus \{u\}| = n + 1 - 1 = n$. This proves (8).

9) The degree of $u$ is 2. In particular, $T''\setminus u$ consists of two isomorphic components, namely $C$ and $T_v \setminus l_2$.

Note that the union of all components of $T''\setminus u$ other than $T_v\setminus l_2$ has size $|V(T_u) \cup \{l_1\} \setminus \{u\}| = n$. Therefore if there is another component of $T'' \setminus u$ other than $C$ and $T_v\setminus l_2$, then it must be a single vertex. Therefore $u$ has degree either 2 or 3. If $u$ has degree 3, then it has a neighbor who has degree 1. Then this leaf must have been our choice $l_1$. But by (2), this is impossible. Therefore $u$ has exactly two neighbors. This proves (9).

Suppose there are some vertices of degree at least 3 in $C$. Now let $x$ be the shortest distance from $u$ to a vertex of degree at least 3 in $C$. And let $y$ be the shortest distance from $v$ to a vertex of degree at least 3 in $T_v$. Since $T_u$ and $T_v$ are isomorphic, $x = y$.

On the other hand, the shortest distance from $u$ to a vertex of degree at least 3 in $T_v$ is $y + 1$. Since $T_v \setminus l_2$ is isomorphic to $C$, the shortest distance from $u$ to a vertex of degree at least 3 in $C$ is $y+1$. Therefore $x = y+1$ and this is a contradiction.

Therefore no vertex has degree at least 3 in $C$. And this implies that $T$ is a path. And this is a contradiction to the fact that $T$ is in AFT. This proves Theorem 1.

Theorem 2. Let $T$ be a minimal tree in the poset AFT. Then $T$ is isomorphic to $E_7$

Proof. From Theorem 1, $T$ has two centers $u$ and $v$. Let $T_u$ and $T_v$ be the two sub-trees in $T \setminus uv$. ($T_u$ contains $u$ and $T_v$ contains $v$.)

Let $l_1$ be the special leaf with respect to $u$ and $T_u$ and let $l_2$ be the special leaf with respect to $v$ and $T_v$. Let $x$ be the shortest distance from $u$ to a vertex of degree at least 3 in $T_u$. (If there aren't any vertices of degree 3 in $T_u$, then $T_u$ is a path, and set this number $x$ as the length of the path.) Similarly, let $y$ be the shortest distance from $v$ to a vertex of degree at least 3 in $T_v$.

Without loss of generality, we may assume $|T_u| \leq |T_v|$. And further we may assume if $|T_u| = |T_v|$ then $x \leq y$ by switching $u$ and $v$ if necessary.

We first look at $T' = T \setminus l_2$.

1) $u$ and $v$ are still two centers of $T'$.

Note that every path of length $d_T(v)$ starting from $v$ passes $u$ in $T$. Therefore this path still exists in $T'$ since $l_2 \in T_v$. Therefore $d_{T'}(v) = d_T(v)$. This means that $u$ is still a center of $T'$.

Suppose $u$ is the unique center of $T'$. Let $\phi$ be a non-trivial automorphism of $T'$. Then, $\phi$ does not fix $v$ since otherwise we get a contradiction to our choice of $l_2$.

Then the component $T_v \setminus l_2$ of $T' \setminus u$ is isomorphic to some other component $C$ of $T' \setminus u$. Note that $$|C| = |T_v \setminus l_2| = |T_v| - 1$$ Since $C$ is a subset of $V(T_u) \setminus \{u\}$, $$|T_u| \geq |C| + 1 = |T_v|$$ Therefore $|T_u| = |T_v|$. And $T' \setminus u$ has exactly two components, namely $C$ and $T_v \setminus l_2$. We may assume there is a vertex of degree at least 3 in $T_v \setminus l_2$, since otherwise $T$ is a path. But then, $x \geq y+1$ and this is a contradiction to our assumption ($x \leq y$ if $|T_u| = |T_v|$). Therefore $u$ is not the unique center of $T'$. This means that $d_{T'}(u) = d_T(u)$ and $v$ is still a center as well. This proves (1).

2) $\phi$ switches $u$ and $v$. And $|T_u| = |T_v| -1$.

Again, if $\phi$ fixes $v$, then $\phi$ fixes $u$ as well and we get a contradiction to our choice of $l_2$. Since $\phi$ switches $u$ and $v$, $T_u$ and $T_v \setminus l_2$ are isomorphic. In particular, $|T_u| = |T_v| - 1$. This proves (2).

Now we consider $T'' = T \setminus l_1$. Let $\phi'$ be a non-trivial automorphism of $T''$.

3) $\phi'$ does not fix $u$. And $v$ is the unique center of $T''$.

Again, every path of length $d_T(u)$ starting from $u$ passes $v$ in $T$. Therefore this path still exists in $T''$ since $l_1 \in T_u$. Therefore $d_{T'}(u) = d_T(u)$. This means that $v$ is still a center of $T''$.

Note that either $d_{T'}(v) = d_T(v)-1$ or $d_{T'}(v) = d_T(v)$. In the former case, $v$ is the unique center of $T''$, and in the latter case, $u$ and $v$ are again two centers of $T''$. Therefore if there is another center, then it must be $u$.

Suppose $\phi'$ fixes $u$. Then, again $v$ is fixed as well and we get a contradiction to the choice of $l_1$. Therefore $\phi'$ does not fix $u$.

For the sake of contradiction, suppose $u$ is another center of $T''$. Since $\phi'$ does not fix $u$, it switches $u$ and $v$. Then, $T_u \setminus l_1$ is isomorphic to $T_v$, but $|T_u \setminus l_1| = |T_u| - 1 = |T_v| - 2 \neq |T_v|$. A contradiction. This proves (3).

Since $v$ is the unique center of $T''$ and $\phi'$ does not fix $u$, the component $T_u \setminus l_1$ of $T'' \setminus v$ is isomorphic to another component $C$ of $T'' \setminus v$.

Note that the union of all components of $T''\setminus v$ other than $T_u \setminus l_1$ is exactly $T_v \setminus v$. And $C$ has size $|T_u| - 1 = |T_v| - 2$. This means that there are exactly three components of $T''\setminus v$, namely $T_u \setminus l_1$, $C$, and the third one with a single vertex. Therefore $v$ has a neighbor of degree 1, and this must have been our choice $l_2$.

Now suppose there is a vertex of degree at least 3 in $T_u$. Then there is one in $T_v$ as well. And by the usual argument, $x=y$ and $x+1 = y$ at the same time. A contradiction. Therefore $T_u$ must be a path of length $|T_u|$ and $T_v$ must be a path of length $|T_v| = |T_u| + 1$.

Then, $T$ is a tree with a unique vertex of degree 3, namely $v$, and $T \setminus v$ has three components. One of them is a single vertex, namely $l_2$, and the other two components are paths of length $k$ and $k+1$.

For every $k > 2$, $T$ is not minimal since deleting $l_1$ from $T$ yields a smaller tree $T''$ in AFT. Therefore $k$ must be 2. This proves that $T$ must be isomorphic to $E_7$.

$\endgroup$
7
  • 2
    $\begingroup$ You might as well keep this answer, and instead add to it in a few days' time a link to your proof, when it is ready. When you edit this answer, it will show up again on the front page, so that people will be aware. $\endgroup$
    – Todd Trimble
    Jan 14, 2013 at 23:00
  • 1
    $\begingroup$ Wow. On my first read through, everything in here looks reasonable and believable. I will continue thinking about it to make sure I understand it all before accepting, but it looks good so far. $\endgroup$
    – ARupinski
    Jan 16, 2013 at 23:04
  • $\begingroup$ @ARupinski : Thanks. Please let me know if there is something unclear. By the way, could you tell us some references or motivations of this problem? $\endgroup$
    – Ilhee Kim
    Jan 18, 2013 at 23:32
  • $\begingroup$ I dont have any particular references. As far as motivation, I was thinking about some problems related to antichains in posets and was tired of thinking about some common examples such as $\mathbb{N}$ and the poset of Young Diagrams of partitions, so I was trying to come up with a more complicated poset to think about in context (and it seems I did; while $\mathbb{N}$ and the set of Young Diagrams each obviously have a unique minimal element, proving this is also true in $\mathcal{AFT}$ is apparently much more difficult) $\endgroup$
    – ARupinski
    Jan 19, 2013 at 0:03
  • 1
    $\begingroup$ Their paper is now on the arxiv: arxiv.org/abs/1303.1551 $\endgroup$ Mar 9, 2013 at 4:51
7
$\begingroup$

[edit 01.15.2013] The following proof is still incomplete, but the main ideas should be useful.

[edit 01.17.2013] I filled the lacking point in the case 2, small but subtle, completing the proof, so I wrote it (even if in the meanwhile a complete proof has been posted).

Let me start with some general notions, that I believe are known, for a tree $T=(V,E)$ with finite, nonempty vertex set $V$ and edge set $E$. I will assume that $T$ is a minimal element of $\mathcal{AFT}$ only in the end.

For a path of length $n$ (number of edges) , $ (v_0 \dots v_n) $ in $ T $, let's define the centre of the path as the set $ \big\{v _ {\lfloor\frac{n }{2}\rfloor},v _ {\lceil \frac{n }{2}\\rceil } \big\}$, consisting of one or two vertices (thus, either the middle vertex, if $n$ is even, or the middle edge, if $n$ is odd). Given two paths, there is a third path including the centres of both, and one endpoint of each. As a consequence, all paths of maximum length in a tree share the same centre, that we can therefore refer to as centre of the tree, $C(T):=\{v,v'\}$ (so this notation allows that $C(T)=\{v\}=\{v'\}$, a singleton, precisely whenever the diameter of $T$ is an even number, as remarked).

Since the image of a maximum length path via an automorphism of $T$ is still a maximum length path, whose center is the image of the center of the path, the set $C(T)$ is invariant for any automorphism $f$ of $T$ (thus, it is either a fixed point, or a couple of fixed points , or a 2-periodic orbit of $f$).

The centre determines a natural genealogy order in $T$; in particular, we can attach to any vertex $v$ its progeny, $\Gamma(v,T)$, the set of all vertices $x$ such that the minimal path from $x$ to the centre passes by $v$. Thus, e.g. this reduces to $\{v\}$ if and only is $v$ is a leaf; if $ C(T)$ is a singleton $\{v\}$, $\Gamma(v,T)$ is the whole vertex set $V$; if $ C(T)$ is an edge $vv'$, $\Gamma(v,T)$ and $\Gamma(v',T)$ are the components of $(V, E\setminus\{C(T)\}$.

For a vertex $x$, denote $( x^0 \dots x^n )$ the unique minimal path in $ T $ connecting $x$ to the center: $x^0\in C(T)$, $x^n=x$; here $n$ is the path distance from $C(T)$. It is also convenient to consider the nested sequence $ \Gamma(x^i,T) $, and the vector $\gamma(x,T):=(\gamma_0,\dots,\gamma_n)\in\mathbb{N}^{n+1}$ whose $i$-th entry is the cardinality $\gamma_i:=|\Gamma (x^i,T)|$ of each of these sets. Note that, since the center of a tree is automorphism-invariant, any automorphism of $T$ satisfy $\gamma(f(x),T)=\gamma(x,T)$. Among all leaves, consider those with minimum $\gamma(x,T)$ in the lexicographic order (with leading coefficient $\gamma_0$ ); we may shortly call them minimal leaves. For instance, the three leaves of the tree $E_7$ have labels $(3,2,1)$, $(4,1)$, and $(4,3,1)$, in increasing lexicographic order.

Let $x$ be a leaf of $T$, with father $x'=x^{n-1}$. We may denote $ T_x:=(V_x,E_x)$ the tree obtained deleting the leaf $x$ and the edge $xx'$. For a minimal leaf $x$ we may distinguish the following alternative:

1. $\mathrm{diam}(T_x)=\mathrm{diam}(T)$. This means that $T$ and $T_x$ share a maximum length path, so they also have the same center. Thus, for any $v\in V_x$ we have $\Gamma(v,T_x)=\Gamma(v,T)\setminus\{x\}$, and in particular the entries of $\gamma(x',T_x)$ are simply $\gamma_i(x',T_x) = \gamma_i(x,T) -1$ for $i=0,\dots,n-1$. As a consequence, any automorphism $f$ of $T_x$ fixes the whole path connecting $x'$ to $C(T_x)=C(T)$ (this follows by induction on $i$, arguing on the cardinality of the connected components $\Gamma (x^i,T_x)$: now $\Gamma (x^0,T_x)$ has strictly minimum cardinality among the components of $(V_x, E_x\setminus \{C(T)\})$, so $f(\Gamma (x^0,T_x))=\Gamma(x^0,T_x)$ and $x^0$ is fixed; then $x^1$ is fixed because $\Gamma(x^1,T_x)$ has strictly minimum cardinality among the components of the sons of $x^0$ in $\Gamma (x^0,T_x)$, and so on ). Therefore, $f$ extends to an automorphism of $T$ that fixes $x$. Clearly, this is not the case if $T$ is a minimal element of $\mathcal{AFT}$.

2. $\mathrm{diam}(T_x)=\mathrm{diam}(T)-1$. This means that $x$ is an end of every maximal length path of $T$.

Now, assume $T$ is a minimal element in $\mathcal{AFT}$, so that we are in case 2. Then, $C(T)$ is an edge, i.e. $\mathrm{diam}(T)$ is an odd number $2n+1$, and no vertex of the minimal path $(x^0,\dots, x^{n})$ connecting $x$ to $C(T)$ is a branching point. Proof: consider first the case of odd diameter of $T$, where $C(T)$ is an edge. Assume by contradiction that $\Gamma(x^0, T)$ is not a single path. Then, there are in it leaves $y\neq x$. Take among them the one with minimum vector $\gamma(y,T)$ in the lexicographic order. Now, since $y\neq x$, we have $\mathrm{diam}(T_y)=\mathrm{diam}(T)$, and we can argue with $y$ like in the previous case 1. The automorphism $f_y$ of $T_y$ fixes all $x^i$ because $( f_y(x^0),\dots,f_y(x^n) )$ are an end of a maximum lenght path in $T$, so they must end at $x$, which implies $f_y(x^i)=x^i$ for $0\le i \le n$. But then, $f_y$ also fixes the path $y^i$, for the same inductive argument used in point $1$ (start with the greater index $j$ such that $x^j=y^j$ and proceed looking at the cardinality of $\Gamma(y^{j+1} , T_y)$, observing that $f_ y (y ^ {j+1} ) \neq x^{j+1} =f_y(x^{j+1} ) $ because $ y^{j+1} \neq x^{i+1}$. This is a contradiction as usual, because $f_y$ does not fix the father of $y$, as already observed. For an analog reason, the case $C(T)$ is a vertex implies that $\Gamma(x,T)$, that is the whole $T$, has no branching vertices, that is, it is a path, which however is impossible because $T$ has no nontrivial automorphism.

Conclusion of the proof: Since $(x^0,\dots, x^{n-1})$ is part of a maximum length path in $T_x$, and $ \mathrm{diam}(T_x)=2n $ is even, the center of $T_x$ is a single vertex, namely the other endpoint $y^0$ of $C(T):=\{x^0,y^0\}$. If $f_x$ denote the unique nontrivial automorphism of $T_x$, we know that $f_x(y_0)=y_0$ (it's the center of $T_x$), while $y:=f_x(x^{n-1})\neq x^{n-1} $ (otherwise $f_x$ would extend to $T$). Therefore, $ (y^0, f_x(x^0),f_x(x^1),\dots,f_x(x^{n-1}))$ is the $n$-edges path connecting $y$ to $C(T)$, and since the $x^i$ for $i\ge0$ are not branching points, this path has no branching points too, with the possible exception of $y^0$. Actually, $y^0$ must be a branching point, otherwise the path $\xi:=(x^n,x^{n-1},\dots,x^0,y^0,y^1,\dots y^n)$, which has maximal length $2n+1$ in $T$, would have no branching point at all, and therefore would be $T$ itself, what however is impossible because $T$ has no nontrivial automorphism.

Next, we may consider the automorphism $f_y$ of $T_y$. As to $C(T_y)$, it is either $\{x^0\}$ (if $\xi$ is the unique maximum length path of $T$ and $ \mathrm{diam}(T_y)=2n $) , or $C(T_y)=C(T)$, (if there are other maximum length paths in $T$ and $ \mathrm{diam}(T_y)=2n+1 $). Therefore $f_y(y_0)$ is either $x^0$, or $x^1$, or $y^0$; however, only the last case is possible, because $y_0$ is a branching points and $x^0$, or $x^1$ are not. Thus, $( f_y(y^0), f_y(y^1),\dots, f_ y(y^{n-1}))$ is a path of length $n-1$ , starting from the branching point $y^0=f_ y(y^0)$, without other branching points. For the same reason, $T$ must contain a family of paths emanating from $y^0$, with no branching points, of all lengths between $1$ and $n$; in particular, a leaf $z$ attached to $y^0$ (and possibly other matter). The unique involution $f$ of $T_z$ exchanges the endpoints of $C(T_z)=C(T)$ (otherwise it would be extensible to a nontrivial automorphism of $T$), therefore bijects the whole $\Gamma(x^0, T)=\Gamma(x^0, T_z)$ with $\Gamma(y^0, T_z)$. This proves that $n=2$ and $T$ is $E_7$.

$\endgroup$
16
  • $\begingroup$ warning: there is a gap in part 1, since T\C may have non trivial automorphisms, so that it may fail to be in RATF. I think the proof could be fixed, so I will not delete it for the moment. $\endgroup$ Dec 25, 2012 at 20:51
  • $\begingroup$ IMHO the claim of 1 looks very plausible. So it's matter of fixing the proof there. In 2, the reduction to an involutory automorphism of T\{x} looks incomplete - what's wrong about freezing a part of T? Otherwise, very interesting! $\endgroup$ Dec 26, 2012 at 5:19
  • $\begingroup$ Yes, sorry for the mess. The idea is that for a minimal object T (both in the case of AFT and of AFRT) and a leaf x, any nontrivial automorphism ϕ of T\{x} must have some special properties, otherwise one can use it to make a nontrivial automorphism ψ of T. For instance, it can't fix the father of x, and can't have certain invariant sets. Also, ϕ is unique, and it is an involution. I'll try to state these small bricks more clearly. $\endgroup$ Dec 26, 2012 at 11:25
  • $\begingroup$ An useful lemma should be the following. If a tree S has a vertex y which is fixed by no nontrivial automorphism of S, then S has at most one nontrivial automorphism (which is necessarily an involution). It holds both in the rooted and unrooted case. Do you agree? The proof is not difficult (in case I'll write it down). This applies to S:=T\{x}, T :=a minimal tree (either in the rooted or unrooted case) and x := a leaf of T; y:= the father of the leaf x. $\endgroup$ Dec 26, 2012 at 16:24
  • $\begingroup$ @Pietro: thanks for the answer... I am digesting the details now, but so far everything seems to fit nicely. $\endgroup$
    – ARupinski
    Dec 26, 2012 at 23:57

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.