On thecd-variation polynomials of André and simsun permutations

We prove a conjecture of Stanley on thecd-index of the semisuspension of the face poset of a simplicial shelling component. We give a new signed generalization of André permutations, together with a new notion ofcd-variation for signed permutations. This generalization not only allows us to compute thecd-index of the face poset of a cube, but also occurs as a natural set of orbit representatives for a signed generalization of the Foata-Strehl commutative group action on the symmetric group. From the induction techniques used, it becomes clear that there is more than one way to define classes of permutations andcd-variation such that they allow us to compute thecd-index of the same poset. This research was supported by the UQAM Foundation.     

Monotonicity of the cd-index for polytopes

We prove that the cd-index of a convex polytope satisfies a strong monotonicity property with respect to the cd-indices of any face and its link. As a consequence, we prove for d-dimensional polytopes a conjecture of Stanley that the cd-index is minimized on the d-dimensional simplex. Moreover, we prove the upper bound theorem for the cd-index, namely that the cd-index of any d-dimensional polytope with n vertices is at most that of C(n,d), the d-dimensional cyclic polytope with n vertices. Received September 29, 1998; in final form February 8, 1999     

Inequalities for <Emphasis Type="Bold">cd</Emphasis>-Indices of Joins and Products of Polytopes

The cd-index is a polynomial which encodes the flag f-vector of a convex polytope. For polytopes U and V, we determine explicit recurrences for computing the cd-index of the free join and the cd-index of the Cartesian product U x V. As an application of these recurrences, we prove the inequality involving the cd-indices of three polytopes.     

On the Q-rational cuspidal subgroup and the component group ofJ 0(p r )

Forp≥3 a prime, we compute theQ-rational cuspidal subgroupC(p ^r ) of the JacobianJ ₀(p ^r ) of the modular curveX ₀(p ^r ). This result is then applied to determine the component group Φ _p ^r of the Néron model ofJ ₀(p ^r ) overZ _p . This extends results of Lorenzini [7]. We also study the action of the Atkin-Lehner involution on thep-primary part ofC(p ^r ), as well as the effect of degeneracy maps on the component groups.     

The Number of Permutations with Exactlyr132-Subsequences IsP-Recursive in the Size!

Proving a first nontrivial instance of a conjecture of Noonan and Zeilberger we show that the numberS_r(n) of permutations of lengthncontaining exactlyrsubsequences of type 132 is aP-recursive function ofn. We show that this remains true even if we impose some restrictions on the permutations. We also show the stronger statement that the ordinary generating functionG_r(x) ofS_r(n) is algebraic, in fact, it is rational in the variablesxand . We use this information to show that the degree of the polynomial recursion satisfied byS_r(n) isr.     

Quasisymmetric functions and Kazhdan-Lusztig polynomials

We associate a quasisymmetric function to any Bruhat interval in a general Coxeter group. This association can be seen to be a morphism of Hopf algebras to the subalgebra of all peak functions, leading to an extension of the cd-index of convex polytopes. We show how the Kazhdan-Lusztig polynomial of the Bruhat interval can be expressed in terms of this complete cd-index and otherwise explicit combinatorially defined polynomials. In particular, we obtain the simplest closed formula for the Kazhdan-Lusztig polynomials that holds in complete generality.     

The Generalized Gauss Reduction Algorithm

We generalize the Gauss algorithm for the reduction of two-dimensional lattices from thel₂-norm to arbitrary norms and extend Vallée's analysis [J. Algorithms12(1991), 556–572] to the generalized algorithm.     

On the action of permutations on distances between values of rational functions mod p

For the finite field Fp one may consider the distance between r₁(n) and r₂(n), where r₁, r₂ are rational functions in Fp(x). We study the effect to such distances by applying all possible permutations to the elements.     

Permutations with roots

We prove that the probability p₂(n) that a random permutation of length n has a square root is monotonically nonincreasing in n. More generally, we prove that the probability p_r(n) that a random permutation of length n has an rth root, r prime, is monotonically nonincreasing in n. We also show for all r≥2 that p_r(n)→0 as n→∞. While doing this, we combinatorially prove that p_r(n)=p_r(n+1) for r prime and for all n not congruent to −1 mod r, and we construct several bijections for sets of permutations defined by modular class restrictions on the cycle lengths. We also include a simple probabilistic proof that, for r≥2, p_r(n)→0 as n→∞. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17: 157–167, 2000     

Farrell cohomology and Brown theorems for profinite groups

LetG be a profinite group which has an open subgroupH such that the cohomologicalp-dimensiond≔cd_p(H) is finite (p is a fixed prime). The main result of this paper expresses thep-primary part of high degree cohomology ofG in terms of the elementary abelianp-subgroups ofG: From the latter one constructs a natural profinite simplicial setA G, on whichG acts by conjugation. ThenH ⁿ(G,M)≅H _G ⁿ (AG,M) holds forn≧d+r and everyp-primary discreteG-moduleM (r≔p-rank ofG). If one uses profinite Farrell cohomology, which is introduced in this paper, the analogous fact holds in all degrees. These results are the profinite analogues of theorems by K.S. Brown for discrete groups.     

Decomposition theorem for the cd-index of Gorenstein<Superscript>*</Superscript> posets

We prove a decomposition theorem for the cd-index of a Gorenstein^* poset analogous to the decomposition theorem for the intersection cohomology of a toric variety. From this we settle a conjecture of Stanley that the cd-index of Gorenstein* lattices is minimized on Boolean algebras.     

Coproducts and the cd-Index

