On the bottleneck assignment problem

In this paper, a new approach for solving the bottleneck assignment problem is presented. The problem is treated as a special class of permutation problems which we call max-min permutation problems. By defining a suitable neighborhood system in the space of permutations and designating certain permutations as critical solutions, it is shown that any critical solution yields a global optimum. This theorem is then used as a basis to develop a general method to solve max-min permutation problems.This work was carried out by the junior author while holding a Purdue University Fellowship.     

Quantum immanants and higher Capelli identities

We consider some remarkable central elements of the universal enveloping algebraU(gl(n)) which we call quantum immanants. We express them in terms of generatorsE _ij ofU(gl(n)) and as differential operators on the space of matrices These expressions are a direct generalization of the classical Capelli identities. They result in many nontrivial properties of quantum immanants. The author is supported by the International Science Foundation and the Russian Fundamental Research Foundation.     

A state-space approach to quantum permutations

In this exposition of quantum permutation groups, an alternative to the ‘Gelfand picture’ of compact quantum groups is proposed. This point of view is inspired by algebraic quantum mechanics and interprets the states of an algebra of continuous functions on a quantum permutation group as quantum permutations. This interpretation allows talk of an element of a quantum permutation group, and allows a clear understanding of the difference between deterministic, random, and quantum permutations. The interpretation is illustrated by various quantum permutation group phenomena.     

A linear assignment approach for the least-squares protein morphing problem

This work addresses the computation of free-energy differences between protein conformations by using morphing (i.e., transformation) of a source conformation into a target conformation. To enhance the morphing procedure, we employ permutations of atoms: we seek to find the permutation σ that minimizes the mean-square distance traveled by the atoms. Instead of performing this combinatorial search in the space of permutations, we show that the best permutation can be found by solving a linear assignment problem. We demonstrate that the use of such optimal permutations significantly improves the efficiency of the free-energy computation.     

Hardy空间上一类$m$-复对称Toeplitz算子

本文主要研究Toeplitz算子相对于一对置换的共轭算子是2-复对称的充要条件. 首先在经典的Hardy空间上介绍一类被称为一对置换的共轭算子, 其次完整地刻画了在这类共轭算子下Toeplitz算子是2-复对称的结构, 利用Toeplitz算子在Hardy空间的经典正规正交基下的矩阵表示来刻画2-复对称Toeplitz算子. 最后对于Toeplitz算子分别补充前提$f_n=-f_{-n}$和$f_n=f_{-n}$, 得到了更简化的结果. 在第二个前提下, 研究Toeplitz算子的3-复对称性, 得到$T_f$关于$C_{(i,j)}$是3-CSO的结果和是2-CSO相同.     

The Enumeration of Maximally Clustered Permutations

The maximally clustered permutations are characterized by avoiding the classical permutation patterns {3421, 4312, 4321}. This class contains the freely braided permutations and the fully commutative permutations. In this work, we show that the generating functions for certain fully commutative pattern classes can be transformed to give generating functions for the corresponding freely braided and maximally clustered pattern classes. Moreover, this transformation of generating functions is rational. As a result, we obtain enumerative formulas for the pattern classes mentioned above as well as the corresponding hexagon-avoiding pattern classes where the hexagon-avoiding permutations are characterized by avoiding {46718235, 46781235, 56718234, 56781234}.     

Light tails and the Hermitian dual polar graphs

This paper investigates ciphers where the set of encryption functions is identical to the set of decryption functions, which we call reflection ciphers. Equivalently, there exists a permutation P, named the coupling permutation, such that decryption under k corresponds to encryption under P(k). We study the necessary properties for this coupling permutation. Special care has to be taken of some related-key distinguishers since, in the context of reflection ciphers, they may provide attacks in the single-key setting. We then derive some criteria for constructing secure reflection ciphers and analyze the security properties of different families of coupling permutations. Finally, we concentrate on the case of reflection block ciphers and, as an illustration, we provide concrete examples of key schedules corresponding to several coupling permutations, which lead to new variants of the block cipher prince.     

Coding for locality in reconstructing permutations

