# Recent papers by Margaret Readdy

Papers are sorted in reverse chronological order according to the date they were originally written.

Unless otherwise noted, all files are pdf.
• A generalization of combinatorial identities for stable discrete series constants submitted, with R. Ehrenborg and S. Morel. (52 pages).
This article is concerned with the constants appearing in Harish-Chandra's character formula for stable discrete series of real reductive groups. In Harish-Chandra' work the only information we have about these constants is that they are uniquely determined by an inductive property. Later Goresky-Kottwitz-MacPherson and Herb gave different formulas for these constants. We generalize these formulas to the case of arbitrary finite Coxeter groups (in this setting, discrete series no longer make sense), and give a direct proof that the two formulas agree. We actually prove a slightly more general identity that also implies the combinatorial identity underlying the discrete series character identities of Morel (2011). We also introduce a signed convolution of valuations on polyhedral cones in Euclidean space and show that the resulting function is a valuation. This gives a theoretical framework for the valuation appearing in Goresky-Kottwitz-MacPherson (1997). In Appendix B we extend the notion of 2-structures (due to Herb) to pseudo-root systems.
• Classification of uniform flag triangulations of the Legendre polytope Acta Mathematica Hungarica, to appear with R. Ehrenborg and G. Hetyei. (45 pages).
The Legendre polytope, also known as the type A full root polytope, is the convex hull of all pairwise differences of the standard basis vectors. We completely classify all flag triangulations of this polytope that are uniform in the sense that the edges may be described as a function of the relative order of the indices of the four basis vectors involved. These triangulations fall naturally into three classes: the lex class, the revlex class and the Simion class. We also determine that the refined face counts of these triangulations only depend on the class of the triangulations. The refined face generating functions are expressed in terms of the Catalan and Delannoy generating functions and the modified Bessel function of the first kind.
• Balanced and Bruhat graphs. Annals of Combinatorics, 24 (2020), no. 3, 587--617, with R. Ehrenborg.
We generalize chain enumeration in graded posets by relaxing the graded, poset and Eulerian requirements. The resulting balanced digraphs, which include the classical Eulerian posets having an R-labeling, imply the existence of the (non-homogeneous) cd-index. An analogue of Alexander duality for balanced digraphs holds. For Bruhat graphs of Coxeter groups, an important family of balanced graphs, our theory gives elementary proofs of the existence of the complete cd-index and its properties. The rising and falling quasisymmetric functions of a labeled acyclic digraph are introduced and shown to be Hopf algebra homomorpisms mapping balanced digraphs to the Stembridge peak algebra.
• A bijective answer to a question of Simion Journal of Integer Sequences, 22 (2019) Article 19.1.2, with R. Ehrenborg and G. Hetyei. (12 pages).
We present a bijection between balanced Delannoy paths of length 2n and the faces of the n-dimensional Simion type B associahedron. This polytope is also known as the Bott-Taubes polytope and the cyclohedron. This bijection takes a path with k up steps (and k down steps) to a (k-1)-dimensional face of Simion's type B associahedron. We give two presentations of this bijection, one recursive and one non-recursive.
• Some combinatorial identities appearing in the calculation of the cohomology of Siegel modular varieties Algebraic Combinatorics, 2 (2019), no. 5, 863--878, with R. Ehrenborg and S. Morel.
In Morel's computation of the intersection cohomology of Shimura varieties, or of the L2 co-homology of equal rank locally symmetric spaces, combinatorial identities involving averaged discrete series characters of real reductive groups play a large technical role. These identities can become very complicated and are not always well-understood. We propose a geometric approach to these identities in the case of Siegel modular varieties using the combinatorial properties of the Coxeter complex of the symmetric group.
• q-Stirling identities revisited Electronic Journal of Combinatorics, 25 Issue 1 (2018), Paper #P1.37, with R. Ehrenborg and Y. Cai. (18 pages).
We give combinatorial proofs of q-Stirling identities using restricted growth words. This includes a poset theoretic proof of Carlitz's identity, a new proof of the q-Frobenius identity of Garsia and Remmel and of Ehrenborg's Hankel q-Stirling determinantal identity. We also develop a two parameter generalization to unify identities of Mercier and include a symmetric function version.
• Simion's type B associahedron is a pulling triangulation of the Legendre polytope. Discrete and Computational Geometry, 60 (2018), 98--114, with R. Ehrenborg and G. Hetyei.
We show that the Simion type B associahedron is combinatorially equivalent to a pulling triangulation of the type A root polytope called the Legendre polytope. Furthermore, we show that every pulling triangulation of the Legendre polytope yields a flag complex. Our triangulation refines a decomposition of the Legendre polytope given by Cho. We extend Cho's cyclic group action to the triangulation in such a way that it corresponds to rotating centrally symmetric triangulations of a regular 2n+2-gon.
• The Gaussian coefficient revisited. Journal of Integer Sequences, 19 (2016), Article 16.7.8, with R. Ehrenborg. (8 pages).
We give a new q-(1+q)-analogue of the Gaussian coefficient which is symmetric in k and n-k and more compact than that of Fu--Reiner--Stanton--Thiem. Underlying our q-(1+q)-analogue is a Boolean algebra decomposition of an associated poset. These ideas are extended to the Birkhoff transform of any poset. We end with a discussion of higher analogues of the q-binomial.
• The van der Waerden complex. Journal of Number Theory, 172 (2017), 287--300, with R. Ehrenborg, L. Govindaiah and P. Park.
We introduce the van der Waerden complex vdW(n,k), a simplicial complex whose facets correspond to arithmetic progressions of length k on the vertex set {1, 2, ..., n}. We show vdW(n,k) is homotopy equivalent to a CW-complex whose cells asymptotically have dimension at most log k/log log k. We also give bounds on n and k which imply contractibility.
• q-Stirling numbers: A new view. Advances in Applied Math, 86 (2017), 50--80, with Y. Cai. (31 pages).
Extended abstract accepted for the 2015 FPSAC Conference under the title, "Negative q-Stirling numbers".
We show the classical q-Stirling numbers of the second kind can be expressed more compactly as a pair of statistics on a subset of restricted growth words. The resulting expressions are polynomials in q and 1 + q. We extend this enumerative result via a decomposition of a new poset Π(n, k) which we call the Stirling poset of the second kind. Its rank generating function is the q-Stirling number Sq[n,k]. The Stirling poset of the second kind supports an algebraic complex and a basis for integer homology is determined. A parallel enumerative, poset theoretic and homological study for the q-Stirling numbers of the first kind is done. Letting t = 1 + q we give a bijective argument showing the (q, t)-Stirling numbers of the first and second kind are orthogonal.
• Euler enumeration and beyond. Journal of Combinatorial Mathematics and Combinatorial Computing, 98 (2016), 299--317.
This paper surveys recent results for flag enumeration of polytopes, Bruhat graphs, balanced graphs, Whitney stratified spaces and quasi-graded posets. It is based upon a one hour invited talk given by the author at the 28th Midwest Conference on Combinatorics, Cryptography and Computing in Fall 2014.
• A poset view of the major index.
Advances in Applied Math, 62 (2015), 1--14, with R. Ehrenborg.
We introduce the Major MacMahon map from ℤ⟨a,b⟩ to ℤ[q] and show how this map commutes with the pyramid and bipyramid operators. When applied to the ab-index of a simplicial poset, we obtain the q-analogue of n! times the h-polynomial of the polytope. Applying the map to the Boolean algebra gives the distribution of the major index on the symmetric group, a seminal result due to MacMahon. When applied to the cross-polytope we obtain the distribution of one of the major indexes on signed permutations due to Reiner.
• Polytopes.
Lectures Notes for May 2013 WAM Program (Institute for Advanced Study & Princeton University) (39 pages).
Lecture I: Introduction to polytopes and face enumeration
Lecture II: Coalgebraic techniques and geometric operations
Lecture III: Hyperplane arrangements & zonotopes; Inequalities: A first look
Lecture IV: New horizons
• Manifold arrangements.
Journal of Combinatorial Theory Ser. A. 125 (2014), 214--239, with R. Ehrenborg.
We determine the cd-index of the induced subdivision arising from a manifold arrangement. This generalizes earlier results in several directions: (i) One can work with manifolds other than the n-sphere and n-torus, (ii) the induced subdivision is a Whitney stratification, and (iii) the submanifolds in the arrangement are no longer required to be codimension one.
• Euler flag enumeration of Whitney stratified spaces.
Advances in Mathematics, 268 (2015), 85--128, with R. Ehrenborg and M. Goresky.
We show the cd-index exists for manifolds whose boundary has a Whitney stratification. The face poset of a stratification is a quasi-graded poset, that is, a poset endowed with an order-preserving rank function and a weighted zeta function. The notion of a poset being Eulerian and the existence of the cd-index extends in the quasi-graded poset arena. We also generalize the semi-suspension operation to that of embedding a complex in the boundary of a higher dimensional ball and study the shelling components of the simplex.
• Level Eulerian posets.
Graphs and Combinatorics, 29 (2013), 857--882, with R. Ehrenborg and G. Hetyei.
We introduce the notion of level posets, that is, infinite posets where every two adjacent ranks have the same bipartitie graph. We determine the longest interval one needs to check to verify the Eulerian property when the adjacency matrix is indecomposable and show the poset has even order. A condition for verifying shellability is introduced and is automated using the algebra of walks. Applying the Skolem--Mahler--Lech theorem, the ab-series of a level poset is shown to be a rational generating function in the non-commutative variables a and b. In the case the poset is also Eulerian, the analogous result holds for the cd-series. Using coalgebraic techniques a method is developed to recognize the cd-series matrix of a level Eulerian poset.
• Enumerative and asymptotic analysis of a moduli space.
Advances in Applied Math 47 (2011), 575--588.
This paper focuses on combinatorial aspects of the Hilbert series of the cohomology ring of the moduli space of stable pointed curves of genus zero. We show its graded Hilbert series satisfies an integral operator identity. This is used to give asymptotic behavior, and in some cases, exact values, of the coefficients themselves. We then study the total dimension, that is, the sum of the coefficients of the Hilbert series. Its asymptotic behavior surprisingly involves the Lambert W function, which has applications to classical tree enumeration, signal processing and fluid mechanics.
• On the non-existence of an R-labeling.
Order, 28 (2011), 437--442, with R. Ehrenborg.
A family of Eulerian posets is described which does not have any R-labeling. The result uses a structure theorem for R-labelings of the butterfly poset.
• The Rees product of posets.
Journal of Combinatorics, 2 (2011), 165--191, with P. Muldoon Brown.
We study enumerative and homological properties of the Rees product of the cubical lattice with the chain. We also determine how the flag f-vector of any graded poset changes under the Rees product with the chain, and more generally, any t-ary tree. As a corollary, the Mobius function of the Rees product of any graded poset with the chain is exactly the same as the Rees product of its dual with the chain.
• The Tchebyshev transforms of the first and second kind.
Annals of Combinatorics, 41 (2010), 211-244, with R. Ehrenborg.
We give an in-depth study of the Tchebyshev transforms of the first and second kind of a poset, recently discovered by Hetyei. Many new properties are revealed, including: preserves EL-shellability, is a linear transformation on flag vectors, for Eulerian posets restricts to the Billera-Ehrenborg-Readdy omega map of oriented matroids, coincides with Stembridges peak enumerator in the Eulerian case, is a Hopf algebra endomorpism on QSym. The complete spectrum is also determined, generalizing work of Billera-Hsiao-van Willigenburg. Analogous to Ehrenborg's classical quasisymmetric function of a poset, the notion of a type B quasisymmetric function of a poset is developed. A general study of chain maps is initiated which has connections with Aguiar-Bergeron-Sottile's work on the terminal object in the category of combinatorial Hopf algebras.
• Cyclotomic factors of the descent set polynomial.
Journal of Combinatorial Theory Ser. A. 116 (2009), 247-264, with D. Chebikin, R. Ehrenborg, and P. Pylyavskyy.
The notion of the descent set polynomial is introduced as an alternative way of encoding the sizes of descent classes of permutations. These polynomials exhibit interesting factorization patterns. We explore the question of when particular cyclotomic factors divide these polynomials. As an instance we deduce that the proportion of odd entries in the descent set statistics in the symmetric group on n elements only depends on the number on 1's in the binary expansion of n. We observe similar properties for the signed descent set statistics.
• Affine and toric hyperplane arrangements.
Discrete and Computational Geometry 41 (2009), 481-512, with R. Ehrenborg and M. Slone.
We study affine and toric hyperplane arrangements. Coalgebraic techniques are used to extend the Billera-Ehrenborg-Readdy omega map between the flag f-vector and intersection poset for these families of arrangements. Zaslavsky's fundamental results on the number of bounded and unbounded regions are generalized for toric arrangements. This paper ends with a wealth of problems involving regular subdivisions of manifolds.
• Exponential Dowling structures,
European Journal of Combinatorics, 30 (2009), 311-326, with R. Ehrenborg.
We extend Stanley's theory of exponential structures to that of exponential Dowling structures.
• The Möbius function of partitions with restricted block sizes.
Advances in Applied Math. 39 (2007), 283-292, with R. Ehrenborg.
We study filters in the partition lattice formed by restricting to partitions by type. The Möbius function is determined in terms of the easier-to-compute descent set statistics on permutations and the Möbius function of filters in the lattice of integer compositions. When the underlying integer partition is a knapsack partition, the Möbius function on integer compositions is determined by a topological argument. In this proof the permutahedron makes a cameo appearance.
• Classification of the factorial functions of Eulerian binomial and Sheffer posets.
Journal of Combinatorial Theory Ser. A. 114 (2007), 339-359, with R. Ehrenborg.
We completely classify the factorial functions of Eulerian binomial and Eulerian Sheffer posets. Imposing the further condition that the poset be a lattice forces the poset to be the infinite Boolean algebra or the infinite cubical lattice. Many interesting constructions and examples are included.
• The pre-WDVV ring of physics and its topology.
The Ramanujan Journal, Special issue on the Number Theory and Combinatorics in Physics, 10 (2005), 269-281.
A simplicial complex arising from the WDVV (Witten-Dijkgraaf-Verlinde-Verlinde) equations of string theory is shown to correspond to the Whitehouse complex. Using discrete Morse theory, elementary proofs of its topological structure (homotopy equivalent to a wedge of spheres, the Cohen-Macaulay property) are given. Face enumeration of the complex and the Hilbert series of the pre-WDVV ring are also determined.
• Homology of Newtonian coalgebras,
European Journal of Combinatorics, 23 (2002), 919-927, with R. Ehrenborg.
The homology groups of the chain complex of two important Newtonian coalgebras arising in the study of flag vectors of polytopes are computed. The homology of R<a,b> corresponds to the homology of the boundary of the n-crosspolytope. For R<c,d> the homology depends upon the characteristic of the ring. In the characteristic 2 case the homology is computed via cubical complexes arising from distributive lattices. The integer homology of R<c,d> is also characterized.
• A probabilistic approach to the descent statistic,
Journal of Combinatorial Theory Ser. A, 98 (2002), 150-162, with R. Ehrenborg and M. Levin.
Quadratic inequalities for the descent set of permutations are developed using a probabilistic reformulation of the descent statistic.
• The Yuri Manin ring and its B_n analogue,
Advances in Applied Math, 26 (2001), 154-167.
A combinatorial interpretation is found for a family of commutative algebras arising in string theory. A signed analogue is also developed.
• The Dowling transform of subspace arrangements,
J. Combin. Theory Ser. A, 91 (2000), 322-333, with R. Ehrenborg.
The Dowling transform of a real frame arrangement is introduced. As a special case, it sends the braid arrangement of type A to the Dowling arrangement. We show how the characteristic polynomial changes under this transformation, as well as the fact it preserves supersolvability.
• Cutting polytopes and flag f-vectors,
Discrete and Computational Geometry, 23 (2000), 261-271, with R. Ehrenborg, D. Johnston and R. Rajagopalan.
We show how the flag f-vector changes when cutting off any face of a polytope. The result is expressed in terms of explicit linear operators on cd-polynomials. The operation of contracting any face of the polytope is also considered.
• On flag vectors, the Dowling lattice and braid arrangements,
Discrete and Computational Geometry, 21 (1999), 389-403, with R. Ehrenborg.
Flag vectors of complex hyperplane arrangements whose intersection lattices are a natural generalization of the partition lattice are studied. The real case corresponds to the braid arrangements of types A and B. A recursive formula for the cd-index of the lattice of regions of these two braid arrangements is obtained which uses the exponents of the corresponding Weyl group.
• On valuations, the characteristic polynomial and complex subspace arrangements,
Advances in Mathematics, 134 (1998), 32-42, with R. Ehrenborg.
A new combinatorial method to determine the characteristic polynomial of any subspace arrangement defined over an infinite field is introduced. This generalizes work of Blass and Sagan's on subarrangements of the braid arrangement of type B and Athanasiadis' mod q method.
• Mixed volumes and slices of the cube,
Journal of Combinatorial Theory Ser. A, 81 (1998), 121-126, with R. Ehrenborg and E. Steingrimsson.
Generalizing a result of Euler, a combinatorial interpretation for the mixed volumes of two adjacent slices from the unit cube in terms of a refinement of the Eulerian numbers is given.
• The c-2d -index of oriented matroids,
Journal of Combinatorial Theory Ser. A, 80 (1997), 79-105, with L. J. Billera and R. Ehrenborg.
An explicit method to compute the cd-index of the lattice of regions of an oriented matroid from the flag vector data of the corresponding lattice of flats is obtained.
• The cd -index of zonotopes and arrangements,
with L. J. Billera and R. Ehrenborg
Mathematical essays in honor of Gian-Carlo Rota
(Bruce E. Sagan and Richard P. Stanley, eds.), Birkhauser Boston, 1998, 23-40.
A concise proof that flag vectors of polytopes formed by the pyramid and prism operations span the space of all flag vectors of polytopes is given. It is also shown that zonotopes span, that is, the flag vectors of zonotopes span the same space.
• Coproducts and the cd -index,
Journal of Algebraic Combinatorics, 8 (1998), 273-299, with R. Ehrenborg.
Using the theory of Newtonian coalgebras, the cd-index is shown to be a coalgebra homomorphism. As a result, easy to compute expressions for the cd-index of a polytope after applying geometric operations (such as the pyramid and prism) are derived.
• The r-cubical lattice and a generalization of the cd-index,
European Journal of Combinatorics, 17 (1996), 709-725, with R. Ehrenborg.
The notion of the cd-index for the cubical lattice is generalized to an r-cd-index. The coefficients enumerate augmented André r-signed permutations. A hypercube of inequalities is found for the Möbius function values of arbitrary rank selections.
• Juggling and applications to q-analogues, (gzipped PostScript)
Discrete Math., Special issue on Algebraic Combinatorics, 157 (1996), 107-125, with R. Ehrenborg.
By introducing a crossing statistic in the study of simple juggling patterns, a q-analogue of Buhler, Eisenbud, Graham and Wright's enumerative result for juggling patterns is found. The first combinatorial verification of the Poincaré series of the affine Weyl group \$\widetilde{A}_{d-1}\$ is determined. A combinatorial interpretation of the q-Stirling numbers of the second kind, equivalent to Garsia and Remmel's rook placements on a Ferrer's board, is found. This leads to a bijective proof of an identity of Carlitz.
• Sheffer posets and r-signed permutations,
Annales des Sciences Mathématiques du Québec, 19 (1995), 173--196, with R. Ehrenborg.
Doubilet, Rota and Stanley's concept of a binomial poset is generalized to a larger class of posets, called Sheffer posets. The theory of R-labelings is extended to linear edge-labelings to prove an analogue of Björner and Stanley's theorem on R-labelings. (These ideas were later used Bergeron and Sottile in their construction of a quasi-symetric generating function for chains having labels with fixed descents.) The paper ends with the construction of a linear analogue of the 4-cubical lattice, similar to the isotropic subspace lattice.
• Extremal problems for the Möbius function in the face lattice of the n-octahedron, (gzipped PostScript)
Discrete Math., Special issue on Algebraic Combinatorics, 139 (1995), 361-380.
Extremal problems for the Möbius function of three families of subsets (lower order ideals, intervals of ranks and arbitrary rank selections) from the face lattice of an n-dimensional crosspolytope are studied. The case of arbitrary rank selections follows from an observation of Stanley on the nonnegativity of the cd-index of polytopes.

