Properties of Suborbits of the Dihedral Group Dn Acting on Ordered Subsets

Show more

1. Introduction

Previous investigations on rank, suborbits and subdegrees have taken into account the symmetric group S_{n} acting on various subsets of
$X=\left\{1,2,\cdots ,n\right\}$ . The rank and subdegrees of S_{n} on 2-element subsets were shown to be 3 and 1, 2,

$\left(\begin{array}{c}n\\ 2\end{array}\right)$ respectively [1] . The study was generalized to the action of S_{n} on X^{(r)}, unordered r-element subsets of
$X=\left\{1,2,\cdots ,n\right\}$ where it was established that the rank is r + 1 if n ≥ 2r, and the sudegrees are; 1,
$r\left(\begin{array}{c}n-r\\ r-1\end{array}\right),\left(\begin{array}{c}r\\ 2\end{array}\right)\left(\begin{array}{c}n-r\\ r-2\end{array}\right),\cdots ,\left(\begin{array}{c}n-1\\ r\end{array}\right)$ .

It was also proved that the suborbits of S_{n} acting on X^{(r)} are self-paired [2] . Similarly, the action of S_{n} on ordered r-element subsets of
$X=\left\{1,2,\cdots ,n\right\}$ was discussed. The action was shown to be transitive, the rank of S_{n} on X^{[3]} as 34 for n ≥ 6, and the rank of S_{n} on X^{[2]} as 7 for n ≥ 4. Properties of suborbital graphs were also examined in this action [3] . The action of the dihedral group D_{n} on X^{(r)} has also been considered where the action was proved transitive for values of r = 1 and r = n − 1 [4] .

The study of suborbits of the dihedral group acting on ordered subsets has revealed some interesting properties which translate to properties of associated suborbital graphs. This has seen a clear connection between Group Theory and Graph Theory, which has realized the artistic value in Mathematics. Section 2 outlines some of the notations and preliminary definitions which have been used in the investigations. Section 3 discusses the rank, subdegrees and suborbits of D_{n} on X^{[r]}. Some properties of suborbits have also been discussed in this Section. Section 4 has seen the application of properties of suborbits in construction of associated suborbital graphs. Section 5 examines suborbits of D_{n} on its ordered adjacent vertices.

The dihedral group D_{n} consists of all the symmetries of a regular n-sided polygon. The group is of order 2n, constituted by n rotations and n reflections.

2. Notations and Preliminary Definitions

Notation 2.1

Throughout this paper, G is the dihedral group D_{n}, X^{[r]} is the set of all ordered r-element subsets of
$X=\left\{1,2,\cdots ,n\right\}$ , and n P _{r} is n permutation r.

Definition 2.2 (Group action) [5]

Let X be a non-empty set. The group action of G on X is a relation on the pair (G, X) such that gx is a unique image of every x in X under g in G. The relation satisfies the algebraic laws of identity and associativity. Namely,

・ Ix = x, for all $x\in X$ , where $I\in G$

・
${g}_{1}\left({g}_{2}x\right)=\left({g}_{1}{g}_{2}\right)x$ , for all g_{1}, g_{2} in G and x in X_{ }

Definition 2.3 (Orbit of an element) (see [5] : p. 31)

A group action partitions the set into disjoint equivalence classes known as G-orbits. The orbit of each x in X is the subset of X,
$Or{b}_{G}\left(x\right)=\left\{gx|g\in G\right\}$ , which contains all the images of x under every g in G. The group G is transitive if given any pair of elements x_{i}, x_{j} in X, there exists g in G such that gx_{i} = x_{j}. Thus G is transitive if and only if there is exactly one orbit.

Definition 2.4 (Stabilizer of x, G_{x})

