Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 1 down vote accepted

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


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:


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

share|cite|improve this answer

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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.