The symmetric and unimodal expansion of Eulerian polynomials via continued fractions

This paper was motivated by a conjecture of Brändén [P. Brändén, Actions on permutations and unimodality of descent polynomials, European J. Combin. 29 (2) (2008) 514-531] about the divisibility of the coefficients in an expansion of generalized Eulerian polynomials, which implies the symmetric and unimodal property of the Eulerian numbers. We show that such a formula with the conjectured property can be derived from the combinatorial theory of continued fractions. We also discuss an analogous expansion for the corresponding formula for derangements and prove a (p,q)-analogue of the fact that the (-1)-evaluation of the enumerator polynomials of permutations (resp. derangements) by the number of excedances gives rise to tangent numbers (resp. secant numbers). The (p,q)-analogue unifies and generalizes our recent results [H. Shin, J. Zeng, The q-tangent and q-secant numbers via continued fractions, European J. Combin. 31 (7) (2010) 1689-1705] and that of Josuat-Vergès [M. Josuat-Vergés, A q-enumeration of alternating permutations, European J. Combin. 31 (7) (2010) 1892-1906].     

Product decompositions of the symmetric group induced by separable permutations

In this paper we consider the rank generating function of a separable permutation π in the weak Bruhat order on the two intervals [id,π] and [π,w₀], where w₀=n,n−1,…,1. We show a surprising result that the product of these two generating functions is the generating function for the symmetric group with the weak order. We then obtain explicit formulas for the rank generating functions on [id,π] and [π,w₀], leading to the rank-symmetry and unimodality of the two graded posets.     

Generating indecomposable permutations

An indecomposable permutation π on [n] is one such that π([m])=[m] for no m<n. We consider indecomposable permutations and give a new, inclusive enumerative recurrence for them. This recurrence allows us to generate all indecomposable permutations of length n in transposition Gray code order, in constant amortized time (CAT). We also present a CAT generation algorithm for indecomposable permutations which is based on the Johnson-Trotter algorithm for generating all permutations of length n. The question of whether or not there exists an adjacent transposition Gray code for indecomposable permutations remains open.     

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 functional equation arising from multiplication of quantum integers

For the quantum integer [n]_q=1+q+q²+?+qⁿ⁻¹ there is a natural polynomial multiplication such that [m]_q⊗_q[n]_q=[mn]_q. This multiplication leads to the functional equation f_m(q)f_n(q^m)=f_mn(q), defined on a given sequence of polynomials. This paper contains various results concerning the construction and classification of polynomial sequences that satisfy the functional equation, as well open problems that arise from the functional equation.     

The Length of the Longest Increasing Subsequence of a Random Mallows Permutation

The Mallows measure on the symmetric group S _n is the probability measure such that each permutation has probability proportional to q raised to the power of the number of inversions, where q is a positive parameter and the number of inversions of π is equal to the number of pairs i<j such that π _i >π _j . We prove a weak law of large numbers for the length of the longest increasing subsequence for Mallows distributed random permutations, in the limit that n→∞ and q→1 in such a way that n(1?q) has a limit in R.     

Counting matrices over finite fields with support on skew Young diagrams and complements of Rothe diagrams

We consider the problem of finding the number of matrices over a finite field with a certain rank and with support that avoids a subset of the entries. These matrices are a q-analogue of permutations with restricted positions (i.e., rook placements). For general sets of entries, these numbers of matrices are not polynomials in q (Stembridge in Ann. Comb. 2(4):365, 1998); however, when the set of entries is a Young diagram, the numbers, up to a power of q?1, are polynomials with nonnegative coefficients (Haglund in Adv. Appl. Math. 20(4):450, 1998). In this paper, we give a number of conditions under which these numbers are polynomials in q, or even polynomials with nonnegative integer coefficients. We extend Haglund’s result to complements of skew Young diagrams, and we apply this result to the case where the set of entries is the Rothe diagram of a permutation. In particular, we give a necessary and sufficient condition on the permutation for its Rothe diagram to be the complement of a skew Young diagram up to rearrangement of rows and columns. We end by giving conjectures connecting invertible matrices whose support avoids a Rothe diagram and Poincaré polynomials of the strong Bruhat order.     

Combinatorial invariance of Kazhdan-Lusztig polynomials on intervals starting from the identity

We show that for Bruhat intervals starting from the identity in Coxeter groups the conjecture of Lusztig and Dyer holds, that is, the R-polynomials and the Kazhdan-Lusztig polynomials defined on [e,u] only depend on the isomorphism type of [e,u]. To achieve this we use the purely poset-theoretic notion of special matching. Our approach is essentially a synthesis of the explicit formula for special matchings discovered by Brenti and the general special matching machinery developed by Du Cloux.     

How to play the one-lie Rényi-Ulam game

The one-lie Rényi-Ulam liar game is a two-player perfect information zero-sum game, lasting q rounds, on the set [n]?{1,…,n}. In each round Paul chooses a subset A⊆[n] and Carole either assigns one lie to each element of A or to each element of [n]?A. Paul wins the original (resp. pathological) game if after q rounds there is at most one (resp. at least one) element with one or fewer lies. We exhibit a simple, unified, optimal strategy for Paul to follow in both games, and use this to determine which player can win for all q,n and for both games.     

Constructing permutations of finite fields via linear translators

Methods for constructing large families of permutation polynomials of finite fields are introduced. For some of these permutations the cycle structure and the inverse mapping are determined. The results are applied to lift minimal blocking sets of PG(2,q) to those of PG(2,qn).     

Weyl quantization for semidirect products