Let G be a group acting transitively on a set X. The stabilizer of x in X is the set of all elements g in G such that gx = x. The set is denoted by
${G}_{x}=\left\{g\in G:gx=x,\text{\hspace{0.17em}}\text{for}\text{\hspace{0.17em}}\text{a}\text{\hspace{0.17em}}\text{fixed}\text{\hspace{0.17em}}x\text{\hspace{0.17em}}\text{in}\text{\hspace{0.17em}}X\right\}$ . The G_{x}-orbits on X,
${\Delta}_{0},{\Delta}_{1},\cdots ,{\Delta}_{m}{}_{-1}$ are known as suborbits of G. The rank of G is m and the cardinalities,
$\left|{\Delta}_{i}\right|\left(i=0,1,\cdots ,m-1\right)$ , are the subdegrees of G. It was established in [6] that both m and the cardinalities of the suborbits are independent of the choice of x in X.

Definition 2.5

Let G act transitively on a set X and let D be an orbit of G_{x} on X. Define
${\Delta}^{*}=\left\{gx|g\in G,x\in g\Delta \right\}$ . Then D^{*} is also an orbit of G_{x} and is called the G_{x}-orbit paired with D. If D = D^{*}, then D is said to be self-paired [7] .

Theorem 2.6 (see [8] )

Let G act transitively on a set X, and suppose g Î G. The number of self- paired suborbits of G is given by

$\frac{1}{\left|G\right|}\underset{g\in G}{{\displaystyle \sum}}\left|Fix\left({g}^{2}\right)\right|$ .

Theorem 2.7 (see [9] )

Let G act transitively on X and let G_{x} be the stabilizer of the point
$x\in X$ . Let
${\Delta}_{i},i=0,1,\cdots ,m-1$ be the orbits of G_{x} on X. If
${O}_{i}\subseteq X\times X$ ,
$i=0,1,\cdots ,m-1$ , is the suborbital corresponding to ∆_{i}, then G is primitive if and only if each non-trivial suborbital graph ᴦ_{i} is connected.

Theorem 2.8 (Orbit-Stabilizer Theorem [10] : p. 72)

Let G be a group acting on a finite set X with x in X. The size of the orbit of x in G is the index $\left|G:sta{b}_{G}\left(x\right)\right|$ . Thus, $\left|or{b}_{G}\left(x\right)\right|=\left|G:sta{b}_{G}\left(x\right)\right|$ .

Theorem 2.9 (Cauchy-Frobenius Lemma [11] : p. 98)

Suppose G is a group acting on a finite set X. The number of G-orbits on X is given by $\frac{1}{\left|G\right|}{{\displaystyle \sum}}^{\text{}}\left|Fix\left(g\right)\right|$ where $\left|Fix\left(g\right)\right|$ denotes the number of elements in X fixed by g in G.

3. Main Results

3.1. Rank, Subdegrees and Suborbits of G = D_{n} on X^{[r]}

The action of G on X^{[r]} is defined by the rule;
$g\left[{x}_{1},{x}_{2},\cdots ,{x}_{r}\right]=\left[g{x}_{1},g{x}_{2},\cdots ,g{x}_{r}\right]$ for all g in G and
$\left[{x}_{1},{x}_{2},\cdots ,{x}_{r}\right]$ in X^{[r]}. The set X^{[r]} consists of all permutations of r elements from
$X=\left\{1,2,\cdots ,n\right\}$ , and its cardinality is n P_{r}.

Theorem 3.1.1

The action of G = D_{n} on X^{[r]} is transitive if and only if n = 3.

Proof:

Let
$g\in G$ and
$\left[{x}_{1},{x}_{2},\cdots ,{x}_{r}\right]$ in X^{[r]}. Now, g fixes an ordered r-element subset if and only if
$g\left[{x}_{1},{x}_{2},\cdots ,{x}_{r}\right]=\left[{x}_{1},{x}_{2},\cdots ,{x}_{r}\right]$ so that
$g{x}_{1}={x}_{1},g{x}_{2}={x}_{2},\cdots ,g{x}_{r}={x}_{r}$ . This is possible only if g is the identity. It follows that the number of elements in X^{[r]} fixed by g is n P _{r}. Using Theorem 2.9, the number of G-orbits on X^{[r]} is;