The problem of storing permutations in a distributed manner arises in several common scenarios, such as efficient updates of a large, encrypted, or compressed data set. This problem may be addressed in either a combinatorial or a coding approach. The former approach boils down to presenting large sets of permutations with locality, that is, any symbol of the permutation can be computed from a small set of other symbols. In the latter approach, a permutation may be coded in order to achieve locality. Both approaches must present low query complexity to allow the user to find an element efficiently. We discuss both approaches, and give a particular focus to the combinatorial one. In the combinatorial approach, we provide upper and lower bounds for the maximal size of a set of permutations with locality, and provide several simple constructions which attain the upper bound. In cases where the upper bound is not attained, we provide alternative constructions using a variety of tools, such as Reed-Solomon codes, permutation polynomials, and multi-permutations. In addition, several low-rate constructions of particular interest are discussed. In the coding approach we discuss an alternative representation of permutations, present a paradigm for supporting arbitrary powers of the stored permutation, and conclude with a proof of concept that permutations may be stored more efficiently than ordinary strings over the same alphabet.     

F2^n上4次正形置换多项式的形式与计数

分组峦码是现代密码学中一个重要的研究分支，而置换理论在分组密码中有重要的地位．199j年，美国Tcledyne电子技术公司的Lothrop Mittenthal博士提出了一种置换，即正形置换．止形置换是一类完全映射，完全映射是由Mann在1942年研究正交拉丁方的构造时引入的，其具有良好的密码学性质（良好的扩散性和完令平衡性），因此，正形置换常用来构造密码系统的算法，研究正形置换也就非常订必要．本文根据文章[1]的方法讨论了F2^n（n=4，5）上的4次正形置换多项式的形式与计数，至于n〉5的情形我们将在以后的篇章中继续讨论．     

Packing sets of patterns

Packing density is a permutation occurrence statistic which describes the maximal number of permutations of a given type that can occur in another permutation. In this article we focus on containment of sets of permutations. Although this question has been tangentially considered previously, this is the first article focusing exclusively on it. We find the packing density for various special sets of permutations and study permutation and pattern co-occurrence.     

On natural isomorphisms of cycle permutation graphs

Two problems are approached in this paper. Given a permutation onn elements, which permutations onn elements yield cycle permutation graphs isomorphic to the cycle permutation graph yielded by the given permutation? And, given two cycle permutation graphs, are they isomorphic? Here the author deals only with natural isomorphisms, those isomorphisms which map the outer and inner cycles of one cycle permutation graph to the outer and inner cycles of another cycle permutation graph. A theorem is stated which then allows the construction of the set of permutations which yield cycle permutation graphs isomorphic to a given cycle permutation graph by a natural isomorphism. Another theorem is presented which finds the number of such permutations through the use of groups of symmetry of certain drawings of cycles in the plane. These drawings are also used to determine whether two given cycle permutation graphs are isomorphic by a natural isomorphism. These two methods are then illustrated by using them to solve the first problem, restricted to natural isomorphism, for a certain class of cycle permutation graphs.     

Restricted colored permutations and Chebyshev polynomials

Several authors have examined connections between restricted permutations and Chebyshev polynomials of the second kind. In this paper we prove analogues of these results for colored permutations. First we define a distinguished set of length two and length three patterns, which contains only 312 when just one color is used. Then we give a recursive procedure for computing the generating function for the colored permutations which avoid this distinguished set and any set of additional patterns, which we use to find a new set of signed permutations counted by the Catalan numbers and a new set of signed permutations counted by the large Schröder numbers. We go on to use this result to compute the generating functions for colored permutations which avoid our distinguished set and any layered permutation with three or fewer layers. We express these generating functions in terms of Chebyshev polynomials of the second kind and we show that they are special cases of generating functions for involutions which avoid 3412 and a layered permutation.     

A class of permutation quadrinomials

In this paper, we investigate the permutation behavior of a class of quadrinomials. Each term of these quadrinomials has a Niho-type exponent, and two sets of coefficient triples making the quadrinomials to be permutations are obtained. We use a substitution to transform the permutation problem into the root distribution problem in the unit circle of certain quadratic and cubic equations.     

On generation of permutations through decomposition of symmetric groups into cosets

A hardware-oriented algorithm for generating permutations is presented that takes as a theoretic base an iterative decomposition of the symmetric groupS _n into cosets. It generates permutations in a new order. Simple ranking and unranking algorithms are given. The construction of a permutation generator is proposed which contains a cellular permutation network as a main component. The application of the permutation generator for solving a class of combinatorial problems on parallel computers is suggested.     

Simple permutations and pattern restricted permutations