### Translation:

English translator of the French text,
Espèces de structures et combinatoire des structures arborescentes --
Combinatorial Species and Tree-like Structures,

by François Bergeron, Gilbert Labelle, and Pierre Leroux,
Encyclopedia of Mathematics and its Applications,
Cambridge University Press, 1997.

### Sequences:

Six of my sequences appear in The On-Line Encyclopedia of Integer Sequences, ed. by N. J. A. Sloane:

• A108917 (Number of knapsack partitions of n): 1, 1, 2, 3, 4, 6, 7, 11, 12, 17, 19, 29, 25, 41, 41, 58, 56, 84, 75, 117, 99, 149, 140, 211, 172, 259, 237, 334, 292, 434, 348, 547, 465, 664, 588, 836, 681, 1014, 873, 1243, 1039, 1502, 1224, 1822, 1507, 2094, 1810, 2605, 2118, 3038, 2516, ...
• A074059 (Dimension of the cohomology ring of the moduli space of n-pointed stable curves of genus 0 satisfying the the WDVV equations of physics): 1, 2, 7, 34, 213;
• A074060 (Graded dimension of the cohomology ring of the moduli space of n-pointed stable curves of genus 0 satisfying the the WDVV equations of physics): 1, 1, 1, 1, 5, 1, 1, 16, 16, 1, 1, 42, 127, 42, 1;
• A6873 (Alternating augmented 4-signed permutations): 1, 1, 7, 47, 497, 6241, 95767, 1704527, 34741217, 796079041, ...;
• A7286 (Alternating augmented 3-signed permutations) 1, 1, 5, 26, 205 1936, 22265, 297296, 4544185, 78098176, ...;
• A7788 (Augmented André 3-signed permutations) 1, 1, 4, 19, 136, 1201, 13024, 165619, 2425216, 40132801,...