This paper investigates the combinatorial properties, invariants, and structures arising from the action of the direct product \(S_n \times A_n\) on the Cartesian product \(X^{(2)} \times Y^{(2)}\), where \(X^{(2)}\) and \(Y^{(2)}\) denote the sets of unordered 2-element subsets of two distinct sets \(X\) and \(Y\), each of cardinality \(n\). Using the Orbit-Stabilizer Theorem, we establish that the action is transitive for all \(n \ge 2\) and, through block theory, demonstrate that it is imprimitive for all \(n \ge 3\). By determining the orbits of the stabilizer of a fixed element, we compute the rank of the action to be \(9\) and explicitly enumerate the eight non-trivial subdegrees for \(n \ge 5\) as: \(2(n-2)\), \(2(n-2)\), \(\frac{(n-2)(n-3)}{2}\), \(\frac{(n-2)(n-3)}{2}\), \(4(n-2)^2\), \((n-2)^2(n-3)\), \((n-2)^2(n-3)\), and \(\frac{(n-2)^2(n-3)^2}{4}\). A combinatorial proof establishes that all suborbits are self-paired for \(n\ge 5\). We construct the eight non-trivial suborbital graphs corresponding to these suborbits and analyze their fundamental graph-theoretic properties, including connectedness, regularity, vertex degrees, and girth. The results extend the classical theory of permutation groups acting on combinatorial objects and provide a foundation for potential applications in coding theory, cryptography, and control systems.
Group actions form a fundamental concept in modern algebra, providing a framework for studying symmetries of mathematical objects through permutation representations. The systematic study of group actions began in the 19th century with the work of mathematicians such as Cauchy, Jordan, and Klein, who recognized that understanding how a group acts on a set reveals deep structural properties of both the group and the set. The Orbit-Stabilizer Theorem, Cauchy-Frobenius Lemma, and the theory of permutation groups have since become indispensable tools in diverse areas ranging from number theory to theoretical physics.
The symmetric group \(S_n\) and the alternating group \(A_n\) occupy central positions in permutation group theory. Their actions on combinatorial objects have been extensively investigated due to their rich structure and wide applicability. In particular, actions on subsets of a finite set have yielded profound insights into the nature of permutation groups. Nagai [4] initiated this line of inquiry by studying the action of \(A_7\) on \(X^{(2)}\), the set of unordered pairs from a \(7\)-element set, demonstrating the existence of primitive groups of degree \(21\) containing non-abelian regular subgroups. This seminal work inspired a systematic investigation of symmetric and alternating groups acting on various combinatorial configurations. Higman [3] established foundational results for the action of \(S_n\) on \(X^{(2)}\), showing that the action has rank \(3\) with subdegrees \(1\), \(2(n-2)\), and \(\binom{n-2}{2}\), and that primitivity holds precisely when \(n\ge5\). Neumann [5] extended this work, proving that all suborbits of this action are self-paired for \(S_5\). Subsequent investigations have expanded this theory in multiple directions. Rimberia [7] analyzed the action of \(S_n\) on ordered \(r\)-element subsets \(X^{[r]}\), deriving formulas for the rank and establishing conditions for imprimitivity. Nyaga [6] examined the analogous action on unordered \(r\)-element subsets \(X^{(r)}\), proving transitivity, computing the rank as \(r+1\) for \(n\ge 2r\), and demonstrating that all suborbits are self-paired. More recently, Gachimu [2] studied actions of the alternating group \(A_n\) on both ordered and unordered subsets, characterizing transitivity and primitivity conditions and computing subdegrees.
Despite this extensive literature on actions of \(S_n\) and \(A_n\) individually on subsets of a single set, the action of their direct product \(S_n\times A_n\) on the Cartesian product of unordered subset collections from two distinct sets has remained unexplored. This paper addresses that gap. The key novel features are:
(a) Direct product structure: Earlier work considered either \(S_n\) or \(A_n\) alone acting on subsets of a single set. Here, the two factors act independently on two separate sets, introducing independent permutation coordinates.
(b) Mixed parity constraints: The second factor is restricted to even permutations (\(A_n\)), while the first factor is unrestricted (\(S_n\)). This asymmetry generates a richer orbit structure than the action of \(S_n\times S_n\) or \(A_n\times A_n\).
(c) Cartesian product of unordered pairs: While Nyaga [6] studied \(S_n\) acting on \(X^{(r)}\), and Gachimu [2] studied \(A_n\) on \(X^{(r)}\), the Cartesian product \(X^{(2)}\times Y^{(2)}\) with a direct product group has not been analyzed before.
As we shall show, this action has rank \(9\) (compared to rank \(3\) for \(S_n\) on \(X^{(2)}\)), eight non-trivial subdegrees with explicit combinatorial formulas, and all suborbits are self-paired for \(n\ge5\). The associated suborbital graphs exhibit diverse properties: some are connected with small girth (\(3\) or \(5\)), others are disconnected; all are regular. These results extend the classical theory of permutation groups acting on combinatorial objects and provide a new family of examples for the study of rank-\(9\) permutation groups.
While specific direct applications are beyond the scope of this purely mathematical investigation, the structural results-explicit subdegrees, self-paired suborbits, and associated graphs – may prove useful in domains such as coding theory (association schemes) and cryptography (permutation codes). For instance, self-paired suborbits correspond to symmetric association schemes, which are relevant to coding theory [1].
The paper is organized as follows. Section 2 presents preliminary definitions and theorems essential for the subsequent analysis. Section 3 contains the main results: transitivity (Subsection 3.1), primitivity (Subsection 3.2), rank and subdegrees (Subsection 3.3), suborbit pairing (Subsection 3.4), and suborbital graph constructions (Subsection 3.5). Section 4 provides concluding remarks and directions for future research.
In this section, we establish the notation used throughout the paper and recall fundamental definitions and theorems from group action theory.
Let \(X = \{x_1,x_2,\dots,x_n\}\) and \(Y = \{y_1,y_2,\dots,y_n\}\) be two disjoint sets, each of cardinality \(n\ge2\). Define \[X^{(2)} = \{A \subseteq X : |A|=2\}, \qquad Y^{(2)} = \{B \subseteq Y : |B|=2\}.\]
These are the sets of unordered \(2\)-element subsets. Set \(\Omega = X^{(2)} \times Y^{(2)}.\) Let \(G = S_n \times A_n\), where \(S_n\) acts on \(X\) by all permutations and \(A_n\) acts on \(Y\) by even permutations.
Definition 2.1 (Group Action). A left action of a group \(G\) on a set \(\Omega\) is a function \(G \times \Omega \to \Omega\), denoted \((g, \omega) \mapsto g \cdot \omega\), satisfying \((g_1 g_2) \cdot \omega = g_1 \cdot (g_2 \cdot \omega)\) and \(e \cdot \omega = \omega\) for all \(g_1, g_2 \in G\) and \(\omega \in \Omega\), where \(e\) is the identity element.
Definition 2.2 (Explicit Action). For \((\sigma, \tau) \in G\) and \((\{x_i, x_j\}, \{y_k, y_\ell\}) \in \Omega\), define \[(\sigma, \tau) \cdot \big( \{x_i, x_j\}, \{y_k, y_\ell\} \big) = \big( \{\sigma(x_i), \sigma(x_j)\}, \{\tau(y_k), \tau(y_\ell)\} \big).\]
This is a well-defined left action because permutations map unordered pairs to unordered pairs, and composition in the direct product acts componentwise. Consequently, \[|\Omega| = \binom{n}{2}^2, \qquad |G| = |S_n| \cdot |A_n| = n! \cdot \frac{n!}{2} = \frac{(n!)^2}{2}.\]
Definition 2.3 (Orbit). Let \(G\) act on \(\Omega\). For \(\omega \in \Omega\), the orbit of \(\omega\) is \(Orb_G(\omega) = \{g \cdot \omega \mid g \in G\}.\) The orbits partition \(\Omega\).
Theorem 2.4 (Cauchy-Frobenius (Burnside’s Lemma)). The number of orbits of \(G\) on \(\Omega\) is \[\frac{1}{|G|} \sum_{g \in G} |fix(g)|,\] where \(fix(g) = \{\omega \in \Omega \mid g \cdot \omega = \omega\}\).
Definition 2.5 (Stabilizer). For \(\omega \in \Omega\), the stabilizer of \(\omega\) is \(Stab_G(\omega) = \{g \in G \mid g \cdot \omega = \omega\}.\) This is a subgroup of \(G\).
Theorem 2.6 (Orbit-Stabilizer Theorem). Let \(G\) be a finite group acting on a set \(\Omega\), and let \(\omega \in \Omega\). Then \[|Orb_G(\omega)| = |G : Stab_G(\omega)| = \frac{|G|}{|Stab_G(\omega)|}.\]
Definition 2.7 (Transitive Action). An action of \(G\) on \(\Omega\) is transitive if for every \(\omega_1, \omega_2 \in \Omega\) there exists \(g \in G\) such that \(g \cdot \omega_1 = \omega_2\). Equivalently, there is exactly one orbit.
Definition 2.8. Let \(G\) act transitively on \(\Omega\). Fix \(\alpha\in\Omega\) and let \(H = \operatorname{Stab}_G(\alpha)\). The orbits \(\Delta_0=\{\alpha\},\Delta_1,\dots,\Delta_{r-1}\) of \(H\) on \(\Omega\) are the suborbits. The number \(r\) is the rank. For \(i\ge1\), \(|\Delta_i|\) is a subdegree.
Definition 2.9 (Self-Pairing). For a suborbit \(\Delta\), define \(\Delta^* = \{g \cdot \alpha \mid g \in G,\; \alpha \in g \cdot \Delta\}.\) Then \(\Delta^*\) is also a suborbit, called the paired suborbit of \(\Delta\). If \(\Delta^* = \Delta\), then \(\Delta\) is said to be self-paired.
Definition 2.10 (Block). Let a group \(G\) act on a set \(\Omega\). A nonempty subset \(B \subseteq \Omega\) is called a block (or block of imprimitivity) if for every \(g \in G\), \(gB = B \quad \text{or} \quad gB \cap B = \varnothing.\) The trivial blocks are \(B = \Omega\) and all singleton subsets \(\{\omega\}\) for \(\omega \in \Omega\). An action is primitive if the only blocks are trivial; otherwise it is imprimitive.
Remark 2.11. In transitive actions, if \(B\) is a block then \(|B|\) divides \(|\Omega|\).
Theorem 3.1. The action of \(G = S_n \times A_n\) on \(\Omega = X^{(2)} \times Y^{(2)}\) is transitive for all \(n \ge 2\).
Proof. Let \(\left(\sigma,\tau\right)\in G\). For \(\sigma \in S_n\) to fix \(\{x_1, x_2\}\) setwise, \(\sigma\) must permute \(\{x_1, x_2\}\) (2 ways) and independently permute the remaining \(n-2\) elements \(\{x_3, \dots, x_n\}\) arbitrarily in \((n-2)!\) ways. Thus \[|\operatorname{Stab}_{S_n}(\{x_1, x_2\})| = 2(n-2)!.\]
For \(\tau \in A_n\) to fix \(\{y_1, y_2\}\) setwise, we consider three cases.
Case \(n=2\): If \(n=2\), then \(Y = \{y_1,y_2\}\) and \(Y^{(2)} = \{\{y_1,y_2\}\}\) is a singleton. The only permutation of \(Y\) is the identity, which is even. Thus, \(|\operatorname{Stab}_{A_2}(\{y_1,y_2\})| = 1\). Now, \(|G_\alpha| = |\operatorname{Stab}_{S_2}(\{x_1,x_2\})| \cdot |\operatorname{Stab}_{A_2}(\{y_1,y_2\})| = (2\cdot 0!) \cdot 1 = 2 \cdot 1 = 2\). Then \(|G| = |S_2|\cdot|A_2| = 2 \cdot 1 = 2\), so \(|\operatorname{Orb}_G(\alpha)| = \frac{2}{2} = 1 = \binom{2}{2}^2\).
Case \(n=3\): If \(n=3\), then \(Y = \{y_1,y_2,y_3\}\). The even permutations are \(A_3 = \{e_Y, (y_1y_2y_3), (y_1y_3y_2)\}\). Which of these fix \(\{y_1,y_2\}\) setwise?
(i) \(e_Y\) fixes both points.
(ii) \((y_1y_2y_3)\) sends \(y_1 \mapsto y_2\), \(y_2 \mapsto y_3\), so \(\{y_1,y_2\}\) is not fixed setwise.
(iii) \((y_1y_3y_2)\) sends \(y_1 \mapsto y_3\), \(y_2 \mapsto y_1\), so \(\{y_1,y_2\}\) is not fixed setwise.
Thus only the identity works, so \(|\operatorname{Stab}_{A_3}(\{y_1,y_2\})| = 1\). Now, \(|G_\alpha| = (2 \cdot 1!) \cdot 1 = 2 \cdot 1 = 2\). \(|G| = 6 \cdot 3 = 18\), so \(|\operatorname{Orb}_G(\alpha)| = \frac{18}{2}= 9 = \binom{3}{2}^2\).
Case \(n \ge 4\): A permutation \(\tau \in A_n\) fixes \(\{y_1,y_2\}\) setwise if either:
(i) \(\tau\) fixes \(y_1\) and \(y_2\) pointwise, and acts as an even permutation on \(\{y_3,\dots,y_n\}\). The number of such permutations is \(\frac{(n-2)!}{2}\).
(ii) \(\tau\) swaps \(y_1\) and \(y_2\), and acts as an odd permutation on \(\{y_3,\dots,y_n\}\) (so that the overall permutation is even). The number of odd permutations on \(n-2\) elements is \(\frac{(n-2)!}{2}\), provided \(n-2 \ge 2\) (i.e., \(n \ge 4\)).
Therefore, for \(n \ge 4\), \[|\operatorname{Stab}_{A_n}(\{y_1,y_2\})| = \frac{(n-2)!}{2} + \frac{(n-2)!}{2} = (n-2)!.\]
If \[\alpha = (\{x_1, x_2\}, \{y_1, y_2\}),\] then, for the appropriate range, \[|G_\alpha| = |\operatorname{Stab}_{S_n}(\{x_1, x_2\})| \cdot |\operatorname{Stab}_{A_n}(\{y_1, y_2\})| = 2(n – 2)! \cdot (n – 2)! = 2\big((n – 2)!\big)^2.\]
Therefore \[|\operatorname{Orb}_G(\alpha)| = \frac{|G|}{|G_\alpha|} = \frac{\frac{(n!)^2}{2}}{2\bigl((n-2)!\bigr)^2} = \left( \frac{n(n-1)}{2} \right)^2 = \binom{n}{2}^2 = |\Omega|.\]
Thus the orbit of \(\alpha\) is the entire set \(\Omega\), proving transitivity for all \(n \ge 2\) (the cases \(n=2,3\) having been verified directly). \(\square\)
Theorem 3.2. The action of \(G\) on \(\Omega\) is imprimitive for all \(n \ge 3\).
Proof. Recall that a non-empty proper subset \(B \subset \Omega\) is a block if \(|B|\) divides \(|\Omega|\) and for every \(g \in G\), either \(gB = B\) or \(gB \cap B = \emptyset\).
Define \[B = \big\{ \{x_1, x_2\} \big\} \times Y^{(2)} = \big\{ (\{x_1, x_2\}, \{y_i, y_j\}) \mid 1 \le i < j \le n \big\}.\]
For \(n \ge 3\), we have \(\binom{n}{2} \ge 3\), so \[1 < |B| = \binom{n}{2} < \binom{n}{2}^2 = |\Omega|.\]
Thus \(B\) is non-trivial in size.
Now take any \((\sigma, \tau) \in G\). There are two cases:
(i) Case 1: \(\sigma(\{x_1, x_2\}) = \{x_1, x_2\}\). Then for any \((\{x_1, x_2\}, \{y_i, y_j\}) \in B\), \[(\sigma, \tau) \cdot (\{x_1, x_2\}, \{y_i, y_j\}) = (\{x_1, x_2\}, \{\tau(y_i), \tau(y_j)\}) \in B,\] because \(\tau\) permutes \(Y\) and therefore maps \(Y^{(2)}\) onto itself. Hence \((\sigma, \tau)B \subseteq B\), and by bijectivity \((\sigma, \tau)B = B\).
(ii) Case 2: \(\sigma(\{x_1, x_2\}) \neq \{x_1, x_2\}\). Every element of \(B\) has first coordinate \(\{x_1, x_2\}\), while every element of \((\sigma, \tau)B\) has first coordinate \(\sigma(\{x_1, x_2\}) \neq \{x_1, x_2\}\). Thus \((\sigma, \tau)B \cap B = \emptyset\).
Therefore \(B\) is a non-trivial block, and the action is imprimitive. \(\square\)
Theorem 3.3.
The group \(G=S_{_{n}}\times A_{_{n}}\)
acts on \(X^{^{(2)}}\times Y^{^{(2)}}\)
with rank \(9\) and subdegrees \(1,2\left(n-2\right),2\left(n-2\right),\frac{\left(n-2\right)\left(n-3\right)}{2},\)
\(\frac{\left(n-2\right)\left(n-3\right)}{2},4\left(n-2\right)^{^{2}},\left(n-2\right)^{^{2}}\left(n-3\right),\left(n-2\right)^{^{2}}\left(n-3\right),\frac{\left(n-2\right)^{^{2}}\left(n-3\right)^{^{2}}}{4}\)
for all \(n\geq5\).
Proof. Choose \(\alpha = (\{x_1,x_2\},\{y_1,y_2\}) \in \Omega\) and let \(H = \operatorname{Stab}_G(\alpha)\). Because \(G\) acts componentwise, \[H = \operatorname{Stab}_{S_n}(\{x_1,x_2\}) \times \operatorname{Stab}_{A_n}(\{y_1,y_2\}) = H_X \times H_Y.\]
Explicitly, \[H_X \cong \langle (x_1\,x_2) \rangle \times S_{\{x_3,\ldots,x_n\}}, \qquad |H_X| = 2(n-2)!,\] \[H_Y = \{\tau \in A_n : \tau(\{y_1,y_2\}) = \{y_1,y_2\}\}, \qquad |H_Y| = (n-2)! \;\; (n\ge 4).\]
For any \(\beta = (\{u_1,u_2\},\{v_1,v_2\}) \in \Omega\), define \[a = |\{u_1,u_2\} \cap \{x_1,x_2\}| \in \{0,1,2\}, \qquad c = |\{v_1,v_2\} \cap \{y_1,y_2\}| \in \{0,1,2\}.\]
Both \(a\) and \(c\) are invariant under the action of \(H\) because \(H\) preserves \(\{x_1,x_2\}\) and \(\{y_1,y_2\}\) setwise. Thus the \(H\)-orbits (suborbits) refine the partition of \(\Omega\) by the pair \((a,c)\). For each fixed \((a,c) \in \{0,1,2\}^2\), \(H\) acts transitively on \[\Delta_{(a,c)} = \{\beta \in \Omega : |\{u_1,u_2\}\cap\{x_1,x_2\}| = a,\; |\{v_1,v_2\}\cap\{y_1,y_2\}| = c\}.\]
(a) \(X\)-coordinate: \(H_X \cong C_2 \times S_{n-2}\) acts transitively on all \(2\)-subsets of \(X\) with a given \(a\):
(i) \(a=2\): only \(\{x_1,x_2\}\) (trivial).
(ii) \(a=1\): subsets \(\{x_1,x_k\}\) or \(\{x_2,x_k\}\) (\(k\ge 3\)). \(S_{n-2}\) permutes the \(k\)’s transitively; \((x_1\,x_2)\) swaps the two types.
(iii) \(a=0\): subsets \(\{x_i,x_j\}\) (\(i,j\ge 3\)). \(S_{n-2}\) acts as the full symmetric group on these \(\binom{n-2}{2}\) subsets.
Hence \(H_X\) is transitive on each \(X\)-class for all \(n\ge 3\).
(b) \(Y\)-coordinate: \(H_Y\) consists of even permutations preserving \(\{y_1,y_2\}\). For \(n\ge 5\), \(H_Y\) acts transitively on each \(Y\)-class:
(i) \(c=2\): only \(\{y_1,y_2\}\) (trivial).
(ii) \(c=1\): subsets \(\{y_1,y_p\}\) or \(\{y_2,y_p\}\) (\(p\ge 3\)). To map \(\{y_1,y_p\} \to \{y_1,y_q\}\), use the \(3\)-cycle \((y_p\,y_q\,y_r)\) with \(r\ge 3\) distinct from \(p,q\) (possible since \(n\ge 5\) gives at least \(3\) spare indices). This \(3\)-cycle is even, fixes \(y_1,y_2\), and lies in \(H_Y\). To map \(\{y_1,y_p\} \to \{y_2,y_q\}\), first apply \((y_1\,y_2)\) times an odd permutation on \(\{y_3,\ldots,y_n\}\) (exists for \(n\ge 5\)). This product is even and swaps the pair, then adjust with a \(3\)-cycle. Thus \(H_Y\) is transitive on \(c=1\) subsets.
(iii) \(c=0\): subsets \(\{y_p,y_q\}\) with \(p,q\ge 3\). If disjoint, \((y_p\,y_r)(y_q\,y_s)\) (product of two transpositions) is even. If they share an element, use a \(3\)-cycle with a spare index. Hence transitive.
The condition \(n\ge 5\) is essential: for \(n=4\) there is no spare index for \(3\)-cycles; for \(n=3\), \(H_Y\) is trivial.
Since \(H = H_X \times H_Y\) acts componentwise, the product of transitive actions on each coordinate yields transitivity of \(H\) on \(\Delta_{(a,c)}\). Therefore the \(H\)-orbits are exactly the nine sets \(\Delta_{(a,c)}\) for \((a,c) \in \{0,1,2\}^2\).
For a fixed \((a,c)\), the number of \(2\)-subsets of \(X\) with intersection size \(a\) with \(\{x_1,x_2\}\) is \(\binom{2}{a}\binom{n-2}{2-a}\). Similarly for \(Y\) with parameter \(c\). Hence \[|\Delta_{(a,c)}| = \binom{2}{a}\binom{n-2}{2-a} \cdot \binom{2}{c}\binom{n-2}{2-c}.\]
Evaluating all nine pairs gives the subdegrees listed in the table below.
| Orbit | \((a,c)\) | Description | Size |
|---|---|---|---|
| \(\Delta_1\) | \((2,1)\) | \(\{u_1,u_2\} = \{x_1,x_2\}\), \(\{v_1,v_2\}\) contains exactly one of \(y_1,y_2\) |
\(2(n-2)\) |
| \(\Delta_2\) | \((1,2)\) | \(\{u_1,u_2\}\) contains exactly one of \(x_1,x_2\), \(\{v_1,v_2\} = \{y_1,y_2\}\) |
\(2(n-2)\) |
| \(\Delta_3\) | \((2,0)\) | \(\{u_1,u_2\} = \{x_1,x_2\}\), \(\{v_1,v_2\} \cap \{y_1,y_2\} = \emptyset\) |
\(\dfrac{(n-2)(n-3)}{2}\) |
| \(\Delta_4\) | \((0,2)\) | \(\{u_1,u_2\} \cap \{x_1,x_2\} = \emptyset\), \(\{v_1,v_2\} = \{y_1,y_2\}\) |
\(\dfrac{(n-2)(n-3)}{2}\) |
| \(\Delta_5\) | \((1,1)\) | \(\{u_1,u_2\}\) contains exactly one of \(x_1,x_2\), \(\{v_1,v_2\}\) contains exactly one of \(y_1,y_2\) |
\(4(n-2)^2\) |
| \(\Delta_6\) | \((1,0)\) | \(\{u_1,u_2\}\) contains exactly one of \(x_1,x_2\), \(\{v_1,v_2\} \cap \{y_1,y_2\} = \emptyset\) |
\((n-2)^2(n-3)\) |
| \(\Delta_7\) | \((0,1)\) | \(\{u_1,u_2\} \cap \{x_1,x_2\} = \emptyset\), \(\{v_1,v_2\}\) contains exactly one of \(y_1,y_2\) |
\((n-2)^2(n-3)\) |
| \(\Delta_8\) | \((0,0)\) | \(\{u_1,u_2\} \cap \{x_1,x_2\} = \emptyset\), \(\{v_1,v_2\} \cap \{y_1,y_2\} = \emptyset\) |
\(\dfrac{(n-2)^2(n-3)^2}{4}\) |
The trivial suborbit \(\Delta_0\) corresponds to \((a,c)=(2,2)\) with size \(1\). The remaining eight are non‑trivial.
The identity \[\sum_{a=0}^{2}\sum_{c=0}^{2} \binom{2}{a}\binom{n-2}{2-a}\binom{2}{c}\binom{n-2}{2-c} = \binom{n}{2}^2 = |\Omega|,\] confirms that the nine suborbits partition \(\Omega\). For \(n\ge 5\), all are positive and the rank is exactly \(9\). The suborbits \(\Delta_1\) and \(\Delta_2\) are not equal; rather, their subdegree values are equal: \(|\Delta_1| = |\Delta_2| = 2(n-2)\), and similarly \(|\Delta_3|=|\Delta_4|=\frac{\left(n-2\right)\left(n-3\right)}{2},\) \(|\Delta_6|=|\Delta_7|=\left(n-2\right)^{^{2}}\left(n-3\right).\) \(\square\)
Remark 3.4. The subdegrees satisfy the strict inequalities \[1 < 2(n-2) < \frac{(n-2)(n-3)}{2} < 4(n-2)^2 < (n-2)^2(n-3) < \frac{(n-2)^2(n-3)^2}{4},\] for all \(n \ge 8\).
For \(5 \le n \le 7\), some of these inequalities reverse or become equalities. For example, when \(n = 5\), \(2(n-2) = 6\) and \(\frac{(n-2)(n-3)}{2} = 3\), so \(2(n-2) > \frac{(n-2)(n-3)}{2}\). The threshold \(n \ge 8\) is where all six distinct non-trivial subdegree values become strictly increasing as listed.
Theorem 3.5. Every suborbit \(\Delta_i\) (\(i = 0, 1, \dots, 8\)) is self-paired for all \(n \ge 5\),
Proof. By Definition 2.9, the trivial suborbit \(\Delta_0 = \{\alpha\}\) is always self-paired. For the remaining eight, we exhibit explicit group elements that establish self-pairing.
\(\Delta_1\) (type \((2,1)\)): Take \(\beta = (\{x_1, x_2\}, \{y_1, y_3\}) \in \Delta_1\). Let \(g = (e_{_{X}}, (y_1\; y_2\; y_3)) \in G\). Then \(g \cdot \beta = (\{x_1, x_2\}, \{y_1, y_2\}) = \alpha\), and \(g \cdot \alpha = (\{x_1, x_2\}, \{y_2, y_3\}) \in \Delta_1\). Hence \(\Delta_1^* = \Delta_1\).
\(\Delta_2\) (type \((1,2)\)): Take \(\beta = (\{x_1, x_3\}, \{y_1, y_2\}) \in \Delta_2\). Let \(g = ((x_1\; x_2\; x_3), e_{_{Y}}) \in G\). Then \(g \cdot \beta = \alpha\) and \[\begin{aligned} g \cdot \alpha = (\{x_2, x_3\}, \{y_1, y_2\}) \in \Delta_2. \end{aligned}\] Hence \(\Delta_2^* = \Delta_2\).
\(\Delta_3\) (type \((2,0)\)): Take \(\beta = (\{x_1, x_2\}, \{y_3, y_4\}) \in \Delta_3\). Let \(g = (e_{_{X}}, (y_1\; y_3)(y_2\; y_4)) \in G\) (a product of two disjoint transpositions, hence even). Then \(g \cdot \beta = \alpha\) and \(g \cdot \alpha = \beta \in \Delta_3\). Hence \(\Delta_3^* = \Delta_3\).
\(\Delta_4\) (type \((0,2)\)): Take \(\beta = (\{x_3, x_4\}, \{y_1, y_2\}) \in \Delta_4\). Let \(g = ((x_1\; x_3)(x_2\; x_4), e_{_{Y}}) \in G\). Then \(g \cdot \beta = \alpha\) and \(g \cdot \alpha = \beta \in \Delta_4\). Hence \(\Delta_4^* = \Delta_4\).
\(\Delta_5\) (type \((1,1)\)): Take \(\beta = (\{x_1, x_3\}, \{y_1, y_3\}) \in \Delta_5\). Let \(g = ((x_1\; x_2\; x_3), (y_1\; y_2\; y_3)) \in G\) (3-cycles are even permutations). Then \(g \cdot \beta = \alpha\) and \(g \cdot \alpha = (\{x_2, x_3\}, \{y_2, y_3\}) \in \Delta_5\). Hence \(\Delta_5^* = \Delta_5\).
\(\Delta_6\) (type \((1,0)\)): Take \(\beta = (\{x_1, x_3\}, \{y_3, y_4\}) \in \Delta_6\). Let \(g = ((x_1\; x_2\; x_3), (y_1\; y_3)(y_2\; y_4)) \in G\). Then \(g \cdot \beta = \alpha\) and \(g \cdot \alpha = (\{x_2, x_3\}, \{y_3, y_4\}) \in \Delta_6\). Hence \(\Delta_6^* = \Delta_6\).
\(\Delta_7\) (type \((0,1)\)): Take \(\beta = (\{x_3, x_4\}, \{y_1, y_3\}) \in \Delta_7\). Let \(g = ((x_1\; x_3)(x_2\; x_4), (y_1\; y_2\; y_3)) \in G\). Then \(g \cdot \beta = \alpha\) and \(g \cdot \alpha = (\{x_3, x_4\}, \{y_2, y_3\}) \in \Delta_7\). Hence \(\Delta_7^* = \Delta_7\).
\(\Delta_8\) (type \((0,0)\)): Take \(\beta = (\{x_3, x_4\}, \{y_3, y_4\}) \in \Delta_8\). Let \(g = ((x_1\; x_3)(x_2\; x_4), (y_1\; y_3)(y_2\; y_4)) \in G\). Then \(g \cdot \beta = \alpha\) and \(g \cdot \alpha = \beta \in \Delta_8\). Hence \(\Delta_8^* = \Delta_8\).
Since every non-trivial suborbit contains a point that can be mapped to \(\alpha\) by an element that also maps \(\alpha\) back into the same suborbit, each \(\Delta_i\) is self-paired. \(\square\)
For each nontrivial suborbit \(\Delta_i\) (\(i = 1, \dots, 8\)), the corresponding suborbital graph \(\Gamma_i\) has vertex set \(\Omega\) and, since \(\Delta_i\) is self-paired, undirected edges are defined globally by \[\{ (A,B), (C,D) \} \in E(\Gamma_i) \iff |A\cap C| = a \text{ and } |B\cap D| = c,\] where \((a,c)\) is the type of \(\Delta_i\). Because \(H=G_\alpha\) acts transitively on \(\Delta_i\), this definition is consistent for all vertices.
Edge condition: \(A = C\) and \(|B\cap D|=1\). For each fixed \(A\in X^{(2)}\), vertices \((A,B)\) form a copy of the Johnson graph \(J(n,2)\) on \(Y^{(2)}\), where \(B\) and \(D\) are adjacent if they intersect in exactly one element. \(J(n,2)\) is known to be connected for \(n\ge4\) and contains triangles for \(n\ge4\) (e.g., \(\{y_1,y_2\},\{y_1,y_3\},\{y_2,y_3\}\)). Hence \(\Gamma_1\) is disconnected with \(\binom{n}{2}\) components, each isomorphic to \(J(n,2)\), regular of degree \(2(n-2)\), girth \(3\) for \(n\ge4\).
Edge condition: \(|A\cap C|=1\) and \(B = D\). This is isomorphic to \(\Gamma_1\) by swapping coordinates, with components indexed by fixed \(B\in Y^{(2)}\), each \(J(n,2)\) on \(X^{(2)}\).
Edge condition: \(A = C\) and \(B\cap D = \emptyset\). For each fixed \(A\), vertices \((A,B)\) with \(B\cap\{y_1,y_2\}=\emptyset\) form the Kneser graph \(KG(n,2)\), where vertices are \(2\)-subsets of an \(n\)-set and edges connect disjoint subsets. \(KG(5,2)\) is the Petersen graph (girth \(5\)). For \(n\ge6\), \(KG(n,2)\) contains triangles (e.g., \(\{y_1,y_2\},\{y_3,y_4\},\{y_5,y_6\}\) are pairwise disjoint only if \(n\ge6\)). \(\Gamma_3\) is regular of degree \(\binom{n-2}{2}=\frac{(n-2)(n-3)}{2}\), disconnected with \(\binom{n}{2}\) components.
Edge condition: \(A\cap C = \emptyset\) and \(B = D\). This is isomorphic to \(\Gamma_3\) via coordinate swap, components indexed by \(B\in Y^{(2)}\), each \(KG(n,2)\) on \(X^{(2)}\).
Edge condition: \(|A\cap C| = 1\) and \(|B\cap D| = 1\). This graph is the tensor product (or direct product) \(J(n,2) \otimes J(n,2)\) of two Johnson graphs. Two vertices are adjacent iff they are adjacent in each coordinate independently. For \(n\ge5\), \(\Gamma_5\) is connected (both \(J(n,2)\) are connected and the product of connected graphs with at least one edge is connected). It contains triangles, e.g., \((\{x_1,x_2\},\{y_1,y_2\})\), \((\{x_1,x_3\},\{y_1,y_3\})\), \((\{x_1,x_4\},\{y_1,y_4\})\) form a triangle. Regular degree \(4(n-2)^2\) and girth \(3\).
Edge condition: \(|A\cap C| = 1\) and \(B\cap D = \emptyset\). This graph is isomorphic to \(J(n,2) \otimes KG(n,2)\). For \(n\ge5\), both factors have degree \(\ge2\), so the product has degree \((2(n-2))\cdot \binom{n-2}{2} = (n-2)^2(n-3) \ge 12\) for \(n\ge5\), hence it contains cycles (finite regular graphs of degree \(\ge2\) always contain cycles). Thus the claim that \(\Gamma_6\) is acyclic is false; it contains many cycles. Connectivity: For \(n\ge5\), both \(J(n,2)\) and \(KG(n,2)\) are connected, so their tensor product is connected. The girth is \(4\) for \(n=4,5\) and for \(n\ge6\), \(KG(n,2)\) contains triangles, so the girth is \(3\).
Edge condition: \(A\cap C = \emptyset\) and \(|B\cap D| = 1\). This graph is isomorphic to \(\Gamma_6\) by swapping coordinates, i.e., \(KG(n,2) \otimes J(n,2)\).
Edge condition: \(A\cap C = \emptyset\) and \(B\cap D = \emptyset\). This graph is the tensor product \(KG(n,2) \otimes KG(n,2)\). Both factors are Kneser graphs, which are connected for \(n\ge5\) (except \(n=5\) where Petersen is connected). The product is therefore connected for \(n\ge5\). Actually, tensor product of two connected non-bipartite graphs is connected; \(KG(n,2)\) is not bipartite for \(n\ge5\) (it contains odd cycles). Hence \(\Gamma_8\) is connected for \(n\ge5\). Its degree is \(\binom{n-2}{2}^2\). Girth: For \(n=5\), each factor is Petersen (girth \(5\)), so product has girth \(5\); for \(n\ge6\), each factor contains triangles, so product has girth \(3\). Regular, connected.
Proposition 3.6. \(\Gamma_3 \cong \Gamma_4\) and \(\Gamma_3 \cong \Gamma_4\) and \(\Gamma_6 \cong \Gamma_7\) via the map \(\phi((A,B)) = (B,A)\) after fixing a bijection between \(X\) and \(Y\).
In this paper, we have initiated the systematic study of the action of the direct product \(G = S_n \times A_n\) on the Cartesian product \(\Omega = X^{(2)} \times Y^{(2)}\), where \(X^{(2)}\) and \(Y^{(2)}\) are disjoint \(2\)-element subsets. Our main findings are:
Transitivity and imprimitivity: The action is transitive for all \(n \ge 2\) (Theorem 3.1) and imprimitive for all \(n \ge 3\) (Theorem 3.2).
Rank and subdegrees: For \(n \ge 5\), the action has rank 9 with subdegrees given explicitly in Theorem 3.3. The eight non-trivial subdegrees arise naturally from the intersection parameters \((a, c) \in \{0,1,2\}^2 \setminus \{(2,2)\}\).
Self-pairing: Every suborbit is self-paired for \(n \ge 5\) (Theorem 3.5), implying that the associated suborbital graphs are undirected.
Suborbital graphs: The eight non-trivial suborbital graphs \(\Gamma_1,\dots,\Gamma_8\) exhibit a range of properties: some are connected with girth 3 or 4, others are disconnected or acyclic, and all are regular with degrees given by the corresponding subdegrees. Isomorphisms \(\Gamma_3 \cong \Gamma_4\) and \(\Gamma_6 \cong \Gamma_7\) are established.
The rank-9 decomposition is notable because most classical actions of symmetric and alternating groups on subset-type objects yield rank 3 or rank \(r+1\). The appearance of nine suborbits reflects the interaction between the two independent coordinates and the parity restriction on the second factor.
Several natural extensions of this work present themselves:
(a) Generalization to \(X^{(r)} \times Y^{(s)}\): Replace 2-subsets with \(r\)-subsets and \(s\)-subsets, where \(r, s \ge 2\). The number of suborbits would become \((r+1)(s+1)\) in the generic case, with subdegrees given by products of binomial coefficients.
(b) Primitivity criteria for other direct products: For which subgroups \(H \le S_n\) and \(K \le A_n\) does the action of \(H \times K\) on \(X^{(2)} \times Y^{(2)}\) become primitive? The block structure identified here suggests that primitivity fails whenever \(H\) preserves a proper subset of \(X^{(2)}\).
(c) Characterization of the graph families: The suborbital graphs \(\Gamma_i\) may belong to known families (e.g., Johnson graphs, Kneser graphs, or tensor products thereof). Determining their place in graph taxonomy could yield further insights.
(d) Algebraic properties: The association scheme generated by these suborbital graphs has rank 9. Its intersection numbers and eigenvalues could be computed explicitly.
These directions are currently under investigation and will be reported in future work.
The first author gratefully acknowledges the German Academic Exchange Service (DAAD) for its financial support of his doctoral studies.