I was studying the Luks algorithm and in the chapter for Trivalent Graphs I did not understand on the why the elements $\sigma \in K_{r}$ stabilizes all of the elements of $X_{r}$ and the conclusion that $K_{r}$ is precisely the elementary abelian 2-group generated by the transpositions in each pair of twins and $|Aut_{e}(X_{r+1})| = |Image(\Pi_{r})| \cdot |K_{r}|$.
Luks began with a trivalent graph $X$ with $|V(X)| = n$ and we want to determine the $Aut_{e}(X)$ (automorphism with a fixed edge $e$) by a sequence of what he calls "approximations". He breaks the graph in subgraphs $X_{r}$ of $X$ where all vertices and edges of $X_{r}$ appear in some path of length of size $r$ or less through the edge $e$.
We have that $X_{1}$ is just $e$ and $X_{n-1}$ is exactly the original graph $X$. Then, he built the induced homomorphism $\pi_{r} : Aut_{e}(X_{r+1}) \rightarrow Aut_{e}(X_{r})$ and assumed that $Aut_{e}(X_{r})$ is already known. Then, the determination of $Aut_{e}(X_{r+1})$ is broken up into two problems:
- Find a set $\Re$ of generators for the kernel $K_{r}$ of $\pi_{r}$;
- Find a set $\Im$ of generators for $\pi_{r}(Aut(X_{r+1})) = Image(\pi_{r})$.
Then, we can build the generators of $Aut_{e}(X_{r+1})$ with $\Re \cup \Im'$, where $\Im'$ is the pullback of the set $\Im$. He then claims that "...if $\sigma \in K_{r}$, (i.e. fixes all elements of $X_{r}$) then $f(v) = f(\sigma(v))$; so eiher $v = \sigma(v)$ or $v$ and $\sigma(v)$ are twins. It follows that $K_{r}$ is precisely the elementary abelian 2-group generated by the transpositions in each pair of twins." and that $|Aut_{e}(X_{r+1})| = |Image(\Pi_{r})| \cdot |K_{r}|$.
I cannot see how $K_{r}$ is a stabilizer of $X_{r}$ and that he is the elementary abelian 2-group. And why the order of $|Aut_{e}(X_{r+1})|$ is not just a sum of the order of the two sets.
Well, $K_r$ is the set of automorphisms of $X_{r+1}$ that, when restricted to $X_r,$ are trivial. This is the definition of kernel.
The stabilizer of $S$ is the set of group elements who fix some set pointwise, and indeed this is the case for $K_r.$
I suggest drawing a tree of some constant depth, and calling $X_r$ the set of non-leaf nodes, so that $X_{r+1}$ is the whole tree. Now, we have a lot of automorphisms of this tree fixing $X_r:$ namely one for every pair of leafs with the same parent, given by fixing all the vertices except those 2 leafs, which get swapped (btw, note your tree can't have triplets. Why?). Label the leafs, and then redraw the graph after various sequences of twin swaps. You'll see the action commutes, and that you can choose to swap or not swap every twin (giving you much more than |twins| possible actions).
Anyway, if 2 vertecies have the same neighbors, we can swap them while still fixing everything in $X_r.$ There's a nice diagram of the cases in the paper. Since all these actions are on distinct nodes, they can be done in any order, so the group is abelian. Since it's generated by operations that have order 2 (the twin swap returns both twins to the same place if we do it twice), every element in the group has order $2.$
Finally, the size estimate is a classic result. It's essentially linear algebra: you have a choice of actions that do actually change some subset (In this case $Img(\pi)$ acts on $X_r \subset X_{r+1}$) followed by a choice of an action which does nothing to that set (but might act elsewhere) ($K_r$). It's not too bad to convince oneself that these are independent choices.