$\begin{array}{c}\frac{1}{2n}\left(\frac{n!}{\left(n-r\right)!}\right)=\frac{\left(n-1\right)!}{2\left(n-r\right)!},\text{\hspace{0.17em}}\text{\hspace{0.17em}}r\le n\\ =\frac{1}{2}\left(n-1\right)\left(n-2\right)\cdots \left(n-r+1\right).\end{array}$

The least number of G-orbits on X^{[r]} is realized when n = r, where the number is
$\frac{\left(n-1\right)!}{2}$ . If the action is transitive, then
$\frac{\left(n-1\right)!}{2}=1$ ,
$\Rightarrow $ n = 3. Conversely, if n = 3, then
$\frac{\left(n-1\right)!}{2}=1$ , and the action is transitive.

Example 3.1.2^{ }

The set X^{[2]} consists of all ordered 2-element subsets of
$X=\left\{1,2,\cdots ,n\right\}$ . Hence, its cardinality is n P_{2} =
$\frac{n!}{\left(n-2\right)!}$ . ^{ }

Let [x, y] be in X^{[}^{2]}. Now, g in G fixes an ordered pair, [x, y], if and only if
$g\left[x,y\right]=\left[x,y\right]$ , so that gx = x and gy = y. When n is odd, this is possible only if