A simple permutation is one that does not map any non-trivial interval onto an interval. It is shown that, if the number of simple permutations in a pattern restricted class of permutations is finite, the class has an algebraic generating function and is defined by a finite set of restrictions. Some partial results on classes with an infinite number of simple permutations are given. Examples of results obtainable by the same techniques are given; in particular it is shown that every pattern restricted class properly contained in the 132-avoiding permutations has a rational generating function.     

A criterion for the adjacency of vertices of polytopes generated by subsets of symmetric groups

We propose a characterization of the adjacency of vertices in the class of permutation polytopes generated by arbitrary subsets of symmetric groups. In particular, this class contains polytopes for the well-known classical problems, such as the assignment problem, 2-and 3-combinations, the traveling salesman problem and their various modifications. Up to now, the problem of vertex adjacency has been studied for a single polytope only. In the present paper, we obtain, for general permutation polytopes, necessary and sufficient conditions that guarantee that two given vertices are adjacent (or not) to each other. The conditions are formulated in terms of permutations and of the solvability of certain special systems of linear equations. The presently known adjacency criteria for vertices of polytopes for the assignment problem are simple corollaries of our conditions. The latter allow us to develop a general algorithmic scheme for recognizing vertex adjacency of a general permutation polytope and estimate its complexity.     

Path Integrals in Noncommutative Quantum Mechanics

We consider an extension of the Feynman path integral to the quantum mechanics of noncommuting spatial coordinates and formulate the corresponding formalism for noncommutative classical dynamics related to quadratic Lagrangians (Hamiltonians). The basis of our approach is that a quantum mechanical system with a noncommutative configuration space can be regarded as another effective system with commuting spatial coordinates. Because the path integral for quadratic Lagrangians is exactly solvable and a general formula for the probability amplitude exists, we restrict our research to this class of Lagrangians. We find a general relation between quadratic Lagrangians in their commutative and noncommutative regimes and present the corresponding noncommutative path integral. This method is illustrated with two quantum mechanical systems in the noncommutative plane: a particle in a constant field and a harmonic oscillator.     

Non-nudgable subgroups of permutations

Motivated by a problem from behavioral economics, we study subgroups of permutation groups that have a certain strong symmetry. Given a fixed permutation, consider the set of all permutations with disjoint inversion sets. The group is called non-nudgable if the cardinality of this set always remains the same when replacing the initial permutation with its inverse. It is called nudgable otherwise. We show that all full permutation groups, standard dihedral groups, half of the alternating groups, and any abelian subgroup are non-nudgable. In the right probabilistic sense, it is thus quite likely that a randomly generated subgroup is non-nudgable. However, the other half of the alternating groups are nudgable. We also construct a smallest possible nudgable group, a 6-element subgroup of the permutation group on 4 elements.     

F_2~n上4次正形置换多项式的形式与计数

分组密码是现代密码学中一个重要的研究分支,而置换理论在分组密码中有重要的地位.1995年,美国Teledyne电子技术公司的Lothrop Mittenthal博士提出了一种置换,即正形置换.正形置换是一类完全映射,完全映射是由Mann在1942年研究正交拉丁方的构造时引入的,其具有良好的密码学性质(良好的扩散性和完全平衡性),因此,正形置换常用来构造密码系统的算法,研究正形置换也就非常有必要.本文根据文章[1]的方法讨论了F2n(n=4,5)上的4次正形置换多项式的形式与计数,至于n5的情形我们将在以后的篇章中继续讨论.     

A note on permutation regularity

The existence of a small partition of a combinatorial structure into random-like subparts, a so-called regular partition, has proven to be very useful in the study of extremal problems, and has deep algorithmic consequences. The main result in this direction is the renowned Szemerédi Regularity Lemma [Szemerédi, E., Regular partitions of graphs, Colloques Internationaux C.N.R.S. No: 260 – Problèmes Combinatoires et Théorie des Graphes, Orsay (1976), 399–401] in graph theory. In this note, we are concerned with regularity in permutations: we show that every permutation of a sufficiently large set has a regular partition into a small number of intervals. This refines the partitioning given by Cooper [Cooper, J., A permutation regularity lemma, The Electronic Journal of Combinatorics 13 (2006), 20pp.], which required an additional non-interval exceptional class. We also introduce a distance between permutations that plays an important role in the study of convergence of a permutation sequence.