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 email me at:
brenti@mat.uniroma2.it
Papers available:

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 5cycles 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 (32 pages)
(with P. Sentinelli)
Europ. J. Combinatorics,
(to appear).
Wachs permutations and signed Wachs permutations play a role in the signed enumeration of the symmetric and
hyperoctahedral groups (see [Annals Combin., 24 (2020), 809835] 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 3cycles 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 YangBaxter 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 3cycles 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 onedimensional characters for classical Weyl groups (27 pages)
(with P. Sentinelli)
Annals Combin.,
24 (2020), 809835.
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 onedimensional 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 GesselSimion 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), 11251147.
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), 44054436], [Electronic J. Combin., 20(2013), Paper 50],
[Amer. J. Math., 136(2014), 501550], and [Discrete Math., 340(2017), 28222833]. 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), 168183.
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), 102124] 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), 28222833.
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), 44054436], [Electronic J. Combin., 20(2013), Paper 50],
[Amer. J. Math., 136(2014), 501550], and [Trans. Amer. Math. Soc., 369(2017),
75317547]. 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 KazhdanLusztig Rpolynomials (13 pages)
J. Algebra
477 (2017), 472482.
We prove a duality result for the parabolic KazhdanLusztig Rpolynomials
of a finite Coxeter system. This duality is similar to, but different from, the
one obtained by Douglass in [Comm. Algebra, 18 (1990), 371387].
As a consequence of it we obtain an identity between the
parabolic KazhdanLusztig and inverse parabolic KazhdanLusztig 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 KazhdanLusztig 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), 119130.
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 KazhdanLusztig polynomials for quasiminuscule quotients (25 pages)
(with P. Mongelli and P. Sentinelli)
Adv. Applied Math.,
78 (2016), 2755.
We give explicit combinatorial formulas for the parabolic KazhdanLusztig polynomials of type q of the quasiminuscule 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 KazhdanLusztig polynomials of type 1 of the quasiminuscule quotients of classical Weyl groups.

Parabolic KazhdanLusztig Rpolynomials for quasiminuscule quotients (18 pages)
(with P. Mongelli and P. Sentinelli)
J. Algebra
452 (2016), 574595.
We give explicit combinatorial formulas for the parabolic KazhdanLusztig Rpolynomials of the quasiminuscule quotients of classical Weyl groups. As an
application of our results we obtain explicit combinatorial
formulas for certain sums and alternating sums of ordinary
KazhdanLusztig Rpolynomials.

Proof of a conjecture of KlopschVoll on Weyl groups of type A (21 pages)
(with A. Carnevale)
Trans. Amer. Math. Soc.
369 (2017), 75317547.
We prove a conjecture of KlopschVoll in [Trans. Amer. Math. Soc., 361(2009),
44054436] 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 StasinskiVoll in [Amer. J. Math., 136 (2014),
501550] 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 KazhdanLusztig polynomials (36 pages)
(with F. Caselli)
Advances in Math.
304 (2017), 539582.
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
KazhdanLusztig 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,
selfdual, and rank unimodal.
We also compute its rank generating function, the homotopy type of its intervals,
and their Mobius function.

Parabolic KazhdanLusztig Rpolynomials for tight quotients
of the symmetric groups
(19 pages)
J. Algebra,
347 (2011), 247261.
We give explicit closed combinatorial formulas for the parabolic
KazhdanLusztig Rpolynomials 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
KazhdanLusztig Rpolynomials.

KazhdanLusztig polynomials, tight quotients and Dyck
superpartitions
(32 pages)
(with F. Incitti and M. Marietti)
Adv. Applied Math.,
47 (2011), 589614.
We give an explicit combinatorial product formula for
the parabolic KazhdanLusztig 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),
257286] on the parabolic KazhdanLusztig polynomials of the
maximal quotients. The formula depends on a new class of
superpartitions.