g is the identity. It follows that,
${\sum}_{g\in G}\left|Fix\left(g\right)\right|}=n\text{\hspace{0.17em}}\text{P}{\text{\hspace{0.05em}}}_{2}\text{\hspace{0.17em}}=\frac{n!}{\left(n-2\right)!$ . Using Theorem 2.9, the number of G-orbits on X^{[2]} is
$\frac{1}{2n}\left(\frac{n!}{\left(n-2\right)!}\right)$ . Since n = 3, the number of G-orbits is 1 and G = D_{3} acts transitively on X^{[2]}.

When n is even, g fixes an ordered pair if g is the identity or a reflection through a diagonal. If g is the identity,
$\left|Fix\left(g\right)\right|$ is (n P_{2}). Since each reflection fixes 2 elements of X^{[2]} and the number of such reflections is n/2, then
$\left|Fix\left(g\right)\right|=n$ . The number of G-orbits on X^{[2]} is;

$\frac{1}{2n}\left(\frac{n!}{\left(n-2\right)!}+n\right)=\frac{n}{2}$

For transitivity,

$\frac{n}{2}=1$ , $\Rightarrow n=\text{2}$ .

But, n ≥ 3 for G to be defined. It follows that the action is intransitive.

Theorem 3.1.3

The rank of G = D_{3} on X^{[r]} is 6 and each suborbit contains 1 element.

Proof:

Let the group G = D_{3} act on X^{[r]} and
$\left[\text{1},\text{2},\cdots ,r\right]\in {X}^{\left[r\right]}$ . Since the action is transitive,
$\left|{\text{Orb}}_{G}\left[\text{1},\text{2},\cdots ,r\right]\right|=\left|{X}^{\left[r\right]}\right|=n\text{\hspace{0.17em}}\text{P}\text{\hspace{0.05em}}{\text{\hspace{0.05em}}}_{r}$ . By Theorem 2.8,
$\left|{\text{Orb}}_{G}\left[\text{1},\text{2},\cdots ,r\right]\right|=\left|G:{G}_{\left[\text{1},\text{2},\cdots ,r\right]}\right|$ . But
$\left|{G}_{\left[\text{1},\text{2},\cdots ,r\right]}\right|=1$ , by Theorem 3.1.1. Thus,
$\left|{X}^{\left[r\right]}\right|=\left|G\right|=6$ . Now, g in
${G}_{\left[\text{1},\text{2},\cdots ,r\right]}$ acts by fixing each element of X^{[r]} in its own
${G}_{\left[\text{1},\text{2},\cdots ,r\right]}$ -orbit. Since
$\left|{X}^{\left[r\right]}\right|=\text{6}$ then the rank of G on X^{[r]} is 6.

Clearly, the subdegrees of G are; 1, 1, 1, 1, 1, 1.

Example 3.1.4

The rank of G = D_{3} on X^{[3]} is 6 and each suborbit is of length 1.

Since the action is transitive,
$\left|{\text{Orb}}_{G}\left[\text{1},\text{2},\text{3}\right]\right|=\left|{X}^{[\text{3}]}\right|=\text{6}$ . From Theorem 2.8,
$\left|{\text{Orb}}_{G}\left[\text{1},\text{2},\text{3}\right]\right|=\left|G:{G}_{\left[1,2,3\right]}\right|$ . It follows that the size
$\left|{G}_{\left[1,2,3\right]}\right|$ is 1. Now, the action of g in
${G}_{\left[1,2,3\right]}$ on X^{[3]} fixes each of the 6 elements in its orbit. The 6 suborbits of G are:

${\Delta}_{0}=\left\{\left[1,2,3\right]\right\}$ ,
${\Delta}_{1}=\left\{\left[1,3,2\right]\right\}$ ,
${\Delta}_{2}=\left\{\left[3,1,2\right]\right\}$ ,
${\Delta}_{3}=\left\{\left[3,2,1\right]\right\}$ ,
${\Delta}_{4}=\left\{\left[2,3,1\right]\right\}$ ,
${\Delta}_{5}=\left\{\left[2,1,3\right]\right\}$ . Clearly, the subdegrees of G acting on X^{[3]} are: 1, 1, 1, 1, 1, 1.

3.2. Some Properties of suborbits of D_{3} on X^{[r]}

Some properties of suborbits of D_{3} acting on X^{[r]} have been discussed in the following Theorems.

Theorem 3.2.1

The number of self-paired suborbits of D_{3} on X^{[r]} is 4.

Proof:

The number of self-paired suborbits is determined by the fixed point set of g^{2}, by Theorem 2.6.

If r = 2, then g^{2} fixes an ordered set of 2 elements if g is the identity or g is a reflection. If g is the identity, then
$\left|Fix\left({g}^{\text{2}}\right)\right|=\text{3}\text{\hspace{0.17em}}\text{P}{\text{\hspace{0.17em}}}_{\text{2}}\text{\hspace{0.17em}}=\text{6}$ . If g is a reflection, then
$\left|Fix\left({g}^{\text{2}}\right)\right|=\text{3}\text{\hspace{0.17em}}\text{P}{\text{\hspace{0.17em}}}_{\text{2}}\text{\hspace{0.17em}}=\text{6}$ . Since the number of reflections is 3, then the number of

self-paired suborbits is; $\frac{1}{\left|{D}_{3}\right|}{\displaystyle {\sum}_{g\in {D}_{3}}\left|Fix\left({g}^{2}\right)\right|}=\frac{1}{6}\left\{6+3\left(6\right)\right\}=4$ . The 4 self-paired

suborbits of D_{3} on X^{[2]} are;
${\Delta}_{0}=\left[1,2\right]$ ,
${\Delta}_{1}=\left[2,1\right]$ ,
${\Delta}_{2}=\left[1,3\right]$ and
${\Delta}_{5}=\left[3,2\right]$ . By Definition 2.5,
$g\left[{\Delta}_{0},{\Delta}_{1}\right]=\left[{\Delta}_{1},{\Delta}_{0}\right]$ when g = (12),
$g\left[{\Delta}_{0},{\Delta}_{2}={\Delta}_{2},{\Delta}_{0}\right]$ when g = (23) and
$g\left[{\Delta}_{0},{\Delta}_{5}\right]=\left[{\Delta}_{5},{\Delta}_{0}\right]$ when g = (13).

If r = 3, then g^{2} fixes an ordered set of 3 elements if g is the identity or a reflection. Computation of self-paired suborbits is similar to the case when r = 2. The 4 self-paired suborbits of D_{3} on X^{[3]} are;
${\Delta}_{0}=\left[1,2,3\right]$ ,
${\Delta}_{1}=\left[1,3,2\right]$ ,
${\Delta}_{3}=\left[3,2,1\right]$

and ${\Delta}_{\text{5}}=\left[\text{2},\text{1},\text{3}\right]$ . Clearly, g can be chosen accordingly so that; $g\left[{\Delta}_{0},{\Delta}_{\text{1}}\right]=\left[{\Delta}_{\text{1}},{\Delta}_{0}\right]$ when g = (23), $g\left[{\Delta}_{0},{\Delta}_{3}\right]=\left[{\Delta}_{3},{\Delta}_{0}\right]$ when g = (13) and $g\left[{\Delta}_{0},{\Delta}_{5}\right]=\left[{\Delta}_{5},{\Delta}_{0}\right]$ when g = (12).

Theorem 3.2.2

Let G = D_{3} act transitively on X^{[r]}. If
${\Delta}_{i}=\left[{x}_{\text{1}},{x}_{\text{2}},\cdots ,{x}_{r}\right]$ is a
${G}_{\left[\text{1},\text{2},\cdots ,r\right]}$ -orbit on X^{[r]}, where
${x}_{i}\in \left\{\text{1},\text{2},\cdots ,r\right\}$ , then D_{i} is self-paired if and only if the permutation
$g\left[\text{1},\text{2},\cdots ,r\right]=\left[{x}_{\text{1}},{x}_{\text{2}},\cdots ,{x}_{r}\right]$ is such that g^{2} = 1.

Proof:

If D_{i} is self-paired, then there exists g in D_{3} such that
$g\left[{\Delta}_{0},{\Delta}_{i}\right]=\left[{\Delta}_{i},{\Delta}_{0}\right]$ , by Theorem 2.5. Considering
${\Delta}_{0}=\left[1,2,\cdots ,r\right]$ ,
$g\left(1\right)={x}_{1},g\left(2\right)={x}_{2},\cdots ,g\left(r\right)={x}_{r}$ and
$g\left({x}_{1}\right)=1,g\left({x}_{2}\right)=2,\cdots ,g\left({x}_{r}\right)=r$ . This implies that g(1) = x_{1} and g(x_{1}) = 1, Þ
${x}_{\text{1}}={g}^{-\text{1}}\left(\text{1}\right)$ . Thus,
$g\left(\text{1}\right)={g}^{-\text{1}}\left(\text{1}\right)$ . Hence, g^{2} = 1. Conversely, if g^{2} = 1, then g = g^{−1}. Now, g is such that
$g\left[1,2,\cdots ,r\right]=\left[{x}_{1},{x}_{2},\cdots ,{x}_{r}\right]$ and
$g\left[{x}_{\text{1}},{x}_{\text{2}},\cdots ,{x}_{r}\right]=\left[\text{1},\text{2},\cdots ,r\right]$ , Þ
$g\left[{\Delta}_{0},{\Delta}_{i}\right]=\left[{\Delta}_{i},{\Delta}_{0}\right]$ . Hence, D_{i} is self-paired.

Theorem 3.2.3

Suppose G = D_{3} is transitive on X^{[r]}. Then ∆_{i} and ∆_{j} are paired suborbits of G if and only if the permutations g and h, in the maps g∆_{i} = ∆_{0} and h∆_{j} = ∆_{0}, are inverses of each other.

Proof:

Suppose ∆_{i} and ∆_{j} are paired suborbits of G. Then there exists g and h in G such that g∆_{i} = ∆_{0} and h∆_{j} = ∆_{0}. There exists x_{i} in ∆_{i} and y_{i} in ∆_{j} such that gx_{i} = 1 and hy_{i} = 1. By Definition 2.5, g(1) = y_{i} and h(1) = x_{i}. It follows that, gh(1) = 1 and hg(1) = 1. Hence, g and h are inverses of each other. Conversely, if g and h are inverses of each other, then g maps x_{i} to 1 and 1 to y_{i}. Similarly, h maps y_{i} to 1 and 1 to x_{i}. Hence, ∆_{i} and ∆_{j} are paired suborbits.

Example 3.2.4

Let G = D_{3} act on X^{[2]}. Then ∆_{3} = [3, 1] and ∆_{4} = [2, 3] are paired suborbits of G. Clearly, g∆_{3} = ∆_{0} and h∆_{4} = ∆_{0}, when g = (123) and h = (132), where g and h are inverses of each other.

4. Suborbital Graphs of G = D_{3} Acting on X^{[r]}

Let
$\Delta =\left[{x}_{\text{1}},\cdots ,{x}_{r}\right]$ be a suborbit of G on X^{[r]}, where
${x}_{i}\in \left\{\text{1},\text{2},\cdots ,n\right\}$ . Then the suborbital O corresponding to ∆ is given by;
$O=\left\{\left(g\left[\text{1},\text{2},\cdots ,r\right],g\left[{x}_{\text{1}},{x}_{\text{2}},\cdots ,{x}_{r}\right]\right)|g\in G,\left[{x}_{\text{1}},{x}_{\text{2}},\cdots ,{x}_{r}\right]\in \Delta \right\}$ . The graph ᴦ corresponding to suborbital O is formed by considering X^{[r]} as the vertex set and drawing an edge from
$\left[{c}_{\text{1}},{c}_{\text{2}},\cdots ,{c}_{r}\right]$ to
$\left[{d}_{\text{1}},{d}_{\text{2}},\cdots ,{d}_{r}\right]$ if and only if
$\left(\left[{c}_{\text{1}},{c}_{\text{2}},\cdots ,{c}_{r}\right],\left[{d}_{\text{1}},{d}_{\text{2}},\cdots ,{d}_{r}\right]\right)\in O$ . Now, the suborbital graph corresponding to a self-paired suborbit ∆_{i} has an edge from
$C=\left[{c}_{\text{1}},{c}_{\text{2}},\cdots ,{c}_{r}\right]$ to
$D=\left[{d}_{\text{1}},{d}_{\text{2}},\cdots ,{d}_{r}\right]$ only if
$\left|C\cap D\right|=1$ . The graph corresponding to a paired suborbit ∆_{i} has an edge from
$C=\left[{c}_{\text{1}},{c}_{\text{2}},\cdots ,{c}_{r}\right]$ to
$D=\left[{d}_{\text{1}},{d}_{\text{2}},\cdots ,{d}_{r}\right]$ only if
$\left|C\cap D\right|=0$ .

Theorem 4.1

All suborbital graphs corresponding to the action of D_{3} on X^{[r]} are disconnected.

Proof:

Let ᴦ_{i} be the suborbital graph corresponding to a self-paired suborbit ∆_{i}. Suppose
$\left[{c}_{\text{1}},{c}_{\text{2}},\cdots ,{c}_{r}\right]$ is a point on the vertex set, X^{[r]}. Then there is an edge from
$\text{S}=\left[{c}_{\text{1}},{c}_{\text{2}},\cdots ,{c}_{r}\right]$ to
$\text{T}=\left[{d}_{\text{1}},{d}_{\text{2}},\cdots ,{d}_{r}\right]$ if the corresponding coordinates, c_{i} and d_{i}, are identical. The 3 coordinates can be rearranged in 3! ways. Each coordinate can take the same position in 1/3(3!) = 2 possibilities. Thus, an edge joining exactly 2 vertices is a connected component and the graph is disconnected. If ∆_{i} is a paired suborbit, then the corresponding graph has an edge from
$\text{S}=\left[{c}_{\text{1}},{c}_{\text{2}},\cdots ,{c}_{r}\right]$ to
$\text{T}=\left[{d}_{\text{1}},{d}_{\text{2}},\cdots ,{d}_{r}\right]$ if none of the corresponding coordinates, c_{i} and d_{i}, are identical. The number of such rearrangements is 1/2(3!) = 3. It follows that a path joining exactly 3 vertices is a connected component. Hence, the graph is disconnected.

Theorem 4.2

The action of G = D_{3} on X^{[r]} is imprimitive.

Proof:

Suppose ᴦ_{i} is a suborbital graph corresponding to a suborbit, ∆_{i}, of G on X^{[3]}. Then, from Theorem 4.1, the graph is disconnected. From Theorem 2.7, the action of D_{3} on X^{[r]} is imprimitive.

Theorem 4.3

Let G = D_{3} act on X^{[r]}. Suppose ∆_{i} is a self-paired suborbit of G. Then the number of connected components of the suborbital graph ᴦ_{i} corresponding to ∆_{i} is 3. If ∆_{i} is a paired suborbit of G, then the number of connected components in the corresponding graph is 2.

Proof:

Let ᴦ_{i} be the suborbital graph corresponding to the self-paired subotbit ∆_{i}. From Theorem 4.1, the connected component is an edge with exactly 2 vertices. The number of connected components is

$\text{N}\left({\Gamma}_{i}\right)=\frac{\text{Number}\text{\hspace{0.17em}}\text{of}\text{\hspace{0.17em}}\text{vertices}\text{\hspace{0.17em}}\text{in}\text{\hspace{0.17em}}{\Gamma}_{i}}{2}=3.$

If ∆_{i} is a paired suborbit, then the corresponding graph is a path joining exactly 3 vertices. It follows,
$\text{N}\left({\Gamma}_{i}\right)=6/3=\text{2}$ .

5. Suborbits of G = D_{n} Acting on Ordered Adjacent Vertices of G

Let G = D_{n} and S be the set of all ordered pairs of adjacent vertices of G. The action of G on S is defined in Section 3.1, since S is a subset of X^{[2]}.

Theorem 5.1

The action of G on S is transitive.

Proof:

Let [x, y] Î S, g Î G and G act on S. Now, g fixes [x, y] only if g is the identity. It follows that $\left|Fix\left(g\right)\right|=\left|S\right|=2n$ . Using Theorem 2.9, the number of G-orbits on S is 1. Hence, the action is transitive.

Theorem 5.2

The rank of G on S is 2n and each suborbit contains 1 element.

Proof:

Using Theorem 2.8, the size
$\left|{\text{Orb}}_{G}\left[x,y\right]\right|=\left|G:{G}_{\left[x,y\right]}\right|$ , for any element [x, y] in S. Since the action is transitive,
$\left|{\text{Orb}}_{G}\left[x,y\right]\right|=\left|S\right|=\text{2}n$ . It follows that
$\left|{G}_{\left[x,y\right]}\right|=1$ . Now, G_{[x,} _{y}_{]} acts on S by fixing each of the 2n elements in its own orbit. Therefore, the rank of G on S is 2n and each suborbit contains 1 element.

Theorem 5.3

The number of self-paired suborbits of G = D_{n} acting on S is n + 1 when n is odd and n + 2 when n is even.

Proof:

If n is odd, then by Theorem 2.6, g^{2} fixes [x, y] in S, if g is the identity or g is a reflection. If g is the identity, then
$\left|Fix\left({g}^{2}\right)\right|=2n$ . From each reflection, the

number $\left|Fix\left({g}^{2}\right)\right|=2n$ . Since the number of reflections is n, then ${\sum}_{g\in G}\left|Fix\left({g}^{2}\right)\right|}=2n+n\left(2n\right)$ and the number of self-paired suborbits is $\frac{1}{2n}\left(2n+2{n}^{2}\right)=n+1$ .

