Available Papers by Francesco Brenti

If you have trouble downloading any of the files (most are dvi, some are ps or pdf), or would prefer a hard copy, please e-mail me at: brenti@mat.uniroma2.it

Papers available:

Kazhdan--Lusztig R-polynomials, combinatorial invariance, and hypercube decompositions (28 pages)
(with M. Marietti) Math. Zeit., (to appear).
We introduce the concepts of a join hypercube decomposition, and of a shortcut in a Bruhat interval with respect to any one of its elements. We show how shortcuts can be used to compute the Kazhdan-Lusztig R-polynomials of the symmetric groups, and conjecture that the same procedure works using the shortcuts with respect to any join hypercube decomposition of the interval. This conjecture implies the Combinatorial Invariance Conjecture for the symmetric groups. We also investigate the behaviour of these concepts under the operation of direct product of Bruhat intervals and deduce, in particular, that any counterexample of minimal rank to our conjecture cannot be isomorphic to the direct product of two strictly smaller intervals.
Some open problems on Coxeter groups and unimodality (14 pages)
in "Open Problems in Algebraic Combinatorics", (C. Berkesch, B. Brubaker, G. Musiker, P. Pylyavskyy, and V. Reiner, editors) Proceedings of Symposia in Pure Math., 110, Amer. Math. Soc., 2024, 23-37.
This is a collection of conjectures and open problems on Coxeter groups and unimodality, together with the main results, and computational evidence, that are known about them.
Cuntz algebras automorphisms: graphs and stability of permutations (59 pages)
(with R. Conti and G. Nenashev) Trans. Amer. Math. Soc., (to appear).
We associate to any permutation of [n]^t two sequences of graphs, and use them to characterize the stable permutations of [n]^t. As applications of this result we show that almost all permutations of [n]^t are not stable, thereby proving Conjecture 12.5 of [Advances in Math., 381 (2021), 107590], we give an upper bound on the rank of stable permutations in [n]^2 which is linear in n, we characterize explicitly, and enumerate, the stable 4 and 5-cycles in [n]^2, and identify a general class of stable cycles in [n]^2. Some of our results use new combinatorial concepts.
Wachs permutations, Bruhat order and weak order (26 pages)
(with P. Sentinelli) Europ. J. Combinatorics, 119 (2024), 103804.
Wachs permutations and signed Wachs permutations play a role in the signed enumeration of the symmetric and hyperoctahedral groups (see [Annals Combin., 24 (2020), 809-835] and the references cited there). We study the partial orders induced on Wachs and signed Wachs permutations by the Bruhat and (right and left) weak orders of the symmetric and hyperoctahedral groups. We show that these orders are graded, determine their rank function, characterize their ordering and covering relations, and compute their characteristic polynomials, when partially ordered by Bruhat order, and determine their structure explicitly when partially ordered by right weak order. Several conjectures are also presented.
Permutative automorphisms of the Cuntz algebras: quadratic cycles, an involution and a box product (34 pages)
(with R. Conti and G. Nenashev) Adv. in Appl. Math., 143 (2023), 102447.
We study the stable permutations of [n]^t, namely the elements of the reduced Weyl group of the Cuntz algebra O_n. More precisely, we characterize explicitly, and enumerate, the stable cycles of rank 1 in [n]^2, thus proving Conjecture 12.1 in [Advances in Math., 381 (2021), 107590], and the stable 3-cycles in [n]^2. We also show that the inverse transpose of a stable permutation of [n]^t is again stable of the same rank. Finally, we give a construction which produces, from two stable permutations of [n]^t and [m]^t, a stable permutation of [nm]^t.
Odd diagrams, Bruhat order, and pattern avoidance (17 pages)
(with A. Carnevale and B. Tenner) Comb. Theory, 2 (2022), no. 1, Paper No. 13.
We study the odd diagrams of permutations. More precisely, we prove Conjecture 6.1 in [Discrete Math., 344 (2021), no. 5, 112308], namely that the map that associates to a permutation its odd diagram is injective on permutations that avoid 312, and similarly for 213. We also show that the set of permutations that have a given odd diagram is an interval in Bruhat order.
Odd length: odd diagrams and descent classes (22 pages)
(with A. Carnevale) Discrete Math., 344 (2021), no. 5, 112308.
We define and study odd analogues of classical geometric and combinatorial objects associated to permutations, namely odd Schubert varieties, odd diagrams, and odd inversion sets. We show that there is a bijection between odd inversion sets of permutations and acyclic orientations of the Turan graph, that the dimension of the odd Schubert variety associated to a permutation is the odd length of the permutation, and give several necessary conditions for a subset of [n] x [n] to be the odd diagram of a permutation. We also study the signed (by length) generating function of the odd length over descent classes of the symmetric groups, and show that it factors explicitly for a family of descent classes which includes all quotients.
Permutations, tensor products, and Cuntz algebra automorphisms (65 pages)
(with R. Conti) Advances in Math., 381 (2021), 107590.
We study the reduced Weyl groups of the Cuntz algebras O_n from a combinatorial point of view. Their elements correspond bijectively to certain permutations of n^r elements, which we call stable. We mostly focus on the case r=2 and general n. A notion of rank is introduced, which is subadditive in a suitable sense. Being of rank 1 corresponds to solving an equation which is reminiscent of the Yang-Baxter equation. Symmetries of stable permutations are also investigated, along with an immersion procedure that produces stable permutations of (n+1)^2 objects starting from stable permutations of n^2 objects. A complete description of stable transpositions and of stable 3-cycles of rank 1 is obtained, leading to closed formulas for their number. Other enumerative results are also presented which yield lower and upper bounds for the number of stable permutations. We conclude with several conjectures and open problems.
Odd and even major indices and one-dimensional characters for classical Weyl groups (27 pages)
(with P. Sentinelli) Annals Combin., 24 (2020), 809-835.
We define and study odd and even analogues of the major index statistics for the classical Weyl groups. We show that the generating functions of these statistics, twisted by the one-dimensional characters of the corresponding groups, always factor in an explicit way. In particular, we obtain odd and even analogues of Carlitz's identity, of the Gessel--Simion Theorem, and a parabolic extension, and refinement, of a result of Wachs.
Odd length in Weyl groups (23 pages)
(with A. Carnevale) Algebraic Comb., 2 (2019), 1125-1147.
We define, for any crystallographic root system, a new statistic on the corresponding Weyl group which we call the odd length. This statistic reduces, for Weyl groups of types A, B, and D, to each of the statistics by the same name that have already been defined and studied in [Trans. Amer. Math. Soc., 361(2009), 4405-4436], [Electronic J. Combin., 20(2013), Paper 50], [Amer. J. Math., 136(2014), 501-550], and [Discrete Math., 340(2017), 2822-2833]. We show that the signed (by length) generating function of the odd length always factors completely, and we obtain multivariate analogues of these factorizations in types B and D.
Fixed points and adjacent ascents for classical complex reflection groups (18 pages)
(with M. Marietti) Adv. Applied Math., 101 (2018), 168-183.
We characterize the classical complex reflection groups for which a recent symmetric group equidistribution result studied by Diaconis, Evans, and Graham in [Adv. Applied Math., 61(2014), 102-124] holds. More precisely, we show that, with suitable definition of "unseparated pair", the result holds for the group G(r,p,n) if and only if gcd(p,n)=1, and that a refinement of it holds for G(r,p,n) if and only if all divisors of p are larger than n. This refinement seems to be new even in the symmetric group case.
Odd length for even hyperoctahedral groups and signed generating functions (19 pages)
(with A. Carnevale) Discrete Math. 340 (2017), 2822-2833.
We define a new statistic on the even hyperoctahedral groups which is a natural analogue of the odd length statistic recently defined and studied on Coxeter groups of types A and B in [Trans. Amer. Math. Soc., 361(2009), 4405-4436], [Electronic J. Combin., 20(2013), Paper 50], [Amer. J. Math., 136(2014), 501-550], and [Trans. Amer. Math. Soc., 369(2017), 7531-7547]. We show that the signed (by length) generating function of this statistic over the whole group and over its maximal and some other quotients always factors nicely, and present some conjectures.
A twisted duality for parabolic Kazhdan-Lusztig R-polynomials (13 pages)
J. Algebra 477 (2017), 472-482.
We prove a duality result for the parabolic Kazhdan-Lusztig R-polynomials of a finite Coxeter system. This duality is similar to, but different from, the one obtained by Douglass in [Comm. Algebra, 18 (1990), 371-387]. As a consequence of it we obtain an identity between the parabolic Kazhdan-Lusztig and inverse parabolic Kazhdan-Lusztig polynomials of a finite Coxeter system. We also derive applications to certain modules defined by Deodhar and evidence in favor of Marietti's combinatorial invariance conjecture for parabolic Kazhdan-Lusztig polynomials.
Stanley's work on unimodality (12 pages)
in "The Mathematical Legacy of Richard P. Stanley" (P. Hersh, T.Lam, P. Pylyavskyy, V. Reiner, Editors) American Mathematical Society (2016), 119-130.
We survey Stanley's work on unimodality, and its impact. We also pose some open problems that arise naturally from his work in this area.
Parabolic Kazhdan-Lusztig polynomials for quasi-minuscule quotients (25 pages)
(with P. Mongelli and P. Sentinelli) Adv. Applied Math., 78 (2016), 27-55.
We give explicit combinatorial formulas for the parabolic Kazhdan-Lusztig polynomials of type q of the quasi-minuscule quotients of classical Weyl groups. Our results imply that these are always either zero or a monic power of q, and that they are not combinatorial invariants. We conjecture an explicit combinatorial interpretation for the parabolic Kazhdan-Lusztig polynomials of type -1 of the quasi-minuscule quotients of classical Weyl groups.
Parabolic Kazhdan-Lusztig R-polynomials for quasi-minuscule quotients (18 pages)
(with P. Mongelli and P. Sentinelli) J. Algebra 452 (2016), 574-595.
We give explicit combinatorial formulas for the parabolic Kazhdan-Lusztig R-polynomials of the quasi-minuscule quotients of classical Weyl groups. As an application of our results we obtain explicit combinatorial formulas for certain sums and alternating sums of ordinary Kazhdan-Lusztig R-polynomials.
Proof of a conjecture of Klopsch-Voll on Weyl groups of type A (21 pages)
(with A. Carnevale) Trans. Amer. Math. Soc. 369 (2017), 7531-7547.
We prove a conjecture of Klopsch-Voll in [Trans. Amer. Math. Soc., 361(2009), 4405-4436] on the signed generating function of a new statistic on the quotients of the symmetric groups. As a consequence of our results we also prove a conjecture of Stasinski-Voll in [Amer. J. Math., 136 (2014), 501-550] which gives an analogous statement for type B. Our proofs are combinatorial and depend on certain operations on the relevant quotients that leave the corresponding generating function invariant.
Peak algebras, paths in the Bruhat graph and Kazhdan-Lusztig polynomials (36 pages)
(with F. Caselli) Advances in Math. 304 (2017), 539-582.
We give a new characterization of the peak subalgebra of the algebra of quasisymmetric functions and use this to construct a new basis for this subalgebra. As an application of these results we obtain a combinatorial formula for the Kazhdan-Lusztig polynomials which holds in complete generality and is simpler and more explicit than any existing one. We point out that, in a certain sense, this formula cannot be simplified.
Flag weak order on wreath products (20 pages)
(with R. Adin and Y. Roichman) Semin. Lothar. Combinatoire, 67 (2012), #e (20 pp).
We define and study an analogue of the weak order for the wreath products of a symmetric group by a cyclic group. We show that this order is a lattice, that it is ranked, self-dual, and rank unimodal. We also compute its rank generating function, the homotopy type of its intervals, and their Mobius function.
Parabolic Kazhdan-Lusztig R-polynomials for tight quotients of the symmetric groups (19 pages)
J. Algebra, 347 (2011), 247-261.
We give explicit closed combinatorial formulas for the parabolic Kazhdan-Lusztig R-polynomials of the tight quotients of the symmetric group. We give two formulations of our result, one in terms of permutations and one in terms of Motzkin paths. As an application of our results we obtain explicit closed combinatorial formulas for certain sums and alternating sums of ordinary Kazhdan-Lusztig R-polynomials.
Kazhdan-Lusztig polynomials, tight quotients and Dyck superpartitions (32 pages)
(with F. Incitti and M. Marietti) Adv. Applied Math., 47 (2011), 589-614.
We give an explicit combinatorial product formula for the parabolic Kazhdan-Lusztig polynomials of the tight quotients of the symmetric group. This formula shows that these polynomials are always either zero or a monic power of q and implies the main result in [Pacific J. Math., 207 (2002), 257-286] on the parabolic Kazhdan-Lusztig polynomials of the maximal quotients. The formula depends on a new class of superpartitions.
Quasisymmetric functions and Kazhdan-Lusztig polynomials (27 pages)
(with L. Billera) Israel J. Math., 184 (2011), 317-348.
We associate a noncommutative polynomial, which we call the "complete cd-index", to any Bruhat interval of any Coxeter group. We show that the complete cd-index includes the cd-index of the Bruhat interval as an Eulerian poset, that the Kazhdan-Lusztig and R-polynomials of the Bruhat interval can be easily computed from its complete cd-index, and we give a combinatorial formula for the coefficients of the complete cd-index. We conjecture that these coefficients are always nonnegative, and give some evidence in favor of this conjecture.
Enumerative properties of shifted Dyck partitions (18 pages)
J. Comb. Theory, Ser. A, 117 (2010), 223-235.
Shifted-Dyck partitions are a class of (possibly skew) shifted partitions that arise in the study of certain parabolic Kazhdan-Lusztig polynomials (see [Trans. Amer. Math. Soc., 361 (2009), 1703-1729]), and which is closely related to ballot sequences. We show that shifted Dyck partitions include, in a precise sense, the Dyck partitions studied in [Pacific J. Math., 207 (2002), 257-286] and [J. Comb. Theory, Ser. A, 99 (2002), 51-74] and that most of the results that hold for Dyck partitions actually hold for shifted Dyck partitions. As consequences of our results we obtain new identities for the parabolic Kazhdan-Lusztig polynomials of Hermitian symmetric pairs and for the ordinary Kazhdan-Lusztig polynomials of certain Weyl groups. (Maple programs used in the proof of one of the results of this paper.)
The Veronese construction for formal power series and graded algebras (14 pages)
(with V. Welker) Adv. Applied Math., 42 (2009), 545-556.
We study the transformation that maps the h-vector of a standard graded algebra to that of its r-th Veronese subalgebra. We give an explicit combinatorial description of this transformation, and show that, if r is sufficiently large, then it maps nonnegative vectors to vectors whose generating polynomial has only real zeros. As consequences of these results we obtain that, if r is sufficiently large, then the numerator polynomial of the Hilbert series of the r-th Veronese subalgebra of a standard graded algebra, and the generating polynomial of the f-vector of the r-th edgewise subdivision of a simplicial complex, have only real zeros and are therefore log-concave and unimodal, and the h-vector of the r-th Veronese subalgebra of a Cohen-Macaulay standard graded algebra is componentwise monotonically increasing with r.
Alternating subgroups of Coxeter groups (34 pages)
(with V. Reiner and Y. Roichman) J. Comb. Theory, Ser. A, 115 (2008), 845-877.
We study combinatorial properties of the alternating subgroup of a Coxeter group, using a presentation of it due to Bourbaki. More precisely, we study a length function, descent sets, reduced words, palindromes, and define and study a simplicial complex and two partial orderings which are analogues of the Coxeter complex, weak and Bruhat orders on a Coxeter group.
f-vectors of barycentric subdivisions (22 pages)
(with V. Welker) Math. Zeit., 259 (2008), 849-865.
We show that the generating polynomial of the h-vector (and therefore of the f-vector) of the barycentric subdivision of a simplicial complex whose h-vector is nonnegative has only real zeros, and is therefore log-concave and unimodal. We also show that the roots of this polynomial, under repeated barycentric subdivision, tend to a limit that depends only on the dimension of the original simplicial complex. Our results imply a strong version of the Charney-Davis conjecture for the barycentric subdivisions of the boundary complexes of simple polytopes.
Parabolic Kazhdan-Lusztig R-polynomials for Hermitian symmetric pairs (21 pages)
J. Algebra, 318 (2007), 412-429.
We give explicit combinatorial product formulas for the parabolic Kazhdan-Lusztig R-polynomials of Hermitian symmetric pairs. We give two formulations of our main result, one in terms of signed permutations and one in terms of lattice paths. Our results imply that all the roots of these polynomials are (either zero or) roots of unity and complete those in [Pacific J. Math., 207 (2002), 257-286] on Hermitian symmetric pairs of type A. Some of the results are used in [Trans. Amer. Math. Soc., 361 (2009), 1703-1729] for the computation of the parabolic Kazhdan-Lusztig polynomials of Hermitian symmetric pairs.
Special matchings and Coxeter groups (11 pages)
(with F. Caselli and M. Marietti) Arch. Mathematik, 89 (2007), 298-310.
We show that, for any element v of any Coxeter group W whose Dynkin diagram is a simply laced tree, the special matchings of the lower Bruhat interval [e,v], considered as involutions on [e,v], generate a Coxeter system. This gives new necessary conditions on an abstract poset to be isomorphic to a lower Bruhat interval of such Coxeter groups, answers in the affirmative, for this class of Coxeter groups, a problem posed in [F. Brenti, F. Caselli, M. Marietti, Advances in Math., 202 (2006), 555-601], and generalizes the main result of [F. Brenti, F. Caselli, M. Marietti, Advances Applied Math., 38 (2007), 210-226].
Parabolic Kazhdan-Lusztig polynomials for Hermitian symmetric pairs (26 pages)
Trans. Amer. Math. Soc., 361 (2009), 1703-1729.
We give explicit combinatorial product formulas for the parabolic Kazhdan-Lusztig polynomials of Hermitian symmetric pairs. These are closely related to a new class of skew shifted partitions. Our results imply that these polynomials are combinatorial invariants, that they are always either zero or a monic power of q, and complete those in [Pacific J. Math., 207 (2002), 257-286] on Hermitian symmetric pairs of type A.
Special matchings and permutations in Bruhat orders (22 pages)
(with F. Caselli and M. Marietti) Advances Applied Math., 38 (2007), 210-226.
In this paper we show that, for any permutation v, the special matchings of the lower Bruhat interval [e,v], considered as involutions on [e,v], generate a Coxeter system. This gives new necessary conditions on an abstract poset to be isomorphic to a lower Bruhat interval of the symmetric group, and also answers in the affirmative, in the symmetric group case, a problem posed in [F. Brenti, F. Caselli, M. Marietti, Advances in Math., 202 (2006), 555-601].
A unified construction of Coxeter group representations (II) (27 pages)
(with R. Adin and Y. Roichman) J. Algebra, 306 (2006), 208-226.
In this work we continue the investigation of the representations of Coxeter groups and Hecke algebras constructed in [R. Adin, F. Brenti, Y. Roichman, Advances Applied Math., 37 (2006), 31-67]. In particular, we show that all the irreducible representations of the classical Weyl groups of types A and B are obtained by this construction.
Diamonds and Hecke algebra representations (30 pages)
(with F. Caselli and M. Marietti) Int. Math. Research Notices, 2006, Art. ID 29407.
In this work we show that Kazhdan and Lusztig's construction of Hecke algebra representations introduced in [D. Kazhdan, G. Lusztig, Invent. Math., 53 (1979), 165-184] can be carried out in a much more general (and entirely combinatorial) context. More precisely, we introduce a new class of partially ordered sets, that we call diamonds, which have a very rich combinatorial and algebraic structure and which include all Coxeter groups partially ordered by Bruhat order. We prove that one can define a family of polynomials indexed by pairs of elements in the diamond which reduce to the Kazhdan-Lusztig polynomials in the case that the diamond is a Coxeter group. We then show that every diamond contains in a natural way a Coxeter group and hence a Hecke algebra. Finally we show that this Coxeter group and the corresponding Hecke algebra act naturally on the diamond, and that the resulting representations include those constructed by Kazhdan and Lusztig, but contain several new ones.
Lattice paths, lexicographic correspondence and Kazhdan-Lusztig polynomials (17 pages)
(with F. Incitti) J. Algebra, 303 (2006), 742-762.
In this paper we give a new closed formula for the Kazhdan-Lusztig polynomials of finite Coxeter groups and affine Weyl groups. This formula is computationally more efficient than any existing one, and it conjecturally holds for any Coxeter system. The formula is based on the notion of lexicographic correspondence between Bruhat paths.
A unified construction of Coxeter group representations (44 pages)
(with R. Adin and Y. Roichman) Advances Applied Math., 37 (2006), 31-67.
This paper presents a unified, combinatorial, and elementary approach to the construction of some representations of Coxeter groups and their associated Hecke algebras. The construction is particularly explicit for simply laced Coxeter systems.
Equi-distribution over descent classes of the hyperoctahedral group (23 pages)
(with R. Adin and Y. Roichman) J. Comb. Theory, Ser. A, 113 (2006), 917-933.
A classic result of Foata and Schutzenberger shows that the length function and the major index are equi-distributed over inverse descent classes of the symmetric group. In this paper we give analogues, refinements and consequences of this result for the hyperoctahedral group Bn.
Special matchings and Kazhdan-Lusztig polynomials (50 pages)
(with F. Caselli and M. Marietti) Advances in Math., 202 (2006), 555-601.
In this paper we show that the combinatorial concept of a special matching plays a fundamental role in the computation of the Kazhdan-Lusztig polynomials. Our results also imply, and generalize, the recent one in [F. Du Cloux, Advances in Math., 180 (2003), 146-175] on the combinatorial invariance of Kazhdan-Lusztig polynomials.
The intersection cohomology of Schubert varieties is a combinatorial invariant (21 pages)
Europ. J. Combinatorics, 25 (2004), 1151-1167.
We give an explicit and entirely poset-theoretic way to compute, for any permutation v, all the Kazhdan-Lusztig polynomials P_{x,y} for x,y in [e,v], starting from the Bruhat interval [e,v] as an abstract poset. This proves, in particular, that the intersection cohomology of Schubert varieties depends only on the inclusion relations between the closures of its Schubert cells.
Kazhdan-Lusztig polynomials: History, Problems, and Combinatorial Invariance (23 pages)
Seminaire Lotharingien de Combinatoire, 49 (2003), 613-627.
This is an expository paper on Kazhdan-Lusztig polynomials, and particularly on the recent result concerning their combinatorial invariance, based on my lectures at the 49th Seminaire Lotharingien de Combinatoire. The paper consists of three parts entitled: History; Problems; and Combinatorial Invariance. In the first one we give the main definitions and facts about the Bruhat order and graph, and about the Kazhdan-Lusztig and R-polynomials. In the second one we present, as a sample, two results, one on the R-polynomials and one on the Kazhdan-Lusztig polynomials, which in the author's opinion illustrate very well the rich combinatorics that hides in these polynomials. Finally, in the third part, we explain the recent result that the Kazhdan-Lusztig and R-polynomials depend only on a certain poset, and mention some open problems and conjectures related to this.
Descent Representations and Multivariate Statistics (47 pages)
(with R. Adin and Y. Roichman), Trans. Amer. Math. Soc., 357 (2005), 3051-3082.
Combinatorial identities on Weyl groups of types A and B are derived from special bases of the corresponding coinvariant algebras. Using the Garsia-Stanton descent basis of the coinvariant algebra of type A we give a new construction of the Solomon descent representations. An extension of the descent basis to type B, using new multivariate statistics on the group, yields a refinement of the descent representations. These constructions are then applied to refine well-known decomposition rules of the coinvariant algebra and to generalize various identities.
P-kernels, IC bases and Kazhdan-Lusztig polynomials (18 pages)
J. Algebra, 259 (2003), 613-627.
In [R. P. Stanley, J. Amer. Math. Soc., 5 (1992), 805-851] Stanley introduced the concept of a P-kernel for any locally finite partially ordered set P. In [J. Du, Algebraic groups and their generalizations: quantum and infinite-dimensional methods, Proc. Sympos. Pure Math. 56, Amer. Math. Soc., 1994, 135-148] Du introduced, for any set P, the concept of an IC basis. The purpose of this paper is to show that, under some mild hypotheses, these two concepts are equivalent and, given a Coxeter group W partially ordered by Bruhat order, to characterize among all possible W-kernels the one corresponding to the Kazhdan-Lusztig basis of the Hecke algebra of W. Finally, we show that this W-kernel factorizes as a product of other W-kernels, and that these provide a solution to the Yang-Baxter equations for W.
Enumerative and combinatorial properties of Dyck partitions (23 pages)
J. Comb. Theory, Ser. A, 99 (2002), 51-74.
The purpose of this paper is to study the combinatorial and enumerative properties of a new class of (skew) integer partitions. This class is closely related to Dyck paths and plays a fundamental role in the computation of certain Kazhdan-Lusztig polynomials of the symmetric group related to Young's lattice. As a consequence of our results, we obtain some new identities for these polynomials.
Descent Numbers and Major Indices for the Hyperoctahedral Group (15 pages)
(with R. Adin and Y. Roichman), Advances Applied Math., 27 (2001), 210-224.
We introduce and study three new statistics on the hyperoctahedral group Bn, and show that they give two generalizations of Carlitz's identity for the descent number and major index over Sn. This answers a question posed by Foata.
Kazhdan-Lusztig and R-polynomials, Young's lattice, and Dyck partitions (34 pages)
Pacific J. Math., 207 (2002), 257-286.
We give explicit combinatorial product formulas for the maximal parabolic Kazhdan-Lusztig and R-polynomials of the symmetric group. These formulas imply that these polynomials are combinatorial invariants, and that the Kazhdan-Lusztig ones are nonnegative. The combinatorial formulas are most naturally stated in terms of Young's lattice, and the one for the Kazhdan-Lusztig polynomials depends on a new class of skew partitions which are closely related to Dyck paths.
Approximation Results for Kazhdan-Lusztig polynomials (25 pages)
Adv. Studies Pure Math., 28 (2000), 57-81.
We use the theory of P-kernels developed by Stanley in [R. P. Stanley, J. Amer. Math. Soc., 5 (1992), 805-851] to approximate the Kazhdan-Lusztig polynomials with other ``KLS-functions'' that are easier to compute. In particular, we characterize the pairs u,v in W such that the Kazhdan-Lusztig polynomials of the subintervals of [u,v] satisfy certain vanishing properties or, more generally, coincide with some given function in the incidence algebra of W, up to a given order. Two of our results generalize and refine previous ones that have appeared in [D. Kazhdan, G. Lusztig, Invent. Math., 53 (1979), 165-184] and [F. Brenti, Invent. Math., 118 (1994), 371-394].
Mixed Bruhat operators and Yang-Baxter equations for Weyl groups (22 pages)
(with S. Fomin and A. Postnikov), Int. Math. Research Notices, (1999), No.8, 419-441.
We introduce and study a family of operators which act in the group algebra of a Weyl group W and provide a multi-parameter solution to the quantum Yang-Baxter equations of the corresponding type. These operators are then used to derive new combinatorial properties of W, and to obtain new proofs of known results concerning the Bruhat order of W.
A class of q-symmetric functions arising from plethysm (34 pages)
J. Comb. Theory, Ser. A, 91 (2000), 137-170.
We introduce and study a class of symmetric functions, which depend on a parameter q, and which includes symmetric functions that have already appeared in the literature in connection with Jack symmetric functions, parking functions, and lattices of non-crossing partitions. Our results generalize previous ones by Haiman, Stanley, and the author.
Explicit formulae for some Kazhdan-Lusztig polynomials (10 pages)
(with R. Simion) J. Algebraic Combinatorics, 11 (2000), 187-196.
We consider the Kazhdan-Lusztig polynomials 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 in 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.
Twisted incidence algebras and Kazhdan-Lusztig-Stanley functions (31 pages)
Advances in Math., 148 (1999), 44-74.
We introduce a new multiplication in the incidence algebra of a partially ordered set, and study the resulting algebra. As an application of the properties of this algebra we obtain a combinatorial formula for the Kazhdan-Lusztig-Stanley functions of a poset. As special cases this yields new combinatorial formulas for the parabolic and inverse parabolic Kazhdan-Lusztig polynomials, for the generalized (toric) h-vector of an Eulerian poset, and for the Lusztig-Vogan polynomials.
An improved tableau criterion for Bruhat order (5 pages)
(with A. Bjorner) Elec. J. Combinatorics, 3 (1996), \#R22
To decide whether two permutations are comparable in Bruhat order of Sn with the well-known tableau criterion requires n choose 2 comparisons of entries in certain sorted arrays. We show that to decide whether x < y only d1+d2+...+dk of these comparisons are needed, where {d1,d2,...,dk} = {i | x(i)>x(i+1)}. This is obtained as a consequence of a sharper version of Deodhar's criterion, which is valid for all Coxeter groups.
Lattice paths and Kazhdan-Lusztig polynomials (31 pages)
J. Amer. Math. Soc., 11 (1998), 229-259.
The purpose of this paper is to present a new non-recursive combinatorial formula for the Kazhdan-Lusztig polynomials. More precisely, we show that each directed path in the Bruhat graph of W has a naturally associated set of lattice paths with the property that the Kazhdan-Lusztig polynomial of u, v is the sum, over all the lattice paths associated to all the paths going from u to v, of (-1)^{c_0+d_{+}}*q^{(l(u,v)+c(l))/2} where c_0, d_{+}, and c(l) are three natural statistics on the lattice path. This formula is the most explicit non-recursive formula known for the Kazhdan-Lusztig polynomials which holds in complete generality.
Affine Permutations of Type A (35 pages)
(with A. Bjorner) Elec. J. Combinatorics, 3 (1996), #R18.
We study combinatorial properties, such as inversion table, weak order and Bruhat order, for certain infinite permutations that realize the affine Coxeter group of type A.
Hilbert polynomials in Combinatorics (30 pages)
J. Algebraic Combinatorics, 7 (1998), 127-156.
We prove that several polynomials naturally arising in combinatorics are Hilbert polynomials of standard graded commutative k-algebras.
The Applications of Total Positivity to Combinatorics, and conversely (23 pages)
in Total Positivity and its Applications, (M. Gasca, C. A. Micchelli, eds.), Kluwer Academic Pub., Dordrecht, The Netherlands, 1996, 451-473.
Total positivity is an important and powerful concept that arises often in various branches of mathematics, statistics, probability, mechanics, economics, and computer science ( see, e.g., [S. Karlin, Total Positivity, vol.1, Stanford University Press, 1968], and the references cited there). In this paper we give a survey of the interactions between total positivity and combinatorics.
Kazhdan-Lusztig and R-polynomials from a combinatorial point of view (34 pages)
Discrete Math., 193 (1998), 93-116. Discrete Mathematics Editors' Choice for 1998
In this paper we survey and illustrate two combinatorial rules for the computation of the Kazhdan-Lusztig and R-polynomials, and we present some intriguing conjectures and open problems (some old and some new) together with the evidence that exists for them. To help the reader get a better feeling for these conjectures and problems we have included two sections which survey the main combinatorial properties which are known for the Kazhdan-Lusztig and R-polynomials. Our goal is to make the material more easily accessible and understandable by stripping it of all the technical details that the original papers contain and by illustrating it with several examples, while at the same time providing references for further reading for the interested reader. We only treat the symmetric groups since the material is particularly interesting, especially from a combinatorial point of view, in this case. Our hope is that this paper will stimulate combinatorial research on these polynomials for the symmetric groups, since we firmly believe that they hide a wealth of beautiful and deep combinatorial results.
Combinatorial Expansions of Kazhdan-Lusztig polynomials} (25 pages)
J. London Math. Soc., 55 (1997), 448-472.
We introduce two, related, families of polynomials, easily computable by simple recursions into which any Kazhdan-Lusztig (and inverse Kazhdan-Lusztig) polynomial of any Coxeter group can be expanded linearly, and we give combinatorial interpretations to the coefficients in these expansions. This yields a combinatorial rule for computing the Kazhdan-Lusztig polynomials in terms of paths in a directed graph, and a completely combinatorial reformulation of the nonnegativity conjecture
Upper and Lower Bounds for Kazhdan-Lusztig polynomials (15 pages)
Europ. J. Combinatorics, 19 (1998), 283-297.
We give upper and lower bounds for the Kazhdan-Lusztig polynomials of any Coxeter group W. If W is finite we prove that, for any k > 0, the k-th coefficient of the Kazhdan-Lusztig polynomial of two elements u,v of W is bounded from above by a polynomial (which depends only on k) in l(v)-l(u). In particular, this implies the validity of Lascoux-Schutzenberger's conjecture for all sufficiently long intervals, and gives supporting evidence in favor of the Dyer-Lusztig conjecture.
A Combinatorial Formula for Kazhdan-Lusztig polynomials (24 pages)
Invent. Math., 118 (1994), 371-394.
Our aim in this work is to give a simple, nonrecursive, combinatorial formula for any Kazhdan-Lusztig polynomial of any Coxeter group, and to study some consequences of it. The main idea involved in the proof and statement of this formula is that of extending the concept of the R-polynomial to any (finite) multichain of W (so that, for multichains of length 1, one obtains, apart from sign, the usual R-polynomials). Once this has been done, then the Kazhdan-Lusztig polynomial of a pair u,v turns out to be just the sum, over all multichains from u to v, of the corresponding (generalized) R-polynomials. The R-polynomial of a multichain can be readily defined, and computed, from the ordinary R-polynomials. Since several combinatorial formulas and interpretations are known for these polynomials and simple recurrences exist for them, we feel that this formula is a significant step forward in the understanding of the Kazhdan-Lusztig polynomials.
Log-concave and Unimodal sequences in Algebra, Combinatorics, and Geometry: an update (19 pages)
Contemporary Math., 178 (1994), 71-89.
Log-concave and unimodal sequences arise often in combinatorics, algebra, geometry and computer science, as well as in probability and statistics where these concepts were first defined and studied. Even though log-concavity and unimodality have one-line definitions, to prove the unimodality or log-concavity of a sequence can sometimes be a very difficult task requiring the use of intricate combinatorial constructions or of refined mathematical tools. The number and variety of these tools is quite bewildering and surprising. They include, for example, classical analysis, linear algebra, the representation theory of Lie algebras and superalgebras, the theory of total positivity, the theory of symmetric functions, and algebraic geometry. In [R. Stanley, Log-concave and unimodal sequences in Algebra, Combinatorics and Geometry, Annals of the New York Academy of Sciences, 576 (1989), 500-534] R. Stanley gave an excellent survey of many of these techniques, problems, and results. Since then (the paper had been written in the Spring of 1986) new techniques have been developed, many new results have been obtained and some of the problems have been solved, while new ones have emerged. Our purpose in this paper is to give a survey of these developments.
Combinatorial Properties of the Kazhdan-Lusztig R-polynomials for Sn (31 pages)
Advances in Math., 126 (1997), 21-51.
We point out a deep and surprising connection between the Kazhdan-Lusztig R-polynomials for Sn and the enumeration and combinatorics of increasing subsequences in permutations. This leads to a simple combinatorial recurrence and to several new closed formulas for these polynomials.
Combinatorics and Total Positivity (44 pages)
J. Comb. Theory, Ser. A, 71 (1995), 175-218.
It was first observed in [F. Brenti, Unimodal, log-concave, and Polya Frequency sequences in Combinatorics, Memoirs Amer. Math. Soc., no. 413 (1989)] that Polya frequency sequences arise often in combinatorics. In this work we point out that the same is true , more generally, for totally positive matrices. More precisely, we show that many of the familiar matrices arising in combinatorics, as well as in the theory of symmetric functions, and many of their generalizations, have remarkable total positivity properties, and that, conversely, any totally positive matrix can be realized as a matrix of generalized complete homogeneous symmetric functions evaluated at nonnegative real numbers. The method that we use to prove these results is completely combinatorial and has its origin in a technique for counting non-intersecting paths in directed graphs first used by Lindstrom, and then by Gessel, Viennot, and others to solve various enumerative problems. In this paper we use some variations and generalizations of it.
q-Eulerian polynomials arising from Coxeter groups (25 pages)
Europ. J. Combinatorics, 15 (1994), 417-441.
In this work we study the polynomials obtained by enumerating a (finite) Coxeter system with respect to the number of descents. For the symmetric group these polynomials are the classical Eulerian polynomials, and thus have been extensively studied from a combinatorial point of view. In this paper we show that essentially all of the classical results for Eulerian polynomials have analogues for these other polynomials, and that it is possible to define natural q-analogues of them which are also q-analogues of the Eulerian polynomials. Our results generalize and unify previous results of Dolgachev, Lunts, Stanley and Stembridge. We also present several conjectures.
Permutation Enumeration Symmetric Functions, and Unimodality (28 pages)
Pacific J. Math., 157 (1993), 1-28.
We study the polynomials obtained by enumerating a set of permutations with respect to the number of excedances. We prove that these polynomials have only real zeros and are unimodal for many interesting classes of permutations. We then show how these polynomials also arise naturally from the theory of symmetric functions.
Determinants of Super-Schur Functions, Lattice Paths, and Dotted Plane Partitions (38 pages)
Advances in Math., 98 (1993), 27-64.
Let s_L (x1,x2,... / y1,y2 ,... ) be the super-Schur function corresponding to the partition L. The purpose of the present work is to give combinatorial interpretations to the minors of the infinite matrix (s_(k)(x1,...,xn / y1,...,yn)) (n,k=0,1,2,...). Our main results are proved combinatorially using lattice paths and are stated in terms of dotted and diagonal strict plane partitions, respectively. They also have several applications. As special cases we obtain combinatorial interpretations of determinants of homogeneous, elementary, and Hall-Littlewood symmetric functions, Schur's Q-functions, q-binomial coefficients, and q-Stirling numbers of both kinds. Other applications include the combinatorial interpretation of a class of symmetric functions first defined, algebraically, by Macdonald. Many of our results are new even in the case q=1. Others are q-analogues of known results. Our main theorem also has several interesting applications to the theory of total positivity.
Expansions of chromatic polynomials and log-concavity (28 pages)
Trans. Amer. Math. Soc., 332 (1992), 729-756.
In this paper we present several results and open problems about log-concavity properties of sequences associated with graph colorings. Five polynomials intimately related to the chromatic polynomial of a graph are introduced and their zeros, combinatorial and log-concavity properties are studied. Four of these polynomials have never been considered before in the literature and some yield new expansions for the chromatic polynomial.
Log-concavity and combinatorial properties of Fibonacci Lattices (18 pages)
Europ. J. Combinatorics, 12 (1991), 459-476.
We prove that two infinite families of polynomials naturally associated to Fibonacci Lattices have only real zeros and give combinatorial interpretations to these polynomials. This in particular implies the log-concavity of several combinatorial sequences arising from Fibonacci Lattices and generalizes a result obtained by R. Stanley.
Unimodal Polynomials arising from symmetric functions (9 pages)
Proc. Amer. Math. Soc., 108 (1990), 1133-1141.
We present a general result that, using the theory of symmetric functions, produces several new classes of symmetric unimodal polynomials. The result has applications to enumerative combinatorics including the proof of a conjecture by R. Stanley.