Pattern avoidance for alternating permutations and Young tableaux

We define a class Ln,k of permutations that generalizes alternating (up-down) permutations and give bijective proofs of certain pattern-avoidance results for this class. As a special case of our results, we give bijections between the set A2n(1234) of alternating permutations of length 2n with no four-term increasing subsequence and standard Young tableaux of shape 〈n³〉, and between the set A2n+1(1234) and standard Young tableaux of shape 〈³n−1,2,1〉. This represents the first enumeration of alternating permutations avoiding a pattern of length four. We also extend previous work on doubly-alternating permutations (alternating permutations whose inverses are alternating) to our more general context.The set Ln,k may be viewed as the set of reading words of the standard Young tableaux of a certain skew shape. In the last section of the paper, we expand our study to consider pattern avoidance in the reading words of standard Young tableaux of any skew shape. We show bijectively that the number of standard Young tableaux of shape λ/μ whose reading words avoid 213 is a natural μ-analogue of the Catalan numbers (and in particular does not depend on λ, up to a simple technical condition), and that there are similar results for the patterns 132, 231 and 312.     

Evacuation and a geometric construction for Fibonacci tableaux

Tableaux have long been used to study combinatorial properties of permutations and multiset permutations. Discovered independently by Robinson and Schensted and generalized by Knuth, the Robinson–Schensted correspondence has provided a fundamental tool for relating permutations to tableaux. In 1963, Schützenberger defined a process called evacuation on standard tableaux which gives a relationship between the pairs of tableaux (P,Q) resulting from the Schensted correspondence for a permutation and both the reverse and the complement of that permutation. Viennot gave a geometric construction for the Schensted correspondence and Fomin described a generalization of the correspondence which provides a bijection between permutations and pairs of chains in Young's lattice.In 1975, Stanley defined a Fibonacci lattice and in 1988 he introduced the idea of a differential poset. Roby gave an insertion algorithm, analogous to the Schensted correspondence, for mapping a permutation to a pair of Fibonacci tableaux. The main results of this paper are to give an evacuation algorithm for the Fibonacci tableaux that is analogous to the evacuation algorithm on Young tableaux and to describe a geometric construction for the Fibonacci tableaux that is similar to Viennot's geometric construction for Young tableaux.     

Explicit Formulae for Some Kazhdan-Lusztig Polynomials

We consider the Kazhdan-Lusztig polynomials P _u,v (q) indexed by permutations u, v having particular forms with regard to their monotonicity patterns. The main results are the following. First we obtain a simplified recurrence relation satisfied by P _u,v (q) when the maximum value of v S_n occurs in position n – 2 or n – 1. As a corollary we obtain the explicit expression for P_{e,3 4 ... n 1 2}(q) (where e denotes the identity permutation), as a q-analogue of the Fibonacci number. This establishes a conjecture due to M. Haiman. Second, we obtain an explicit expression for P_{e, 3 4 ... (n – 2) n (n – 1) 1 2}(q). Our proofs rely on the recurrence relation satisfied by the Kazhdan-Lusztig polynomials when the indexing permutations are of the form under consideration, and on the fact that these classes of permutations lend themselves to the use of induction. We present several conjectures regarding the expression for P _u,v (q) under hypotheses similar to those of the main results.     

The different ways of stabbing disjoint convex sets

We construct a family ofn disjoint convex set in ^d having (n/(d–1)) ^d–1 geometric permutations. As well, we complete the enumeration problem for geometric permutations of families of disjoint translates of a convex set in the plane, settle the case for cubes in ^d , and construct a family ofd+1 translates in ^d admitting (d+1)!/2 geometric permutations.This research was partly supported by NSERC Grants A3062, A5137, and A8761.     

The order dimension of two levels of the Boolean lattice

LetB _n(s, t) denote the partially ordered set consisting of alls-subsets andt-subsets of ann-element underlying set where these sets are ordered by inclusion. Answering a question of Trotter we prove that dim(B _n(k, n–k))=n–2 for 3k<(1/7)n ^1/3. The proof uses extremal hypergraph theory.     

On the Average Running Time of Odd–Even Merge Sort

This paper gives an upper bound for the average running time of Batcher's odd–even merge sort when implemented on a collection of processors. We consider the case wheren, the size of the input, is an arbitrary multiple of the numberpof processors used. We show that Batcher's odd–even merge (for two sorted lists of lengthneach) can be implemented to run in timeO((n/p)(log(2 + p²/n))) on the average,¹and that odd–even merge sort can be implemented to run in timeO((n/p)(log n + log p log(2 + p²/n))) on the average. In the case of merging (sorting), the average is taken over all possible outcomes of the merge (all possible permutations ofnelements). That means that odd–even merge and odd–even merge sort have an optimal average running time ifn ≥ p². The constants involved are also quite small.     