If n is even, then g^{2} fixes [x, y] in S if g is the identity, or g is a reflection, or g is a rotation of 180˚. From each possibility,
$\left|Fix\left({g}^{2}\right)\right|=2n$ . But the number of

reflections is n and hence, ${\sum}_{g\in G}\left|Fix\left({g}^{2}\right)\right|}=2n+2{n}^{2}+2n$ . The number of self-

paired suborbits is then; $\frac{1}{2n}\left(4n+2{n}^{2}\right)=n+2$ .

The following conjecture was revealed in the process of the investigations;

If n is odd, then the n + 1 self-paired suborbits of G = D_{n} on S are given by;
${\Delta}_{0}=\left[\text{1},\text{2}\right]$ ,
${\Delta}_{\text{1}}=\left[\text{1},n\right]$ ,
${\Delta}_{i}=\left[i,i-1\right]\left(i=2,3,\cdots ,n\right)$ . If n is even, then the n + 2 self-paired suborbits of D_{n} acting on S are given by;
${\Delta}_{0}=\left[\text{1},\text{2}\right]$ ,
${\Delta}_{\text{1}}=\left[\text{1},n\right]$ ,

${\Delta}_{2}=\left[\frac{n+2}{2},\frac{n+4}{2}\right]$ , ${\Delta}_{i}{}_{+1}=\left[i,i-1\right]\left(i=2,3,\cdots ,n\right)$ .