Quasisymmetric functions and KazhdanLusztig polynomials
(27 pages)
(with L. Billera)
Israel J. Math.,
184 (2011), 317348.
We associate a noncommutative polynomial, which we call the "complete
cdindex", to any Bruhat interval of any Coxeter group. We show that
the complete cdindex includes the cdindex
of the Bruhat interval as an Eulerian poset, that the KazhdanLusztig
and Rpolynomials of the Bruhat interval can be easily computed from its
complete cdindex, and we give a combinatorial formula for the coefficients
of the complete cdindex. 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), 223235.
ShiftedDyck partitions are a class of (possibly skew) shifted partitions
that arise in the study of certain parabolic KazhdanLusztig polynomials
(see [Trans. Amer. Math. Soc., 361 (2009), 17031729]), 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), 257286] and [J. Comb. Theory, Ser. A,
99 (2002), 5174] 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 KazhdanLusztig polynomials of Hermitian symmetric
pairs and for the ordinary KazhdanLusztig 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), 545556.
We study the transformation that maps the hvector of a standard graded
algebra to that of its rth 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
rth Veronese subalgebra of a standard graded algebra, and the generating
polynomial of the fvector of the rth edgewise subdivision of a simplicial
complex, have only real zeros and are therefore logconcave and unimodal,
and the hvector of the rth Veronese subalgebra of a CohenMacaulay
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), 845877.
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.

fvectors of barycentric subdivisions
(22 pages)
(with V. Welker)
Math. Zeit.,
259 (2008), 849865.
We show that the generating polynomial of the hvector (and therefore of the
fvector) of the barycentric subdivision of a simplicial complex whose hvector
is nonnegative has only real zeros, and is therefore logconcave 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 CharneyDavis
conjecture for the barycentric subdivisions of the boundary complexes of simple
polytopes.

Parabolic KazhdanLusztig Rpolynomials for Hermitian symmetric pairs
(21 pages)
J. Algebra,
318 (2007), 412429.
We give explicit combinatorial product formulas for the parabolic
KazhdanLusztig Rpolynomials 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), 257286] on Hermitian
symmetric pairs of type A. Some of the results are used in [Trans. Amer.
Math. Soc., 361 (2009), 17031729] for the computation of the parabolic KazhdanLusztig
polynomials of Hermitian symmetric pairs.

Special matchings and Coxeter groups (11 pages)
(with F. Caselli and M. Marietti)
Arch. Mathematik,
89 (2007), 298310.
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), 555601], and generalizes the main result of
[F. Brenti, F. Caselli, M. Marietti, Advances Applied Math., 38 (2007), 210226].

Parabolic KazhdanLusztig polynomials for Hermitian symmetric pairs (26 pages)
Trans. Amer. Math. Soc.,
361 (2009), 17031729.
We give explicit combinatorial product formulas for the parabolic
KazhdanLusztig 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), 257286] 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), 210226.
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), 555601].

A unified construction of Coxeter group representations (II) (27 pages)
(with R. Adin and Y. Roichman)
J. Algebra,
306 (2006), 208226.
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), 3167].
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),
165184] 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 KazhdanLusztig 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 KazhdanLusztig polynomials (17 pages)
(with F. Incitti)
J. Algebra,
303 (2006), 742762.
In this paper we give a new closed formula for the KazhdanLusztig 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), 3167.
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.

Equidistribution over descent classes of the
hyperoctahedral group (23 pages)
(with R. Adin and Y. Roichman)
J. Comb. Theory, Ser. A,
113 (2006), 917933.
A classic result of Foata and Schutzenberger shows that the length function
and the major index are equidistributed 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 KazhdanLusztig polynomials (50 pages)
(with F. Caselli and M. Marietti)
Advances in Math.,
202 (2006), 555601.
In this paper we show that the combinatorial concept
of a special matching plays a fundamental
role in the computation of the KazhdanLusztig polynomials.
Our results also imply, and generalize, the recent one in
[F. Du Cloux, Advances in Math., 180 (2003), 146175]
on the combinatorial invariance of KazhdanLusztig polynomials.

The intersection cohomology of Schubert
varieties is a combinatorial invariant (21 pages)
Europ. J. Combinatorics,
25 (2004), 11511167.
We give an explicit and entirely posettheoretic way to compute,
for any permutation v, all the KazhdanLusztig 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.

