Multiple Recurrence in Quasirandom Groups

We establish a new mixing theorem for quasirandom groups (finite groups with no low-dimensional unitary representations) G which, informally speaking, asserts that if g, x are drawn uniformly at random from G, then the quadruple (g, x, gx, xg) behaves like a random tuple in G ⁴, subject to the obvious constraint that gx and xg are conjugate to each other. The proof is non-elementary, proceeding by first using an ultraproduct construction to replace the finitary claim on quasirandom groups with an infinitary analogue concerning a limiting group object that we call an ultra quasirandom group, and then using the machinery of idempotent ultrafilters to establish the required mixing property for such groups. Some simpler recurrence theorems (involving tuples such as (x, gx, xg)) are also presented, as well as some further discussion of specific examples of ultra quasirandom groups.     

Symmetric Permutations Avoiding Two Patterns

Symmetric pattern-avoiding permutations are restricted permutations which are invariant under actions of certain subgroups of D ₄, the symmetry group of a square. We examine pattern-avoiding permutations with 180° rotational-symmetry. In particular, we use combinatorial techniques to enumerate symmetric permutations which avoid one pattern of length three and one pattern of length four. Our results involve well-known sequences such as the alternating Fibonacci numbers, triangular numbers, and powers of two.     

Counting Simsun Permutations by Descents

We count in the present work simsun permutations of length n by their number of descents. Properties studied include the recurrence relation and real-rootedness of the generating function of the number of n-simsun permutations with k descents. By means of generating function arguments, we show that the descent number is equidistributed over n-simsun permutations and n-André permutations. We also compute the mean and variance of the random variable X _n taking values the descent number of random n-simsun permutations, and deduce that the distribution of descents over random simsun permutations of length n satisfies a central and a local limit theorem as n ?? +???.     

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.     

Horse paths, restricted 132-avoiding permutations, continued fractions, and Chebyshev polynomials

Several authors have examined connections among 132-avoiding permutations, continued fractions, and Chebyshev polynomials of the second kind. In this paper we find analogues for some of these results for permutations π avoiding 132 and 1□23 (there is no occurrence π_i<π_j<π_j+1 such that 1?i?j-2) and provide a combinatorial interpretation for such permutations in terms of lattice paths. Using tools developed to prove these analogues, we give enumerations and generating functions for permutations which avoid both 132 and 1□23, and certain additional patterns. We also give generating functions for permutations avoiding 132 and 1□23 and containing certain additional patterns exactly once. In all cases we express these generating functions in terms of Chebyshev polynomials of the second kind.     

A Refinement of Weak Order Intervals into Distributive Lattices

In this paper we consider arbitrary intervals in the left weak order on the symmetric group S _n . We show that the Lehmer codes of permutations in an interval form a distributive lattice under the product order. Furthermore, the rank-generating function of this distributive lattice matches that of the weak order interval. We construct a poset such that its lattice of order ideals is isomorphic to the lattice of Lehmer codes of permutations in the given interval. We show that there are at least ${\left(\lfloor {\frac{n}{2}} \rfloor \right)!}$ permutations in S _n that form a rank-symmetric interval in the weak order.     

Dyck paths and restricted permutations

This paper is devoted to characterize permutations with forbidden patterns by using canonical reduced decompositions, which leads to bijections between Dyck paths and S_n(321) and S_n(231), respectively. We also discuss permutations in S_n avoiding two patterns, one of length 3 and the other of length k. These permutations produce a kind of discrete continuity between the Motzkin and the Catalan numbers.     

Balanced tableaux

We study a new class of tableaux defined by a certain condition on hook-ranks. Many connections with the classical theory of standard Young tableaux are developed, as well as applications to the problem of enumerating reduced decompositions of permutations in S_n.     

Szemerédi's partition and quasirandomness

In this paper we shall investigate the connection between the Szemerédi Regularity Lemma and quasirandom graph sequences, defined by Chung, Graham, and Wilson, and also, slightly differently, by Thomason. We prove that a graph sequence (G_n) is quasirandom if and only if in the Szemerédi partitions of G_n almost all densities are ½ + o(l).     

Refined Enumeration of Permutations Sorted with Two Stacks and a D 8-Symmetry

We study permutations that are sorted by operators of the form S ° α ° S, where S is the usual stack sorting operator introduced by Knuth and α is any D ₈-symmetry obtained by combining the classical reverse, complement, and inverse operations. Such permutations can be characterized by excluded (generalized) patterns. Some conjectures about the enumeration of these permutations, refined with numerous classical statistics, have been proposed by Claesson, Dukes, and Steingrímsson. We prove these conjectures, and enrich one of them with a few more statistics. The proofs mostly rely on generating trees techniques, and on a recent bijection of Giraudo between Baxter and twisted Baxter permutations.     

A projective plane of order 16

A projective plane of order 16 is constructed. It is a translation plane and appears to be new. The representation of the collineation group on the axis of the plane has a normal subgroup isomorphic to L₃ (2) with factor group isomorphic to S₃. The orbits of this representation have lengths 14 and 3. If two points in the latter orbit are chosen to define a sharply doubly transitive set of permutations, the permutations from the multiplicative loop generate a group isomorphic to A₇. The plane is of Lenz-Barlotti class IVa.1.     

Classification of some metric automorphisms defined by Standish