The linear span of isomorphism classes of posets, P, has a Newtonian coalgebra structure. We observe that the ab-index is a Newtonian coalgebra map from the vector space P to the algebra of polynomials in the noncommutative variables a and b. This enables us to obtain explicit formulas showing how the cd-index of the face lattice of a convex polytope changes when taking the pyramid and the prism of the polytope and the corresponding operations on posets. As a corollary, we have new recursion formulas for the cd-index of the Boolean algebra and the cubical lattice. Moreover, these operations also have interpretations for certain classes of permutations, including simsun and signed simsun permutations. We prove an identity for the shelling components of the simplex. Lastly, we show how to compute the ab-index of the Cartesian product of two posets given the ab-indexes of each poset.     

Exact Enumeration of 1342-Avoiding Permutations: A Close Link with Labeled Trees and Planar Maps

Solving the first nonmonotonic, longer-than-three instance of a classic enumeration problem, we obtain the generating functionH(x) of all 1342-avoiding permutations of lengthnas well as anexactformula for their numberS_n(1342). While achieving this, we bijectively prove that the number of indecomposable 1342-avoiding permutations of lengthnequals that of labeled plane trees of a certain type onnvertices recently enumerated by Cori, Jacquard, and Schaeffer, which is in turn known to be equal to the number of rooted bicubic maps enumerated by Tutte (Can. J. Math.33(1963), 249–271). Moreover,H(x) turns out to be algebraic, proving the first nonmonotonic, longer-than-three instance of a conjecture of Noonan and Zeilberger (Adv. Appl. Math.17(1996), 381–407). We also prove thatconverges to 8, so in particular, lim_n→∞(S_n(1342)/S_n(1234))=0.     

The Flagged Double Schur Function

The double Schur function is a natural generalization of the factorial Schur function introduced by Biedenharn and Louck. It also arises as the symmetric double Schubert polynomial corresponding to a class of permutations called Grassmannian permutations introduced by A. Lascoux. We present a lattice path interpretation of the double Schur function based on a flagged determinantal definition, which readily leads to a tableau interpretation similar to the original tableau definition of the factorial Schur function. The main result of this paper is a combinatorial treatment of the flagged double Schur function in terms of the lattice path interpretations of divided difference operators. Finally, we find lattice path representations of formulas for the symplectic and orthogonal characters for sp(2n) and so(2n + 1) based on the tableau representations due to King and El-Shakaway, and Sundaram. Based on the lattice path interpretations, we obtain flagged determinantal formulas for these characters.     

On the existence of entire functions of boundedl-index andl-regular growth

We prove that, under certain conditions on a positive functionl continuous on [0, +∞], there exists an entire transcendental functionf of boundedl-index such that lnlnM _f(r)lnL(r),r→∞, whereM _f (r)=max {|f(z)|: |z|=r} andL(r)=∫ ₀ ^r l(t)dt. Ifl(r)=r ^p-1 forr≥1, 0<ρ<∞, then there exists an entire functionf of boundedl-index such thatM _f (r)≈r ^p . Lvov University, Lvov. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 48, No. 9, pp. 1166–1182, September, 1996.     

Arithmetic Interpretability Types of Varieties and Some Additive Problems with Primes

We deal with varieties with one basic operation f(x₁,...,x_n) and one defining identity f(x₁,..., x_n) = f(x_π(1),...,x_π(n)), where π is a permutation whose cyclic set consists of distinct primes p₁,...,p_r, with the sum p₁+...+p_r = n. Their interpretability types, together with the greatest element 1 in a lattice ^int, are said to be arithmetic. It is proved that the arithmetic types constitute a distributive lattice _ar, which is dual to a lattice Sub _fΠ of finite subsets of the set Π of all primes. It is shown that for n ⩾ 2, the poset _ar( _n) of arithmetic types defined by permutations in _n, for n fixed, is a lattice iff n = 2, 3, 4, 6, 8, 9, 11. __________ Translated from Algebra i Logika, Vol. 44, No. 5, pp. 622–630, September–October, 2005.     

Weighted Davenport’s constant and the weighted EGZ Theorem

Let G^∗,G be finite abelian groups with nontrivial homomorphism group . Let Ψ be a non-empty subset of . Let D_Ψ(G) denote the minimal integer, such that any sequence over G^∗ of length D_Ψ(G) must contain a nontrivial subsequence s₁,…,s_r, such that for some ψ_i∈Ψ. Let E_Ψ(G) denote the minimal integer such that any sequence over G^∗ of length E_Ψ(G) must contain a nontrivial subsequence of length |G|,s₁,…,s_|G|, such that for some ψ_i∈Ψ. In this paper, we show that E_Ψ(G)=|G|+D_Ψ(G)−1.     

A generalized permutahedron

With respect to a fixedn-element ordered setP, thegeneralized permutahedron Perm(P) is the set of all ordered setsP L, whereL is any permutation of the elements of the underlyingn-element set. Considered as a subset of the extension lattice of ann-element set,Perm(P) is cover-preserving. We apply this to deduce, for instance, that, in any finite ordered setP, there is a comparability whose removal will not increase the dimension, and there is a comparability whose addition toP will not increase its dimension.We establish further properties about the extension lattice which seem to be of independent interest, leading for example, to the characterization of those ordered setsP for which this generalized permutahedron is itself a lattice.Presented by J. Sichler.Dedicated to the memory of Alan DaySupported in part by PRC Mathématiques-Informatique (France) and NSERC (Canada).Supported in part by DFG (Germany) and NSERC (Canada).Supported in part by NSERC (Canada).