Let G be the semidirect product V?K where K is a connected semisimple non-compact Lie group acting linearily on a finite-dimensional real vector space V. Let O be a coadjoint orbit of G associated by the Kirillov-Kostant method of orbits with a unitary irreducible representation π of G. We consider the case when the corresponding little group K₀ is a maximal compact subgroup of K. We realize the representation π on a Hilbert space of functions on Rn where n=dim(K)−dim(K₀). By dequantizing π we then construct a symplectomorphism between the orbit O and the product R2n×O^′ where O^′ is a little group coadjoint orbit. This allows us to obtain a Weyl correspondence on O which is adapted to the representation π in the sense of [B. Cahen, Quantification d'une orbite massive d'un groupe de Poincaré généralisé, C. R. Acad. Sci. Paris Série I 325 (1997) 803-806]. In particular we recover well-known results for the Poincaré group.     

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.     

Minimum number of ideal generators for a linear center perturbed by homogeneous polynomials

Using the algorithm presented in [J. Giné, X. Santallusia, On the Poincaré-Liapunov constants and the Poincaré series, Appl. Math. (Warsaw) 28 (1) (2001) 17-30] the Poincaré-Liapunov constants are calculated for polynomial systems of the form , , where P_n and Q_n are homogeneous polynomials of degree n. The objective of this work is to calculate the minimum number of ideal generators i.e., the number of functionally independent Poincaré-Liapunov constants, through the study of the highest fine focus order for n=4 and n=5 and compare it with the results that give the conjecture presented in [J. Giné, On the number of algebraically independent Poincaré-Liapunov constants, Appl. Math. Comput. 188 (2) (2007) 1870-1877]. Moreover, the computational problems which appear in the computation of the Poincaré-Liapunov constants and the determination of the number of functionally independent ones are also discussed.     

A Generalization of the Kostka–Foulkes Polynomials

Combinatorial objects called rigged configurations give rise to q-analogues of certain Littlewood–Richardson coefficients. The Kostka–Foulkes polynomials and two-column Macdonald–Kostka polynomials occur as special cases. Conjecturally these polynomials coincide with the Poincaré polynomials of isotypic components of certain graded GL(n)-modules supported in a nilpotent conjugacy class closure in gl(n).     

Setwise intersecting families of permutations

A family of permutations A⊂Sn is said to be t-set-intersecting if for any two permutations σ,π∈A, there exists a t-set x whose image is the same under both permutations, i.e. σ(x)=π(x). We prove that if n is sufficiently large depending on t, the maximum-sized t-set-intersecting families of permutations in Sn are cosets of stabilizers of t-sets. The t=2 case of this was conjectured by János Körner. It can be seen as a variant of the Deza-Frankl conjecture, proved in Ellis, Friedgut and Pilpel (2011) [3]. Our proof uses similar techniques to those of Ellis, Friedgut and Pilpel (2011) [3], namely, eigenvalue methods, together with the representation theory of the symmetric group, but the combinatorial part of the proof is harder.     

More on the combinatorial invariance of Kazhdan-Lusztig polynomials

We prove that the Kazhdan-Lusztig polynomials are combinatorial invariants for intervals up to length 8 in Coxeter groups of type A and up to length 6 in Coxeter groups of type B and D. As a consequence of our methods, we also obtain a complete classification, up to isomorphism, of Bruhat intervals of length 7 in type A and of length 5 in types B and D, which are not lattices.     

Sets of permutations that generate the symmetric group pairwise

The paper contains proofs of the following results. For all sufficiently large odd integers n, there exists a set of ²n−1 permutations that pairwise generate the symmetric group Sn. There is no set of ²n−1+1 permutations having this property. For all sufficiently large integers n with n≡2mod4, there exists a set of ²n−2 even permutations that pairwise generate the alternating group An. There is no set of ²n−2+1 permutations having this property.     

On the multigraded Hilbert and Poincaré-Betti series and the Golod property of monomial rings

In this paper we study the multigraded Hilbert and Poincaré-Betti series of A=S/a, where S is the ring of polynomials in n indeterminates divided by the monomial ideal a. There is a conjecture about the multigraded Poincaré-Betti series by Charalambous and Reeves which they proved in the case where the Taylor resolution is minimal. We introduce a conjecture about the minimal A-free resolution of the residue class field and show that this conjecture implies the conjecture of Charalambous and Reeves and, in addition, gives a formula for the Hilbert series. Using Algebraic Discrete Morse theory, we prove that the homology of the Koszul complex of A with respect to x₁,…,x_n is isomorphic to a graded commutative ring of polynomials over certain sets in the Taylor resolution divided by an ideal r of relations. This leads to a proof of our conjecture for some classes of algebras A. We also give an approach for the proof of our conjecture via Algebraic Discrete Morse theory in the general case.The conjecture implies that A is Golod if and only if the product (i.e. the first Massey operation) on the Koszul homology is trivial. Under the assumption of the conjecture we finally prove that a very simple purely combinatorial condition on the minimal monomial generating system of a implies Golodness for A.     

A Grothendieck module with applications to Poincaré rationality

In this paper, we define a Grothendieck module associated to a Noetherian ring A. This structure is designed to encode relations between A-modules which can be responsible for the relations among Betti numbers and therefore rationality of the Poincaré series. We will define the Grothendieck module, demonstrate that the condition of being torsion in the Grothendieck module implies rationality of the Poincaré series, and provide examples. The paper concludes with an example which demonstrates that the condition of being torsion in the Grothendieck module is strictly stronger than having rational Poincaré series.