Scientific Research

An Academic Publisher

Properties of Suborbits of the Dihedral Group D_{n} Acting on Ordered Subsets

**Author(s)**Leave a comment

*G*,

*X*) is a transitive permutation group

*G*acting on the set

*X*. Investigations on the properties associated with various groups acting on various sets have formed a subject of recent study. A lot of investigations have been done on the action of the symmetric group S

_{n}on various sets, with regard to rank, suborbits and subdegrees. However, the action of the dihedral group has not been thoroughly worked on. This study aims at investigating the properties of suborbits of the dihedral group D

_{n }acting on ordered subsets of X={1,2,...,N}. The action of D

_{n}on X

^{[r]}, the set of all ordered r-element subsets of

*X*, has been shown to be transitive if and only if

*n*= 3. The number of self-paired suborbits of D

_{n}acting on X

^{[r]}has been determined, amongst other properties. Some of the results have been used to determine graphical properties of associated suborbital graphs, which also reflect some group theoretic properties. It has also been proved that when G = D

_{n}acts on ordered adjacent vertices of G, the number of self-paired suborbits is

*n*+ 1 if n is odd and

*n*+ 2 if n is even. The study has also revealed a conjecture that gives a formula for computing the self-paired suborbits of the action of D

_{n}on its ordered adjacent vertices. Pro-perties of suborbits are significant as they form a link between group theory and graph theory.

KEYWORDS

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.

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

_{n}Acting on Ordered Subsets.

*Advances in Pure Mathematics*,

**7**, 375-382. doi: 10.4236/apm.2017.78024.

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

Copyright © 2018 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.