The pinnacle set of a permutation

The peak set of a permutation records the indices of its peaks. These sets have been studied in a variety of contexts, including recent work by Billey, Burdzy, and Sagan, which enumerated permutations with prescribed peak sets. In this article, we look at a natural analogue of the peak set of a permutation, instead recording the values of the peaks. We define the “pinnacle set” of a permutation $w$ to be the set $\{w\left(i\right):i\text{ is a peak of}w\}$. Although peak sets and pinnacle sets mark the same phenomenon for a given permutation, the behaviors of these sets differ in notable ways as distributions over the symmetric group. In the work below, we characterize admissible pinnacle sets and study various enumerative questions related to these objects.     

The probability of generating a permutation group

It is well known that a permutation group of degree can be generated by elements. In this paper we study the asymptotic behavior of the probability of generating a permutation group of degree n with elements. In particular we prove that if n is large enough and elements generate a permutation group G of degree n modulo G G ², then almost certainly these elements generate G itself. Received: 2 January 2002     

The structure of the centralizer of a permutation

Relative to the symmetric groups S_n the structure of centralizers of permutations are known as direct products of certain general wreath products. A recent generalization of the cycle notation for partial one-one transformations (charts) is applied to show that relative to the symmetric inverse semigroups C_n the structure of centralizers of permutations are also direct products of certain subsemigroups of a wreath product, and this latter wreath product includes the former as a subgroup. A necessary and sufficient condition is given for two charts to commute and the approach for the C_n-case parallels and generalizes the one for the S_n-case. As a result, the C_n-case yields the standard known characterizations of commuting permutations, as well as formulas for the orders of centralizers as corollaries. It is an open problem to extend these results to the centralizers of arbitrary charts in C_n. This research was partially supported by a Mary Washington College Faculty Development Grant.     

The permutation class group of a finite group

Analogously to the projective class group, the permutation class group of a finite group π can be defined as the group of equivalence classes of direct summands of integral permutation modules modulo permutation modules. It is shown that this group behaves nicely with respect to localization and completion, which then is used to prove that contrary to the projective class group - it is not always a torsion group. More precisely, the rank of the permutation class of group is computed.     

The characteristic polynomial of a random permutation matrix

We establish a central limit theorem for the logarithm of the characteristic polynomial of a random permutation matrix. We relate this result to a central limit theorem of Wieand for the counting function for the eigenvalues lying in some interval on the unit circle.     

The L-sharp permutation groups

An answer is given to a problem proposed by Bannai and Ito for {l,l+s,l+s+t}-sharp permutation group, and the result is used to determine L-sharp groups for L={l,l+1,l+3}and{l,l+2,l+3}.     

The absolute order of a permutation representation of a Coxeter group

A permutation representation of a Coxeter group W naturally defines an absolute order. This family of partial orders (which includes the absolute order on W) is introduced and studied in this paper. Conditions under which the associated rank generating polynomial divides the rank generating polynomial of the absolute order on W are investigated when W is finite. Several examples, including a symmetric group action on perfect matchings, are discussed. As an application, a well-behaved absolute order on the alternating subgroup of W is defined.     

The distribution of the root degree of a random permutation

Given a permutation ω of {1, …, n}, let R(ω) be the root degree of ω, i.e. the smallest (prime) integer r such that there is a permutation σ with ω = σ ^r . We show that, for ω chosen uniformly at random, R(ω) = (lnlnn − 3lnlnln n + O ^p (1))⁻¹ lnn, and find the limiting distribution of the remainder term. Research supported in part by NSF grants CCR-0225610, DMS-0505550 and ARO grant W911NF-06-1-0076. Research supported by NSF grant DMS-0406024.     

The number of labeled graphs placeable by a given permutation

Let S be a finite set and σ a permutation on S. The permutation σ* on the set of 2-subsets of S is naturally induced by σ. Suppose G is a graph and V(G), E(G) are the vertex set, the edge set, respectively. Let V(G) = S. If E(G) and σ*(E(G)), the image of E(G) by σ*, have no common element, then G is said to be placeable by σ. This notion is generalized as follows. If any two sets of {E(G), (σ¹)*(E(G)),…,(σ^l−1)* (E(G))} have no common element, then G is said to be I-placeable by σ. In this paper, we count the number of labeled graphs which are I-placeable by a given permutation. At first, we introduce the interspaced Ith Fibonacci and Lucas numbers. When I = 2 these numbers are the ordinary Fibonacci and Lucas numbers. It is known that the Fibonacci and Lucas numbers are rounded powers. We show that the interspaced Ith Fibonacci and Lucas numbers are also rounded powers when I = 3. Next, we show the number of labeled graphs which are I-placeable by a given permutation is a product of the interspaced Ith Lucas numbers. Finally, using a property of the generalized binomial series, we count the number of labeled graphs of size k which are I-placeable by σ. © 1996 John Wiley & Sons, Inc.     

Generating a random cyclic permutation

We prove correct an algorithm that, givenn>0, stores in arrayb[0..n–1] a random cyclic permutation of the integers in 0..n–1, with each cyclic permutation having equal probability of being stored inb. The algorithm was developed by Sattolo; our contribution is to present a more convincing proof using standard program-proving methods.Dedicated to Peter Naur on the occasion of his 60th birthdayThis research was supported by the NSF under grant DCR-8320274.Visiting Cornell from the Computer Science Department, Jiangxi Normal University, Nanchang, People's Republic of China.     

Convex solution of a permutation problem

In this paper, we show that a problem of finding a permuted version of k vectors from R^N such that they belong to a prescribed rank r subset, can be solved by convex optimization. We prove that under certain generic conditions, the wanted permutation matrix is unique in the convex set of doubly-stochastic matrices. In particular, this implies a solution of the classical correspondence problem of finding a permutation that transforms one collection of points in R^k into the another one. Solutions to these problems have a wide set of applications in Engineering and Computer Science.     

Characteristic polynomials of a permutation representation

Let G be a finite group. To each permutation representation (G, X) of G and class function χ of G we associate the χ-characteristic polynomialg_χ(x) of (G, X) which is a polynomial in one variable with complex numbers as coefficients. The coefficients of g_χ(x) are investigated in terms of the “exterior powers” of (G, X). If χ is the principal character 1_G of G, the coefficients of g_χ(x) are non-negative integers; and if furthermore G has odd order, the kth coefficient is the number of orbits of G acting on the subsets of X with k elements. Quadratic and linear relations among the exterior powers of (G, X) have been derived and it is shown how the polynomial g_χ(x) can be computed from the cycle index of (G, X).     

The characteristic polynomial of a random permutation matrix at different points

We consider the logarithm of the characteristic polynomial of random permutation matrices, evaluated on a finite set of different points. The permutations are chosen with respect to the Ewens distribution on the symmetric group. We show that the behavior at different points is independent in the limit and are asymptotically normal. Our methods enable us to study also the wreath product of permutation matrices and diagonal matrices with i.i.d. entries and more general class functions on the symmetric group with a multiplicative structure.     

The primitive permutation groups of degree 2 a ·3 b

In this paper, we give a complete classification of all finite simple groups with maximal subgroups of index n, where n = 2^a·3^b for a, b≧ 1. As a consequence, for such n, all primitive permutation groups of degree n are given. The motivation of this work comes also from a study of Cayley graphs of certain valency on a finite simple group. Received: 9 March 2005