Multiply transitivity of perfect 1-codes in symmetric groups (Q1066864)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Multiply transitivity of perfect 1-codes in symmetric groups |
scientific article |
Statements
Multiply transitivity of perfect 1-codes in symmetric groups (English)
0 references
1985
0 references
Let n be a positive integer, \(S_ n\) be the symmetric group on \(X=\{1,...,n\}\), T be the set of all transpositions in \(S_ n\) and \(U=T\cup \{1\}\). A subset Z of \(S_ n\) is a 1-code in \(S_ n\) if \(Ug\cap Uh=\emptyset\) holds for any distinct two elements g and h in Z. A 1-code Z in \(S_ n\) is perfect if \(S_ n=\cup_{g\in Z}Ug\). Let \(X^{(k)}\) be the set of all ordered k-tuples of distinct elements of X. We consider the natural action of \(S_ n\) on \(X^{(k)}\). A subset Z of \(S_ n\) is k-transitive if the following condition holds. For any x and y in \(X^{(k)}\), there exists some z in Z that moves x to y, and the number of such elements in Z is a constant that is independent of the choice of x and y. Theorem. Perfect 1-codes in symmetric group of degree n are k-transitive for \(0\leq k<(n/2)\). Corollary. If \(S_ n\) has a perfect 1-code then \(\left( \begin{matrix} n\\ 2\end{matrix} \right)+1\) divides \([(n/2)+1]!\).
0 references
perfect code
0 references
perfect one-code
0 references
k-transitive
0 references
regular graph
0 references