6. Conclusion

Let G = D_{3} act transitively on X^{[r]}. It has been established that the number of self -paired suborbits is 4. The graph ᴦ_{i} corresponding to a self-paired suborbit ∆_{i} is determined by g in the map
$g\left[{\Delta}_{i},{\Delta}_{0}\right]=\left[{\Delta}_{0},{\Delta}_{i}\right]$ . If g fixes k in ∆_{0}, then the corresponding graph ᴦ_{i} has an edge from
$C=\left[{c}_{1},{c}_{2},{c}_{3}\right]$ to
$D=\left[{d}_{1},{d}_{2},{d}_{3}\right]$ if and only if the k^{th} coordinate of C is identical to the k^{th} coordinate of D. The results could be used to investigate other properties of suborbital graphs associated with the action of D_{3} on ordered subsets.

References

[1] Higman, D.G. (1964) Finite Permutation Groups of Rank 3. Mathematische Zeitschrift, 86, 145-156.

https://doi.org/10.1007/BF01111335

[2] Nyaga, L., Kamuti, I., Mwathi, C. and Akanga, J. (2011) Ranks and Subdegrees of the Symmetric Group Sn Acting on Unordered r-Element Subsets. International Electronic Journal of Pure and Applied Mathematics, 3, 147-163.

[3] Rimberia, J.K., Kamuti, I.N., Kivunge, B.M. and Kinyua, F. (2012) Ranks and Subdegrees of the Symmetric Group Sn Acting on Ordered r-Element Subsets. Journal of Mathematical Sciences, 23, 383-390.

