Complementary permutations for abelian groups

Summary LetG be an additively written abelian group and leth: G G be a given function. M. Hall Jr. (1952) and L. Fuchs (1958) already answered the following question. For what functionsh: G G does the functional equation(x) + (x) = h(x) (x G) have as its solution a pair of permutations and ofG? In this paper, we give explicit constructions of such a pair, in a number of cases, in particular whenh(x) x andG is finite. We further determine the finite groupsG where the latter, can be chosen to be automorphisms.In the case whereG is an infinite topological group, we study in how far and can be chosen as Borel measurable permutations, given thath: G G itself is Borel measurable.     

Counting involutory, unimodal, and alternating signed permutations

In this work we count the number of involutory, unimodal, and alternating elements of the group of signed permutations B_n, and the group of even-signed permutations D_n. Recurrence relations, generating functions, and explicit formulas of the enumerating sequences are given.     

Restricted signed permutations counted by the Schröder numbers

Gire, West, and Kremer have found ten classes of restricted permutations counted by the large Schröder numbers, no two of which are trivially Wilf-equivalent. In this paper we enumerate eleven classes of restricted signed permutations counted by the large Schröder numbers, no two of which are trivially Wilf-equivalent. We obtain five of these enumerations by elementary methods, five by displaying isomorphisms with the classical Schröder generating tree, and one by giving an isomorphism with a new Schröder generating tree. When combined with a result of Egge and a computer search, this completes the classification of restricted signed permutations counted by the large Schröder numbers in which the set of restrictions consists of two patterns of length 2 and two of length 3.     

On reconstruction of signed permutations distorted by reversal errors

The problem of reconstructing signed permutations on n elements from their erroneous patterns distorted by reversal errors is considered in this paper. A reversal is the operation of taking a segment of the signed permutation, reversing it, and flipping the signs of its elements. The reversal metric is defined as the least number of reversals transforming one signed permutation into another. It is proved that for any $n?2$ an arbitrary signed permutation is uniquely reconstructible from three distinct signed permutations at reversal distance at most one from the signed permutation. The proposed approach is based on the investigation of structural properties of a Cayley graph $G_{2n}$ whose vertices form a subgroup of the symmetric group ${\mathrm{Sym}}_{2n}$. It is also proved that an arbitrary signed permutation is reconstructible from two distinct signed permutations with probability $p_2～\frac{1}{3}$ as $n\to \infty$. In the case of at most two reversal errors it is shown that at least $n(n+1)$ distinct erroneous patterns are required in order to reconstruct an arbitrary signed permutation.     

The lawlessness of groups of finitary permutations

Archiv der Mathematik -     

Abelian groups of monotonic permutations

We study m-transitive representations of Abelian m-groups. Representations are found which mimic a variety A {\mathcal A} of all Abelian m-groups and a variety J {\mathcal J} of m-groups defined by an identity x _*  = x ⁻¹.     

On random permutations of finite groups

Given a finite abelian group G,  consider a uniformly random permutation of the set of all elements of G. Compute the difference of each pair of consecutive elements along the permutation. What is the number of occurrences of \(h\in G\setminus \{0\}\) in this sequence of differences? How do these numbers of occurrences behave for several group elements simultaneously? Can we get similar results for non-abelian G? How do the answers change if differences are replaced by sums? In this paper, we answer these questions. Moreover, we formulate analogous results in a general combinatorial setting.

     

Jacobi identity for groups

In group calculations connected with multiple commutators, it may become necessary to reduce all the commutators to the left-normalized form (with respect to the arrangement of parentheses). To this end, an identity representing a natural extension of the Jacobi identity in Lie algebras is given. The identity is proved up to elements of the tenth term of the central filtration.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 46, pp. 53–58, 1974.     

Wreath products of the groups of monotone permutations

We introduce the concept of wreath product of the m-groups of permutations and prove that an m-transitive group of permutations with an m-congruence is embeddable into the wreath product of the suitable m-transitive m-groups of permutations. This implies that an arbitrary m-transitive group in the product of two varieties of m-groups embeds into the wreath product of the suitable m-transitive groups of these varieties.     

Odd length for even hyperoctahedral groups and signed generating functions

We define a new statistic on the even hyperoctahedral groups which is a natural analogue of the odd length statistic recently defined and studied on Coxeter groups of types $A$ and $B$. We compute the signed (by length) generating function of this statistic over the whole group and over its maximal and some other quotients and show that it always factors nicely. We also present some conjectures.     

On some properties of min-wise independent families and groups of permutations

Informally, a family of permutations is k-restricted min-wise independent if for any with |X| ⩽ k, each x ∈ X has an equal chance of being mapped to the minimum among π(X). In the second section of this paper, the connection of min-wise independent families of permutations and independence on lth minimum is studied. In the third section, we present a method of constructing a (k + 1)-restricted min-wise independent family from a k-restricted min-wise independent family when k is odd. As a corollary, we improve the existing upper bound on the minimum size of a 4-restricted min-wise independent family. In the last section, we consider min-wise independent groups of permutations. Bibliography: 12 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 316, 2004, pp. 30–41.