Latin bitrades derived from groups

A Latin bitrade is a pair of partial Latin squares which are disjoint, occupy the same set of non-empty cells, and whose corresponding rows and columns contain the same set of entries. In [A. Drápal, On geometrical structure and construction of Latin trades, Advances in Geometry (in press)] it is shown that a Latin bitrade may be thought of as three derangements of the same set, whose product is the identity and whose cycles pairwise have at most one point in common. By letting a group act on itself by right translation, we show how some Latin bitrades may be derived directly from groups. Properties of Latin bitrades such as homogeneity, minimality (via thinness) and orthogonality may also be encoded succinctly within the group structure. We apply the construction to some well-known groups, constructing previously unknown Latin bitrades. In particular, we show the existence of minimal, k-homogeneous Latin bitrades for each odd k≥3. In some cases these are the smallest known such examples.     

Short proofs for cut-and-paste sorting of permutations

We consider the problem of determining the maximum number of moves required to sort a permutation of [n] using cut-and-paste operations, in which a segment is cut out and then pasted into the remaining string, possibly reversed. We give short proofs that every permutation of [n] can be transformed to the identity in at most ⌊2n/3⌋ such moves and that some permutations require at least ⌊n/2⌋ moves.     

The Round Functions of Cryptosystem PGM Generate the Symmetric Group

S. S. Magliveras et al. have described symmetric and public key cryptosystems based on logarithmic signatures (also known as group bases) for finite permutation groups. In this paper we show that if G is a nontrivial finite group which is not cyclic of order a prime, or the square of a prime, then the round (or encryption) functions of these systems, that are the permutations of G induced by the exact-transversal logarithmic signatures (also known as transversal group bases), generate the full symmetric group on G. This answers a question of S. S. Magliveras, D. R. Stinson and Tran van Trung. AMS Classification:94A60, 20B15, 20B20     

Reduced decompositions and permutation patterns

Billey, Jockusch, and Stanley characterized 321-avoiding permutations by a property of their reduced decompositions. This paper generalizes that result with a detailed study of permutations via their reduced decompositions and the notion of pattern containment. These techniques are used to prove a new characterization of vexillary permutations in terms of their principal dual order ideals in a particular poset. Additionally, the combined frameworks yield several new results about the commutation classes of a permutation. In particular, these describe structural aspects of the corresponding graph of the classes and the zonotopal tilings of a polygon defined by Elnitsky that is associated with the permutation.     

CONSTRUCTION OF COMPACTLY SUPPORTED BIVARIATE ORTHOGONAL WAVELETS BY UNIVARIATE ORTHOGONAL WAVELETS

After some permutation of conjugate quadrature filter, new conjugate quadrature filters can be derived. In terms of this permutation, an approach is developed for constructing compactly supported bivariate orthogonal wavelets from univariate orthogonal wavelets. Non-separable orthogonal wavelets can be achieved. To demonstrate this method, an example is given.     

Intersections of nest algebras in finite dimensions

If are maximal nests on a finite-dimensional Hilbert space H, the dimension of the intersection of the corresponding nest algebras is at least dim H. On the other hand, there are three maximal nests whose nest algebras intersect in the scalar operators. The dimension of the intersection of two nest algebras (corresponding to maximal nests) can be of any integer value from n to n(n+1)/2, where n=dim H. For any two maximal nests there exists a basis {f₁,f₂,…,f_n} of H and a permutation π such that and where M_i=  span{f₁,f₂,…,f_i} and N_i= span{f_π(1),f_π(2),…,f_π(i)}. The intersection of the corresponding nest algebras has minimum dimension, namely dim H, precisely when π(j)=n−j+1,1jn. Those algebras which are upper-triangular matrix incidence algebras, relative to some basis, can be characterised as intersections of certain nest algebras.     

有限Abel群上子集等价类的计数

设G为一有限Abel群，|G|=v,D1,D2是G的两个子集，如果存在t∈Zv,(t,v)=1,s∈G使D1＝tD2 s，则称D1与D2是等价的。文中给出了G的k-子集等价类的计数公式，同时也给出了G的的所有子集等价类的计数公式。     

Counting descent pairs with prescribed tops and bottoms

Given sets X and Y of positive integers and a permutation σ=σ₁σ₂?σn∈Sn, an (X,Y)-descent of σ is a descent pair σi>σi+1 whose “top” σi is in X and whose “bottom” σi+1 is in Y. We give two formulas for the number of σ∈Sn with s(X,Y)-descents. is also shown to be a hit number of a certain Ferrers board. This work generalizes results of Kitaev and Remmel [S. Kitaev, J. Remmel, Classifying descents according to parity, math.CO/0508570; S. Kitaev, J. Remmel, Classifying descents according to equivalence , math.CO/0604455] on counting descent pairs whose top (or bottom) is equal to .     

Necessary conditions for reversed Dickson polynomials of the second kind to be permutational

In this paper, we present several necessary conditions for the reversed Dickson polynomial $E_n(1,x)$ of the second kind to be a permutation of ${\mathbb{F}}_q$. In particular, we give explicit evaluation of the sum ${\sum }_{a\in {\mathbb{F}}_q}{E}_n(1,a)$.