[4] Gachogu, R. and Kamuti, I. (2014) Ranks and Subdegrees of the Dihedral Groups Dn Acting on Unordered r-Element Subsets. International Journal of Algebra, 8, 537-545.

https://doi.org/10.12988/ija.2014.4667

[5] Robinson, D.J.S. (1996) A Course in the Theory of Groups. Springer-Verlag, New York.

https://doi.org/10.1007/978-1-4419-8594-1

[6] Ivanov, A.A., Klin, M.H., Tsaranov, S.V. and Shpektorov, S.V. (1983) On the Problem of Computing Subdegrees of Transitive Permutation Groups. Soviet Mathematical Survey, 38, 123-124.

https://doi.org/10.1070/RM1983v038n06ABEH003460

[7] Wielandt, H. (1964) Finite Permutation Groups. Academic Press, New York.

[8] Cameron, P.J. (1994) Combinatorics: Topics, Techniques and Algorithms. Cambridge University Press, Cambridge.

[9] Sims, C.C. (1967) Graphs and Finite Permutation Groups. Mathematische Zeitschrift, 95, 76-86.

https://doi.org/10.1007/BF01117534

[10] Rose, J.S. (1978) A Course on Group Theory. Cambridge University Press, Cambridge.

[11] Harary, F. (1969) Graph Theory. Addison-Wesley Publishing Company, New York.