An algorithmic sign-reversing involution for special rim-hook tableaux

Eğecioğlu and Remmel [Linear Multilinear Algebra 26 (1990) 59–84] gave an interpretation for the entries of the inverse Kostka matrix K⁻¹ in terms of special rim-hook tableaux. They were able to use this interpretation to give a combinatorial proof that KK⁻¹=I but were unable to do the same for the equation K⁻¹K=I. We define an algorithmic sign-reversing involution on rooted special rim-hook tableaux which can be used to prove that the last column of this second product is correct. In addition, following a suggestion of Chow [preprint, math.CO/9712230, 1997] we combine our involution with a result of Gasharov [Discrete Math. 157 (1996) 193–197] to give a combinatorial proof of a special case of the (3+1)-free Conjecture of Stanley and Stembridge [J. Combin. Theory Ser. A 62 (1993) 261–279].     

The Number of Steps in the Robinson-Schensted Algorithm

Suppose that a permutation σ ∈ S _n is chosen at random (n is large) and the Robinson-Schensted algorithm is applied to compute the associated Young diagram. Then for almost all permutations the number of bumping operations performed by the algorithm is about (128/27π²)n ^3/2, and the number of comparison operations is about (64/27π²)n ^3/2 log₂ n.__________Translated from Funktsional’nyi Analiz i Ego Prilozheniya, Vol. 39, No. 2, pp. 82–86, 2005Original Russian Text Copyright © by D. Romik     

Partial geometries and the triality quadric

Up to now there are eight partial geometries pg(7,8,4) known. Their point graphs as well as their block graphs are all related to the triality quadric Q⁺(7,2). We prove that some of these graphs are the point graph of (up to isomorphism) exactly one partial geometry. We investigate the relations among some of these eight partial geometries. Generalizing our results, we construct two new families of partial geometries pg(2^2n–1– 1, 2^2n–1, 2^2n–2).The second author is a Research Fellow supported by the Flemish Institute for the Promotion of Scientific and Technological Research in Industry (IWT), grant No. IWT/SB/971002.     

Rapidly Mixing Random Walks and Bounds on Characters of the Symmetric Group

We investigate mixing of random walks on S _n and A _n generated by permutations of a given cycle structure. The approach follows methods developed by Diaconis, which requires certain estimates on characters of the symmetric group and uses combinatorics of Young tableaux. We conclude with conjectures and open problems.     

Exact k-Wise Intersection Theorems

A typical problem in extremal combinatorics is the following. Given a large number n and a set L, find the maximum cardinality of a family of subsets of a ground set of n elements such that the intersection of any two subsets has cardinality in L. We investigate the generalization of this problem, where intersections of more than 2 subsets are considered. In particular, we prove that when k–1 is a power of 2, the size of the extremal k-wise oddtown family is (k–1)(n– 2log₂(k–1)). Tight bounds are also found in several other basic cases.Research supported in part by NSF grant DMS 99-70270 and by the joint Berlin/Zurich graduate program Combinatorics, Geometry, Computation, financed by the German Science Foundation (DFG) and ETH ZürichResearch supported in part by NSF grant DMS-0200357, by an NSF CAREER award and by an Alfred P. Sloan fellowship. webpage: http://www.math.ucsd.edu/vanvu/     

Permutation Polyhedra and Minimisation of the Variance of Completion Times on a Single Machine

We consider the problem of minimising variance of completion times when n-jobs are to be processed on a single machine. This problem is known as the CTV problem. The problem has been shown to be difficult. In this paper we consider the polytope P _n whose vertices are in one-to-one correspondence with the n! permutations of the processing times [p ₁, p ₂, ..., p _n]. Thus each vertex of P _n represents a sequence in which the n-jobs can be processed. We define a V-shaped local optimal solution to the CTV problem to be the V-shaped sequence of jobs corresponding to which the variance of completion times is smaller than for all the sequences adjacent to it on P _n. We show that this local solution dominates V-shaped feasible solutions of the order of 2 ^n–3 where 2 ^n–2 is the total number of V-shaped feasible solutions.Using adjacency structure an P _n, we develop a heuristic for the CTV problem which has a running time of low polynomial order, which is exact for n 10, and whose domination number is (2 ^n–3). In the end we mention two other classes of scheduling problems for which also ADJACENT provides solutions with the same domination number as for the CTV problem.     

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.     

Enumerating rc-Invariant Permutations with No Long Decreasing Subsequences

We use the Robinson-Schensted-Knuth correspondence and Schützenberger’s evacuation of standard tableaux to enumerate permutations and involutions which are invariant under the reverse-complement map and which have no decreasing subsequences of length k. These enumerations are in terms of numbers of permutations with no decreasing subsequences of length approximately \frack2;{{\frac{k}{2}};} we use known results concerning these quantities to give explicit formulas when k ≤ 6.     