Let F be a finite set with a probability distribution {P_i: i?F} and (Ω $\text{F}$, P) denote the product space of countably many copies of (F, P). A permutation (bijection) φ of the integers induces an invertible measure preserving transformation T_φ on (Ω $\text{F}$, P) given by the equation (T_φw)_i = w_φ(j). Such metric automorphisms we call S-automorphisms.We show in this paper that S-automorphisms are ergodic if and only they are Bernoulli shifts and two ergodic S-automorphisms are isomorphic if and only if their associated permutations are conjugate.We also show that S-automorphisms have discrete spectrum if and only if they have zero entropy and every S-automorphism is either a Bernoulli shift, has discrete spectrum, or is a product of a Bernoulli shift and an automorphism with discrete spectrum.S-automorphism with discrete spectrum are those whose associated permutations contain only cycles of finite length. These automorphisms are studied according to the number of such finite cycles. Those whose permutations have infinitely many finite cycles with unbounded lengths are shown to be antiperiodic and those whose permutations have infinitely many finite cycles of bounded length are periodic with almost no fixed points. An example is given of two automorphisms of this latter type which are isomorphic but whose permutations are not conjugate.A complete isomorphism invariant is given for S-automorphisms whose associated permutations consist of finitely many finite cycles. Using this invariant we show that if φ is either a product of k disjoint cycles of prime power p^α, or a single cycle of length pq where p and q are primes, or a product of k disjoint cycles of prime lengths p₁ < p₂ < ··· < p_kand if ψ is a permutation such that T_ψand T_φ are isomorphic then ψ is conjugate to φ.     

Central and local limit theorems applied to asymptotic enumeration II: Multivariate generating functions

Let a multivariate sequence a_n(k) ? 0 be given. Multivariate central and local limit theorems are proved for a_n(k) as n → ∞ that are based on examining the generating function. Applications are made to permutations with rises and falls, ordered partitions of sets, Tutte polynomials of recursive families, and dissections of polygons.     

Reconstruction of permutations distorted by reversal errors

The problem of reconstructing permutations on n elements from their erroneous patterns which are distorted by reversal errors is considered in this paper. Reversals are the operations reversing the order of a substring of a permutation. To solve this problem, it is essential to investigate structural and combinatorial properties of a corresponding Cayley graph on the symmetric group Sym_n generated by reversals. It is shown that for any n?3 an arbitrary permutation π is uniquely reconstructible from four distinct permutations at reversal distance at most one from π where the reversal distance is defined as the least number of reversals needed to transform one permutation into the other. It is also proved that an arbitrary permutation is reconstructible from three permutations with a probability p₃→1 and from two permutations with a probability as n→∞. A reconstruction algorithm is presented. In the case of at most two reversal errors it is shown that at least erroneous patterns are required in order to reconstruct an arbitrary permutation.     

Generating the alternating group by cyclic triples

It is shown that a collection of circular permutations of length three on an n-set generates the alternating group A_n if and only if the associated graph is connected. It follows that [$\text{1}\text{2}\text{n}$] circular permutations of length three may generateA_n.     

Pattern Avoidance in Poset Permutations

We extend the concept of pattern avoidance in permutations on a totally ordered set to pattern avoidance in permutations on partially ordered sets. The number of permutations on P that avoid the pattern p is denoted A v _P (p). We extend a proof of Simion and Schmidt to show that A v _P (132)=A v _P (123) for any poset P, and we exactly classify the posets for which equality holds.     

On basic forbidden patterns of functions

The allowed patterns of a map on a one-dimensional interval are those permutations that are realized by the relative order of the elements in its orbits. The set of allowed patterns is completely determined by the minimal patterns that are not allowed. These are called basic forbidden patterns.In this paper, we study basic forbidden patterns of several functions. We show that the logistic map L_r(x)=rx(1−x) and some generalizations have infinitely many of them for 1<r≤4, and we give a lower bound on the number of basic forbidden patterns of L₄ of each length. Next, we give an upper bound on the length of the shortest forbidden pattern of a piecewise monotone map. Finally, we provide some necessary conditions for a set of permutations to be the set of basic forbidden patterns of such a map.     

Lower bounds on the size of spheres of permutations under the Chebychev distance

Lower bounds on the number of permutations p of {1, 2, . . . , n} satisfying |p _i ? i| ?? d for all i are given.     

The maximal-inversion statistic and pattern-avoiding permutations

We define a new combinatorial statistic, maximal-inversion, on a permutation. We remark that the number M(n,k) of permutations in S_n with k maximal-inversions is the signless Stirling number c(n,n−k) of the first kind. A permutation π in S_n is uniquely determined by its maximal-inversion set . We prove it by making an algorithm for retrieving the permutation from its maximal-inversion set. Also, we remark on how the algorithm can be used directly to determine whether a given set is the maximal-inversion set of a permutation. As an application of the algorithm, we characterize the maximal-inversion set for pattern-avoiding permutations. Then we give some enumerative results concerning permutations with forbidden patterns.     

On sorting by 3-bounded transpositions

Heath and Vergara [Sorting by short block moves, Algorithmica 28 (2000) 323-352] proved the equivalence between sorting by 3-bounded transpositions and sorting by correcting skips and correcting hops. This paper explores various algorithmic as well as combinatorial aspects of correcting skips/hops, with the aim of understanding 3-bounded transpositions better.We show that to sort any permutation via correcting hops and skips, ⌊n/2⌋ correcting skips suffice. We also present a tighter analysis of the approximation algorithm of Heath and Vergara, and a possible simplification. Along the way, we study the class H_n of those permutations of S_n which can be sorted using correcting hops alone, and characterize large subsets of this class. We obtain a combinatorial characterization of the set G_n⊆S_n of all correcting-hop-free permutations, and describe a linear-time algorithm to optimally sort such permutations. We also show how to efficiently sort a permutation with a minimum number of correcting moves.