Normalizers of automorphism groups

In abstract groups $\Gamma$ the normalizer $N_\Gamma(S)$ of a subset $S\subseteq\Gamma$ is the subgroup of all $x \in \Gamma$ that commute with $S$, i.e. $xS = Sx$, i.e. $x\ y\ x^{-1} \in S $ for all $y \in S$.

Among the permutations $S_n$ of the vertices of a graph $G$ of order $n$ (or any other kind of structure) there is one distinguished subgroup: the automorphisms $\text{Aut}(G)$, that reflect the symmetries of $G$:

$$\alpha \in \text{Aut}(G)\quad \Leftrightarrow \quad \alpha G = G$$

To give $\alpha G = G$ a proper meaning, identify $G$ with an adjacency matrix, for example.

The normalizer of $\text{Aut}(G)$ is another distinguished subgroup: it consists of those permutations $\pi$ of the vertices, such that $\text{Aut}(\pi G) = \text{Aut}(G)$, i.e. that respect the symmetries of $G$, as can be shown like this:

$\quad \pi \in N_{S_n}(\text{Aut}(G))\\ \Leftrightarrow \pi^{-1}\alpha\ \pi \in \text{Aut}(G)\ \text{for all}\ \alpha \in \text{Aut}(G)\\ \Leftrightarrow \pi^{-1}\alpha\ \pi\ G = G\ \text{for all}\ \alpha \in \text{Aut}(G)\\ \Leftrightarrow \alpha\ \pi\ G = \pi\ G\ \text{for all}\ \alpha \in \text{Aut}(G)\\ \Leftrightarrow\alpha \in \text{Aut}(\pi G)\ \text{for all}\ \alpha \in \text{Aut}(G) $

Note that $\text{Aut}(\pi G)$ and $ \text{Aut}(G)$ are of course isomorphic for every $\pi \in S_n$:

$$\text{Aut}(\pi G) \simeq \text{Aut}(G)$$

but this is not the matter of concern. The matter of concern is

$$\text{Aut}(\pi G) = \text{Aut}(G)$$

My first question now is:

Does the normalizer of the automorphisms of a structure has an established name on its own?

Something like symmetry preserving rearrangements (compared to adjaceny preserving rearrangements [what automorphisms are] or structure preserving rearrangements [what general permuations - of labels - are])? Note, that and how the following permutation is (i) symmetry preserving and (ii) an element of the normalizer of $\text{Aut}(G)$ and that (iii) most other permuations are not:

Where is the normalizer of the automorphisms of a structure investigated in its own right - or plays an explicit role, e.g. in a theorem?

More specific:

How can the normalizer of the automorphisms of a structure be defined/characterized without reference to (and prior definition of) the latter?

Solution 1:

Some background first.

Given a (left) action of a group $S$ on a set $\Gamma$, we call $\Gamma$ a $S$-set. A morphism of $S$-sets $\phi:\Gamma\to\Lambda$ is a function such that $\phi(s\gamma)=s\phi(\gamma)$ for all $s\in S$ and $\gamma\in\Gamma$. In this way, the class of all $S$-sets becomes a category.

If $A\le S$ is a subgroup, then the left coset space $S/A$ is canonically an $S$-set, with action given by left multiplication, i.e. $\sigma(sA)=(\sigma s)A$ (meaning $\sigma$ sends $sA$ to $(\sigma s)A$).

If $\Gamma$ is a transitive $S$-set, meaning for all $\gamma_1,\gamma_2\in\Gamma$ there exists a $s\in S$ such that $s\gamma_1=\gamma_2$, and we have an element $\gamma\in\Gamma$ with point-stabilizer $A=\mathrm{Stab}_S(\gamma)$, then the map $S/A\to\Gamma$ given by $sA\mapsto s\gamma$ is well-defined, is a bijection, and is a morphism of $S$-sets. In other words, $\Gamma\cong S/A$ are isomorphic in the category of $S$-sets. (This is essentially a categorified version of the orbit-stabilizer theorem, which is usually just a numerical equality of cardinalities.)

The automorphism group $\mathrm{Aut}(\Gamma)$ of $\Gamma$ in the category of $S$-sets (i.e. the group of $S$-equivariant bijections $\Gamma\to\Gamma$) will be a direct product of wreath products of automorphism groups of orbits, so without loss of generality we would want to compute $\mathrm{Aut}(\Gamma)$ when $\Gamma=S/A$ is an orbit.

Suppose $\phi:S/A\to S/A$ is $S$-equivariant. Pick $\tau$ with $\phi(A)=\tau A$, then since $aA=A$ or all $a\in A$ we need $a\phi(A)=\phi(A)$ or in other words $a\tau A=\tau A$ for all $a\in A$, which is equivalent to $\tau\in N_S(A)$. Conversely, if $\tau\in N_S(A)$ then $\tau A=A\tau$ so really $\phi(sA)=sA\tau$ is just right-multiplication-by-$\tau$, which is evidently commutes with the left $S$-action.

