2
$\begingroup$

I am reading "Algebraic Graph Theory" by Norman Biggs (1974), and I have problem understanding the following definition and proposition.

We define a stabilizer sequence as follows:

A stabilizer sequence of the $t$-arc $(a_0,a_1,\ldots,a_t)$ in a graph $X$ is the sequence $Aut, F_t, F_{t-1},\ldots,F_1,F_0$ of subgroups of $Aut(X)$, where $F_i \; (0 \leq i \leq t)$ is defined to be the pointwise stabilizer of the set $\{a_0,a_1,\ldots,a_{t-i}\}$.

I understand that a stabilizer sequence is a sequence of subgroups, where each element in the sequence fixes some set of vertices in the graph $X$, and each element in the sequence fixes more than the previous.

Now the following is stated, without a proof:

Since $Aut(X)$ is transitive of $s$-arcs $(1 \leq s \leq t)$ it follows that all stabilizer sequences of $t$-arcs are conjugate in $Aut(X)$.

I also know the definition and (and at least some of) the intuition behind conjugacy, but I do not see why these sequences of stabilizers, are conjugate.

If some definition is missing, or more information about the general setting is needed, there might be information in another question I have asked earlier: Proof about cubic $t$-transitive graphs.

2 Answers 2

1

This can be seen as a realization of some fundamental conceptual facts of stabilizer subgroups.

Let $Y$ be a set equipped with a transitive $G$-action. Given a $g\in G$, applying $g$ to all of $Y$ creates a bijection $Y\to Y$ and hence can be seen as a change of perspective, in the same way an invertible linear transformation creates a change of basis for a vector space. If $\sigma y=y$ for $\sigma\in G,y\in Y$, then we can write $(g\sigma g^{-1})gy=gy$; conversely if $\tau gy=gy$ we may write $(g^{-1}\tau g)y=y$. Notice that the maps $\sigma\mapsto g\sigma g^{-1}$ and $\tau\mapsto g^{-1}\tau g$ are automorphisms of $G$ and are inverses of each other. This establishes an isomorphism of stabilizer subgroups $G_{gy}=gG_y\,g^{-1}.$ An easy way to remember this is to rewrite $G_y y=y$ as $(g G_y g^{-1})gy=gy$.

Since the $G$-action is transitive, for any two $x,y\in Y$ we may write $y=gx$ for some $g\in G$, and hence the stabilizer subgroups $G_x$ and $G_y$ are conjugate to each other.

Now suppose further that the $G$-action is $n$-transitive, that is, for any two sequences

$x=(x_1,\cdots,x_n),y=(y_1,\cdots,y_n)\in Y\times Y\times\cdots \times Y=Y^n,$

there exists a $g\in G$ such that $y=gx$, i.e. $y_i=gx_i$ for $i=1,2,\cdots,n$. In particular, an $n$-transitive action is also $m$-transitive for each $m=1,2,\cdots,n$, and we may write

$(y_1,\cdots,y_m)=g(x_1,\cdots,x_m)$

for each $1\le m\le n$. Thus, for the $G$-action induced on $Y^m$, $G_{\large(y_1,\cdots,y_m)}=gG_{\large(x_1,\cdots,x_m)}g^{-1}$ for each $m$. Notice the conjugation $\sigma\mapsto g\sigma g^{-1}$ is the same for each stabilizer subgroup, so if desired we could write this fact as a conjugation applied (component-wise) to descending series of stabilizers:

$\left(G_{\large(y_1)},G_{\large(y_1,y_2)},\cdots,G_{\large(y_1,\cdots,y_n)}\right)=g\left(G_{\large(x_1)},G_{\large(x_1,x_2)},\cdots,G_{\large(x_1,\cdots,x_n)}\right)g^{-1}.$

These facts apply to your case with $Y=X$ the graph, $n$-tuples as arcs and $G=\mathrm{Aut}(X)$.

1

Let $x,y \in Aut(X)$, now $x$ and $y$ are conjugate if $\exists g \in Aut(X): gxg^{-1} = y$. Now the statement that all stabilizer sequences of $t$-arcs are conjugate in $Aut(X)$ can be shown in the following way.

Let $S_a = Aut,F_t^a,F_{t-1}^a,\ldots,F_{1}^a,F_{0}^a$ be the stabilizer sequence of the $t$-arc $a$, and let $b$ be another $t$-arc. Now we want to show that we can find an automorphism $g \in Aut(X)$, such that $gS_ag^{-1}$ is a stabilizer sequence of $b$.

Since $Aut(X)$ is $t$-transitive, there exists an automorphism $g$ taking $a$ to $b$. An element $F_i^a \in S_a$ is the subgroup of $Aut(X)$ stabilizing the first $(t-i)$ elements of $a$, that is $\{a_0,a_1,\ldots,a_{t-i}\}$. Now we show that $g F_j^a g^{-1}$ stabilizes the $t$-arc $\{b_0,b_1,\ldots,b_{t-j}\}$.

$g F_j^a g^{-1}(b_l) = g F_j^a (a_l) = g(a_l) = b_l \;\;\; 0 \leq l \leq (t-j)$

thus the sequence $gS_bg^{-1} = gAut(X)g^{-1}, g F_t^a g^{-1},g F_{t-1}^a g^{-1},\ldots,g F_{0}^a g^{-1}$ is a stabilizer sequence of $b$.