The multiplicity of 1-factors in the square of a graph

Several authors have shown that if G is a connected graph of even order then its square G² has a 1-factor. We show that the square of any connected graph of order 2n has at least n 1-factors and describe all the extremal graphs.     

New Cyclic Difference Sets with Singer Parameters Constructed from d-Homogeneous Functions

In this paper, for a prime power q, new cyclic difference sets with Singer para- meters ((q ⁿ –1/q–1), (q ^n–1–1/q–1), (q ^n–2–1/q–1)) are constructed by using q-ary sequences (d-homogeneous functions) of period q ⁿ –1 and the generalization of GMW difference sets is proposed by combining the generation methods of d-form sequences and extended sequences. When q is a power of 3, new cyclic difference sets with Singer parameters ((q ⁿ –1/q–1), (q ^n–1–1/q–1), (q ^n–2–1/q–1)) are constructed from the ternary sequences of period q ⁿ –1 with ideal autocorrelation introduced by Helleseth, Kumar, and Martinsen.     

Forbidden Families of Geometric Permutations in ℝd

A geometric permutation induced by a transversal line of a finite family ℱ of disjoint convex sets in ℝ^d is the order in which the transversal meets the members of the family. We prove that for each natural k, each family of k permutations is realizable (as a family of geometric permutations of some ℱ) in ℝ^d for d ≥ 2k – 1, but there is a family of k permutations which is non-realizable in ℝ^d for d ≤ 2k – 2.     

On 321-Avoiding Permutations in Affine Weyl Groups

We introduce the notion of 321-avoiding permutations in the affine Weyl group W of type A _{n – 1} by considering the group as a George group (in the sense of Eriksson and Eriksson). This enables us to generalize a result of Billey, Jockusch and Stanley to show that the 321-avoiding permutations in W coincide with the set of fully commutative elements; in other words, any two reduced expressions for a 321-avoiding element of W (considered as a Coxeter group) may be obtained from each other by repeated applications of short braid relations.Using Shi's characterization of the Kazhdan–Lusztig cells in the group W, we use our main result to show that the fully commutative elements of W form a union of Kazhdan–Lusztig cells. This phenomenon has been studied by the author and J. Losonczy for finite Coxeter groups, and is interesting partly because it allows certain structure constants for the Kazhdan–Lusztig basis of the associated Hecke algebra to be computed combinatorially.We also show how some of our results can be generalized to a larger group of permutations, the extended affine Weyl group associated to GL _n ()     

Binomial posets, Möbius inversion, and permutation enumeration

A unified method is presented for enumerating permutations of sets and multisets with various conditions on their descents, inversions, etc. We first prove several formal identities involving Möbius functions associated with binomial posets. We then show that for certain binomial posets these Möbius functions are related to problems in permutation enumeration. Thus, for instance, we can explain “why” the exponential generating function for alternating permutations has the simple form (1 + sin x)/(cos x). We can also clarify the reason for the ubiquitous appearance of e^x in connection with permutations of sets, and of ξ(s) in connection with permutations of multisets.     

Permutation tableaux and permutation patterns

In this paper we introduce and study a class of tableaux which we call permutation tableaux; these tableaux are naturally in bijection with permutations, and they are a distinguished subset of the -diagrams of Alex Postnikov [A. Postnikov, Webs in totally positive Grassmann cells, in preparation; L. Williams, Enumeration of totally positive Grassmann cells, Adv. Math. 190 (2005) 319-342]. The structure of these tableaux is in some ways more transparent than the structure of permutations; therefore we believe that permutation tableaux will be useful in furthering the understanding of permutations. We give two bijections from permutation tableaux to permutations. The first bijection carries tableaux statistics to permutation statistics based on relative sizes of pairs of letters in a permutation and their places. We call these statistics weak excedance statistics because of their close relation to weak excedances. The second bijection carries tableaux statistics (via the weak excedance statistics) to statistics based on generalized permutation patterns. We then give enumerative applications of these bijections. One nice consequence of these results is that the polynomial enumerating permutation tableaux according to their content generalizes both Carlitz' q-analog of the Eulerian numbers [L. Carlitz, q-Bernoulli and Eulerian numbers, Trans. Amer. Math. Soc. 76 (1954) 332-350] and the more recent q-analog of the Eulerian numbers found in [L. Williams, Enumeration of totally positive Grassmann cells, Adv. Math. 190 (2005) 319-342]. We conclude our paper with a list of open problems, as well as remarks on progress on these problems which has been made by A. Burstein, S. Corteel, N. Eriksen, A. Reifegerste, and X. Viennot.