KazhdanLusztig polynomials: History, Problems,
and Combinatorial Invariance (23 pages)
Seminaire Lotharingien de Combinatoire,
49 (2003), 613627.
This is an expository paper on KazhdanLusztig 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 KazhdanLusztig
and Rpolynomials. In the second one we present, as a sample, two results,
one on the Rpolynomials and one on the KazhdanLusztig 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 KazhdanLusztig and Rpolynomials 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), 30513082.
Combinatorial identities on Weyl groups of types A and B
are derived from special bases of the corresponding coinvariant algebras.
Using the GarsiaStanton 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 wellknown decomposition rules
of the coinvariant algebra and to generalize various identities.

Pkernels, IC bases and KazhdanLusztig polynomials (18 pages)
J. Algebra,
259 (2003), 613627.
In [R. P. Stanley, J. Amer. Math. Soc., 5 (1992), 805851]
Stanley introduced the concept of a Pkernel for any locally
finite partially ordered set P. In [J. Du, Algebraic groups and their
generalizations: quantum and infinitedimensional methods,
Proc. Sympos. Pure Math. 56, Amer. Math. Soc., 1994, 135148]
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 Wkernels the one corresponding to the KazhdanLusztig
basis of the Hecke algebra of W. Finally, we show that this Wkernel
factorizes as a product of other Wkernels, and that these provide a
solution to the YangBaxter equations for W.

Enumerative and combinatorial properties of Dyck partitions (23 pages)
J. Comb. Theory, Ser. A,
99 (2002), 5174.
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
KazhdanLusztig 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), 210224.
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.

KazhdanLusztig and Rpolynomials, Young's lattice, and Dyck partitions (34 pages)
Pacific J. Math.,
207 (2002), 257286.
We give explicit combinatorial product formulas for
the maximal parabolic KazhdanLusztig and Rpolynomials
of the symmetric group. These formulas imply that these
polynomials are combinatorial invariants, and that the
KazhdanLusztig ones are nonnegative. The combinatorial
formulas are most naturally stated in terms of Young's
lattice, and the one for the KazhdanLusztig polynomials
depends on a new class of skew partitions which are
closely related to Dyck paths.

Approximation Results for KazhdanLusztig polynomials (25 pages)
Adv. Studies Pure Math.,
28 (2000), 5781.
We use the theory of Pkernels
developed by Stanley in [R. P. Stanley, J. Amer. Math. Soc., 5 (1992),
805851] to approximate the KazhdanLusztig
polynomials with other ``KLSfunctions''
that are easier to compute. In particular, we characterize the pairs
u,v in W such that the KazhdanLusztig 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), 165184] and
[F. Brenti, Invent. Math., 118 (1994), 371394].

Mixed Bruhat operators and YangBaxter equations for Weyl groups
(22 pages)
(with S. Fomin and A. Postnikov), Int. Math. Research Notices,
(1999), No.8, 419441.
We introduce and study a family of
operators which act in the group algebra of a Weyl group W
and provide a multiparameter solution
to the quantum YangBaxter 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 qsymmetric functions arising from plethysm (34 pages)
J. Comb. Theory, Ser. A,
91 (2000), 137170.
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 noncrossing partitions.
Our results generalize previous ones by Haiman, Stanley, and the author.

Explicit formulae for some KazhdanLusztig polynomials (10 pages)
(with R. Simion) J. Algebraic Combinatorics,
11 (2000), 187196.
We consider the KazhdanLusztig 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 n2 or n1.
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 qanalogue of the Fibonacci number.
This establishes a conjecture due to M. Haiman.
Second, we obtain an explicit expression for
P_{e, 3 4 ... (n2) n (n1) 1 2}(q).
Our proofs rely on the recurrence relation satisfied by the KazhdanLusztig
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 KazhdanLusztigStanley functions (31 pages)
Advances in Math.,
148 (1999), 4474.
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
KazhdanLusztigStanley functions of a poset. As special cases this yields
new combinatorial formulas for the parabolic and inverse
parabolic KazhdanLusztig polynomials, for the generalized (toric) hvector
of an Eulerian poset, and for the LusztigVogan 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 wellknown 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 KazhdanLusztig polynomials (31 pages)
J. Amer. Math. Soc.,
11 (1998), 229259.
The purpose of this paper is to present a new nonrecursive
combinatorial formula for the KazhdanLusztig 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
KazhdanLusztig 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
nonrecursive formula known for the KazhdanLusztig 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), 127156.
We prove that several polynomials naturally
arising in combinatorics are Hilbert polynomials
of standard graded commutative kalgebras.

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, 451473.
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.

