How to think about orbits and stabilizers

Question

I'm trying to grasp the notion of orbits and stabilizers. I have two questions:

1. If we look at the picture below, how can we determine $|G(2 \to 6)|$ and $|{G_2}|$ given the following definitions:

$$ \begin{gathered} G(x \to y) = \{ g \in G|g(x) = y\} \hfill \\ {G_x} = G(x \to x) \hfill \\ \end{gathered} $$

2. Why is $\{1,3,5\}$ an orbit, but not $\{1,2,3\}$?

Answer 1

The orbits and stabilizers depend on the group of symmetries under consideration. In this case that group seems to be the symmetries of the hexagon that preserve the inscribed triangle.

That answers your second question: you can move $1$ to $3$ and $5$ but not to $2$.

For the first question, look for the symmetries that move $2$ to $6$, then look for the symmetries that fix a vertex (the identity will always work but there may be more}.

Answer 2

You need to specify the group that's acting on this set. Based on the second question:

Why is $\{1,3,5\}$ an orbit, but not $\{1,2,3\}$?

I'm guessing the symmetry group of a triangle is acting on the triangle with vertices at $1$, $3$, and $5$ (and by extension is acting on the entire hexagon by preserving the relative positions of the points w.r.t. the triangle). If this is indeed the case, we cannot have $\{1, 2, 3\}$ as an orbit since sending the vertex labeled "$1$" to the point labeled "$2$" cannot preserve the triangle to which vertex "$1$" belongs. In other words, the triangle post-symmetry movement needs to be in the exact same orientation as the original triangle (ignoring labeled vertices).

---

To tackle the first question, first recall that every element in the symmetry group of a triangle is some combination of a chosen flip $F$ and a $120^\circ$ clockwise rotation $R$. You can check that $F$ and $R$ anticommute in the sense that $FR = R^{-1}F$. Armed with this knowledge, you can write down $6$ unique triangle-preserving isometries: $\{R^kF^j \ | \ 0 \leq k \leq 2 \text{ and } 0 \leq j \leq 1 \}$. See which ones will send $2 \mapsto 6$ and which ones will send $2 \mapsto 2$ when applied to the triangle in the figure (and hence the hexagon).

Answer 3

Symmetry is a fancy word for automorphism. Determining the symmetries of the graph in your post is simply asking you to determine the automorphism group of the graph.

Recall that if $G, H$ are graphs, an isomorphism $\phi : V(G) \to V(H)$ is a bijection such that if $ij \in E(G)$, then $\phi(i)\phi(j) \in E(H)$. This second condition is called a graph homomorphism:

$ij \in E(G)$, then $\phi(i)\phi(j) \in E(H)$.

An automorphism is an isomorphism $\phi : V(G) \to V(G)$, where $G$ is a graph. Trivially, the identity map is an automorphism of a graph. The automorphism group of $G$, $\text{Aut}(G)$, measures how symmetric the graph is. That is, how can we relabel the vertices to preserve the graph structure. It is, however, more intuitive to think of sending vertex $i$ to vertex $j$, rather than relabeling. That is, the group action is a dynamical process.

Now from the definition of a graph isomorphism, we have the following lemma:

Lemma: Let $G, H$ be isomorphic graphs, and let $\phi : V(G) \to V(H)$ be an isomorphism. Then for each $v \in V(G)$, $\text{deg}(v) = \text{deg}(\phi(v))$.

Take some time to prove this lemma (and feel free to comment if you need a hint).

Kaj Hansen's answer addresses the automorphism group of your graph from a geometric perspective. I'll expand from a more graph theoretic perspective. Recall that $\text{Aut}(C_{6}) \cong D_{12}$ (where $C_{6}$ is the cycle graph on six-vertices, or the regular hexagon). By the above lemma, in your graph $G$, we have that $1$ cannot map to $2$ under the action of $\text{Aut}(G)$. As $\text{Aut}(G) \leq D_{12}$, we have that $|\text{Aut}(G)| \leq 6$. Now show that $D_{6} \cong \text{Sym}(3) \leq \text{Aut}(G)$, by showing the action of $D_{6}$ on the triangle induces an action on $G$.

Answer 4

If an automorphism of the graph maps vertex $a$ to vertex $b$, then the edges incident to $a$ are mapped to edges incident to $b$. Hence, the degrees of vertices $a$ and $b$ are equal. In the graph shown, vertices $1$ and $2$ have degrees $4$ and $2$, respectively. Hence, there does not exist any automorphism which maps vertex $1$ to vertex $2$. Hence, vertices $1$ and $2$ cannot be in the same orbit of the action of the automorphism group $G$ of the graph.

Let $r$ be the permutation $(1,2,3,4,5,6)$ of the vertex set. As mentioned in the previous paragraph $r \notin G$. However, it can be observed that $r^2$ preserves adjacency and so $r^2 \in G$. Similarly, $r^4 \in G$. Hence, $G$ contains the set $\{1,r^2,r^4\}$ of three rotations. Also, $G$ contains the reflection $s = (1,3)(4,5)$ about the line which passes through vertex $2$ and the center of the figure. Thus, $G$ contains the subgroup $\langle s,r^2 \rangle$, which consists of $6$ permutations. To show that this subgroup is indeed the full automorphism group of the graph, we can use the orbit-stabilizer lemma, which asserts that $|G| = |G_2|~|2^G|$. Observe that if $g \in G_2$, then $g$ must permute the neighbors of $2$ among themselves, and so $g$ either fixes vertex $1$ or maps vertex $1$ to vertex $3$. In the former case, $g$ must be the identity, and in the latter case $g=s$. Hence, $|G_2|=2$, whence $|G| = |G_2|~|2^G| = 2 \cdot 3 = 6$.

From the theory of permutation groups, we know that if $G$ acts on a set $V$ and $x, y \in V$ are in the same orbit, then $|G_x| = |G(x \rightarrow y)|$. Since vertices $6$ and $2$ are in the same orbit, $|G(2 \rightarrow 6)|$ is equal to $|G_2|$, which equals $2$.