Catalan-Spitzer permutations
Enumerative Combinatorics and Applications 4 Issue 2 (2024), Article S2R14, with R. Ehrenborg and G. Hetyei.
doi.org/10.54550/ECA2024V4S2R15
The Chung-Feller theorem assserts the number of lattice paths from the origin to (2n,0) with northeast and southeast steps having 2r steps above the x-axis is independent of r, and is given by the Catalan number Cn. Generalizations are due to Raney and Huq. We study two classes of permutations related to the proof of Spitzer's lemma and Huq's generalization of the Chung-Feller theorem. This leads to a generalization of Flajolet's results from continued fractions to continuants, as well as a restricted variant of the Foata-Strehl group action.
Pizza and 2-structures
Discrete and Computational Geometry 70 (2023), 1221-1244, with R. Ehrenborg and S. Morel.
doi.org/10.1007/s00454-023-00600-2
This paper gives a dissection proof of the n-dimensional pizza theorem that the authors prove in a previous article. The alternating sum identity is lifted to an abstract dissection group where the volume of the regions is replaced by any affine isometry invariant valuation. This includes all cases of the intrinsic volumes. The key ingredient is to relate the alternating sums of the values of certain valuations over the chambers of a Coxeter arrangement to similar alternating sums of simpler subarrangements called 2-structures.
Sharing pizza in n dimensions
Transactions of the AMS, 375 (2022), no. 8, 5829--5857, with R. Ehrenborg and S. Morel.
We introduce and prove the n-dimensional Pizza Theorem: For H a hyperplane arrangement in n-dimensional Euclidean space containing K a measurable set of finite volume, the pizza quantity of K is the alternating sum of the volumes of the regions obtained by intersecting K with the arrangement H. We prove that if H is a Coxeter arrangement different from A1n such that the group of isometries W generated by the reflections in the hyperplanes of H contains the map -id, and if K is a translate of a convex body that is stable under W and contains the origin, then the pizza quantity of K is equal to zero. Our main tool is an induction formula for the pizza quantity involving a subarrangement of the restricted arrangement on hyperplanes of H that we call the even restricted arrangement. More generally, we prove that for a class of arrangements that we call even (this includes the aforementioned Coxeter arrangements) and for a sufficiently symmetric set K, the pizza quantity of K+a is polynomial in a for a small enough, for example if K is convex and the origin is in K+a. We obtain stronger results in the case of balls, more generally, convex bodies bounded by quadratic hypersurfaces. For example, we prove that the pizza quantity of the ball centered at a having radius R ≥ |a| vanishes for a Coxeter arrangement H with |H| - n an even positive integer. We also prove the Pizza Theorem for the surface volume: When H is a Coxeter arrangement and |H| - n is a nonnegative even integer, for an n-dimensional ball the alternating sum of the (n-1)-dimensional surface volumes of the regions is equal to zero.
A generalization of combinatorial identities
for stable discrete series constants
Journal of Combinatorial Algebra, 6 (2022), no. 1, 109--183, with R. Ehrenborg and S. Morel.
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, 163 (2021), 462--511, with R. Ehrenborg and G. Hetyei.
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. ***
Refined face count in uniform triangulations of
the Legendre polytope.
Sém. Lothar. Combin. 82B (2020), Article 13, 12 pp., with R. Ehrenborg and G. Hetyei.
Recall the Legendre polytope is the type A full root polytope. We describe all flag triangulations that are uniform in the sense that all the edges may be described as a function of the relative order of the indices of the four basis vectors involved. We also determine the refined face counts of these triangulations.
A bijective answer to a question of Simion
Journal of Integer Sequences,
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,
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.
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.
Discrete and Computational Geometry,
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.
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.
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.
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.
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.
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.
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
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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 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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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,...
Other Publications:
-
Women's history month, Introduction and Profiles of Twenty-Seven Mathematicians
Notices of the American Mathematical Society 65 (2018), no. 3, 248–303, edited with C. Taylor.
-
Early women mathematicians in Princeton
Notices of the American Mathematical Society 65 (2018), no. 3, 304--305, edited with C. Taylor.
© 2000 Margaret A. Readdy.
margaret.readdy at uky.edu