KazhdanLusztig and Rpolynomials from a combinatorial point of view (34 pages)
Discrete Math.,
193 (1998), 93116. Discrete Mathematics Editors' Choice for 1998
In this paper we survey and illustrate two combinatorial rules
for the computation of the KazhdanLusztig and Rpolynomials, 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 KazhdanLusztig and Rpolynomials.
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 KazhdanLusztig polynomials} (25 pages)
J. London Math. Soc.,
55 (1997), 448472.
We introduce two, related, families of polynomials, easily
computable by simple recursions into which any KazhdanLusztig
(and inverse KazhdanLusztig)
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 KazhdanLusztig polynomials in terms of paths
in a directed graph, and a completely combinatorial
reformulation of the nonnegativity conjecture

Upper and Lower Bounds for KazhdanLusztig polynomials (15 pages)
Europ. J. Combinatorics,
19 (1998), 283297.
We give upper and lower bounds for the KazhdanLusztig
polynomials of any Coxeter group W. If W is finite we
prove that, for any k > 0, the kth coefficient of
the KazhdanLusztig 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 LascouxSchutzenberger's
conjecture for all sufficiently long intervals, and gives
supporting evidence in favor of the DyerLusztig conjecture.

A Combinatorial Formula for KazhdanLusztig polynomials (24 pages)
Invent. Math.,
118 (1994), 371394.
Our aim in this work is to give a simple, nonrecursive,
combinatorial formula for any KazhdanLusztig 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 Rpolynomial to any (finite)
multichain of W (so that, for multichains of length 1, one
obtains, apart from sign, the usual Rpolynomials). Once this
has been done, then the KazhdanLusztig polynomial of a pair
u,v turns out to be just the sum, over all multichains from
u to v, of the corresponding (generalized) Rpolynomials.
The Rpolynomial of a multichain can be readily defined,
and computed, from the ordinary Rpolynomials.
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 KazhdanLusztig polynomials.

Logconcave and Unimodal sequences in Algebra, Combinatorics,
and Geometry: an update (19 pages)
Contemporary Math.,
178 (1994), 7189.
Logconcave 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 logconcavity and unimodality have oneline definitions,
to prove the unimodality or
logconcavity 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, Logconcave and unimodal sequences in Algebra,
Combinatorics and Geometry, Annals of the New York Academy
of Sciences, 576 (1989), 500534]
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 KazhdanLusztig Rpolynomials for Sn (31 pages)
Advances in Math.,
126 (1997), 2151.
We point out a deep and surprising connection between the
KazhdanLusztig Rpolynomials 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), 175218.
It was first observed in [F. Brenti, Unimodal, logconcave,
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
nonintersecting 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.

qEulerian polynomials arising from Coxeter groups (25 pages)
Europ. J. Combinatorics,
15 (1994), 417441.
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 qanalogues of them which are also qanalogues
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), 128.
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 SuperSchur Functions, Lattice Paths,
and Dotted Plane Partitions (38 pages)
Advances in Math.,
98 (1993), 2764.
Let s_L (x1,x2,... / y1,y2 ,... ) be
the superSchur 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
HallLittlewood symmetric functions, Schur's Qfunctions, qbinomial
coefficients, and qStirling 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
qanalogues of known results. Our main theorem also has several interesting
applications to the theory of total positivity.

Expansions of chromatic polynomials and logconcavity (28 pages)
Trans. Amer. Math. Soc.,
332 (1992), 729756.
In this paper we present several results and open
problems about logconcavity 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 logconcavity properties are studied. Four of these polynomials
have never been considered before in the literature and some yield new
expansions for the chromatic polynomial.

Logconcavity and combinatorial properties of Fibonacci Lattices (18 pages)
Europ. J. Combinatorics,
12 (1991), 459476.
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 logconcavity 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), 11331141.
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.