However, there is some redundancy. Every $\tau\in N_S(A)$ defines an automorphism of $\Gamma$, but different elements $\tau\ne \tau'$ may define the same automorphism. The map $N_S(A)\to\mathrm{Aut}_S(S/A)$ can, however, be conceived of as a group homomorphism, where $\tau\mapsto R_{\tau^{-1}}$ with $R_{\tau^{-1}}(sA)=sA\tau^{-1}$ (we need to use $\tau^{-1}$ in order for $R_{\tau \tau'}=R_\tau\circ R_{\tau'}$). The kernel of $N_S(A)\to\mathrm{Aut}_S(S/A)$ is easily seen to be $A$ itself, so we conclude $\mathrm{Aut}_S(S/A)\cong N_S(A)/A$.

If we want to realize all of $N_S(A)$ as a symmetry group, instead of $N_S(A)/A$, we need to equip $\Gamma=S/A$ with more than just an $S$-action. We need to make it a groupoid.

A groupoid is, in one definition, a category with only isomorphisms. More concretely, a groupoid is a set of states and a set of transitions between states that can be composed. For example, the fifteen puzzle has many different configurations of pieces on the board, and many ways of transitioning between different states (a transition is a sequence of shifts of pieces) which can be composed together. The same goes for the Rubik's cube toy.

There is something special about the Rubik's cube's associated groupoid: it is an action groupoid. To understand this, first forget the colors on the cube (so it's entirely gray, say), and take its symmetry group $S$ of layer rotations and have it act on the set of states of the Rubik's cube.

Formally, if $S$ acts on $\Gamma$, the action groupoid $\Gamma/\!/S$ has $\Gamma$ as its set of states, and one transition $\gamma_1\to\gamma_2$ for every $s\in S$ with $s\gamma_1=\gamma_2$, which we can write as ordered triples $(s,\gamma,s\gamma)$. We can depict this with a Cayley graph: think of $\Gamma$ as a bunch of vertices, and draw an arrow $\gamma\to s\gamma$ labelled by $s$ for all $\gamma\in\Gamma,s\in S$.

Composing transitions $\gamma_1\xrightarrow{s}\gamma_2$ and $\gamma_2\xrightarrow{s'}\gamma_3$ gives $\gamma_1\xrightarrow{s's}\gamma_3$.

Note that $S$ canonically acts by groupoid automorphisms of $\Gamma/\!/S$. Applying $s'$ sends state $\gamma$ to state $s\gamma$ and sends transition $\gamma_1\xrightarrow{s'}\gamma_2$ to transition $s\gamma_2\xrightarrow{ss's^{-1}}s\gamma_2$. This identifies $S$ with a subgroup of $\mathrm{Aut}_{\mathrm{Gpd}}(\Gamma/\!/S)$

Exercise. The group of groupoid automorphisms of $\Gamma/\!/S$ that intertwine with the $S$-action is isomorphic to the normalizer $N_S(A)$, where $\Gamma=S/A$.

(Note that it will not be the same subset as $N_S(A)\subseteq S\subset\mathrm{Aut}_{\mathrm{Gpd}}(\Gamma/\!/S)$.)

Now let's relate this to graphs. Actually, we can do this with any kind of labelled combinatorial structure on a finite set. Formally, a combinatorial species is an endofunctor of the category of finite sets with bijections. For example, on a finite set $V$, we can build labelled graphs on $V$, labelled trees, partial orderings, lattice orderings, linear orderings, permutations, permutations with a certain cycle structure, set partitions, set partitions with specified block sizes, $k$-subsets for some whole number $k$, power sets, power sets of power sets, and so forth.

The fact that a species $F$ is a functor means any "label exchange" $\pi:V\to W$ (we think of $V$ and $W$ as a set of labels we can slap onto some combinatorial structure, and grocers frequently exchange one set of labels with another if, for instance, a sale takes place) induces a function $F(\pi):FV\to FW$ between combinatorial structures.

For example, if $F$ is the species of graphs, then this has the following interpretation in semi-colloquial language. Graph with labels from $V$ can be turned into graphs with labels from $W$, because $\pi$ exchanges labels from $V$ for labels from $W$, and this induces a map from the collection $FV$ of graphs with labels from $V$ to the collection $FW$ of graphs with labels from $FW$.

In particular, if $V=W$, then $\pi\in S_V$ induces a $F(\pi)\in S_{FV}$. That is, we have a group homomorphism $S_V\to S_{FV}$, which can be interpreted as an action of $S_V$ on the collection of all $F$-structures on $V$. The orbits are the isomorphic $S_V$-structures, and the relabellings $\pi\in S_V$ provide the isomorphisms between isomorphic $F$-structures.

Suppose we work again with the species $F$ of graphs. A graph on $V$ can be formalized as a collection of edges $E$, or in other words a collection of $2$-subsets (unordered pairs). (This means that $FV=\mathcal{P}(\binom{V}{2})$ is a composition of the power set species with the $2$-subsets species.) The collection $\Gamma$ of all graphs on $V$ isomorphic to a given one with edge set $E$ is an orbit under the action of $S_V$, and the automorphism group $A$ of the particular graph is stabilizer of $E\in\Gamma$.

Now $S=S_V$ acts by groupoid automorphisms of the action groupoid $\Gamma/\!/S$, and the groupoid symmetries that commute with the $V$-relabelling action is $N_S(A)$.

Exercise. Draw all cycle graphs on four given points in the plane labelled $1,2,3,4$. (You should get three: a quadrilateral and two hourglass figures.) Draw arrows between these cycle graphs and label then with the permutations in $S_4$ to get the action groupoid. (You should have $24$ arrows total, with four from each figure to itself.) The fact that the automorphism group $V_4$ is normal in $S_4$ corresponds to the fact all permutations give relabelling-intertwining groupoid symmetries.

We can do this with directed graphs too.

Exercise. Do the same as the previous exercise, but with three points and directed cycle graphs.

Exercise. Do the same with rooted ternary trees on four points.