Recent papers by Margaret Readdy
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 bijective answer to a question of Simion
submitted,
with R. Ehrenborg and G. Hetyei. (8 pages).
We present a bijection between balanced Delannoy paths of length 2n
and the faces of the ndimensional Simion type B associahedron. This
polytope is also known as the BottTaubes polytope and the
cyclohedron. This bijection takes a path with k up steps (and k down
steps) to a (k1)dimensional face of Simion's type B
associahedron. We give two presentations of this bijection, one
recursive and one nonrecursive.

Some combinatorial identities appearing in the calculation of the
cohomology of Siegel modular varieties
submitted,
with R. Ehrenborg and S. Morel. (17 pages).
In Morel's computation of the intersection cohomology of
Shimura varieties, or of the L^{2} cohomology
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 wellunderstood.
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.

qStirling 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 qStirling identities using restricted
growth words. This includes a poset theoretic proof of Carlitz's
identity, a new proof of the qFrobenius identity of Garsia and Remmel
and of Ehrenborg's Hankel qStirling 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), 98114,
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+2gon.

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 nk and more compact than
that of FuReinerStantonThiem.
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 qbinomial.

The van der Waerden complex.
Journal of Number Theory,
172
(2017),
287300,
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 CWcomplex
whose cells asymptotically have dimension
at most log k/log log k.
We also give bounds on n and k which imply contractibility.

qStirling numbers: A new view.
Advances in Applied Math,
86
(2017),
5080,
with Y. Cai. (31 pages).
Extended abstract
accepted for the 2015 FPSAC
Conference under the title,
"Negative qStirling numbers".
We show the classical qStirling 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 qStirling number
S_{q}[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 qStirling 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),
299317.
This paper surveys recent results for flag enumeration of
polytopes, Bruhat graphs, balanced graphs,
Whitney stratified spaces and quasigraded 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),
114,
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 abindex of a simplicial poset,
we obtain the qanalogue of
n! times the hpolynomial 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 crosspolytope 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

Bruhat and balanced graphs.
submitted,
with R. Ehrenborg
(26 pages).
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 Rlabeling,
imply the existence of the
(nonhomogeneous) cdindex.
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 cdindex
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.

Manifold arrangements.
Journal of Combinatorial Theory Ser. A.
125
(2014),
214239,
with R. Ehrenborg.
We determine the cdindex 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 nsphere
and ntorus,
(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),
85128,
with R. Ehrenborg and M. Goresky.
We show the cdindex exists for manifolds whose boundary
has a Whitney stratification. The face poset of a stratification
is a quasigraded poset, that is, a poset endowed with an
orderpreserving rank function and a weighted zeta function.
The notion of a poset being Eulerian and the existence of the cdindex
extends in the quasigraded poset arena.
We also generalize the semisuspension 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),
857882,
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 SkolemMahlerLech theorem,
the
abseries of a level poset
is shown to be a rational generating function in
the noncommutative variables
a and
b.
In the case the poset is also Eulerian,
the analogous result holds for the
cdseries.
Using coalgebraic techniques a method is developed
to recognize the
cdseries
matrix of a level Eulerian poset.

Enumerative and asymptotic analysis of a moduli space.
Advances in Applied Math
47
(2011),
575588.
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 nonexistence of an Rlabeling.
Order,
28
(2011),
437442,
with R. Ehrenborg.
A family of Eulerian posets is described
which
does not have any Rlabeling.
The result uses a structure theorem
for Rlabelings of the butterfly poset.

The Rees product of posets.
Journal of Combinatorics,
2
(2011),
165191,
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 fvector of any graded poset changes under
the Rees product with the chain, and more generally, any tary 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),
211244,
with R. Ehrenborg.
We give an indepth 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 ELshellability, is a linear transformation
on flag vectors, for Eulerian posets restricts
to the BilleraEhrenborgReaddy 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 BilleraHsiaovan 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 AguiarBergeronSottile'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),
247264,
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),
481512,
with R. Ehrenborg and M. Slone.
We study affine and toric hyperplane arrangements.
Coalgebraic techniques are used to
extend the BilleraEhrenborgReaddy
omega map
between the flag fvector 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),
311326,
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),
283292,
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
easiertocompute
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),
339359,
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 preWDVV ring of physics and its topology.
The Ramanujan Journal,
Special issue on the Number Theory and Combinatorics in Physics,
10
(2005),
269281.
A simplicial complex arising from the
WDVV (WittenDijkgraafVerlindeVerlinde)
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 CohenMacaulay property)
are given.
Face enumeration of the complex and
the Hilbert series of the preWDVV ring
are also determined.

Homology of Newtonian coalgebras,
European Journal of Combinatorics,
23
(2002), 919927,
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 ncrosspolytope.
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), 150162,
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), 154167.
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), 322333,
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 fvectors,
Discrete and Computational Geometry,
23
(2000), 261271,
with R. Ehrenborg,
D. Johnston and
R. Rajagopalan.
We show how the flag fvector
changes
when cutting off any
face
of a polytope.
The result is expressed in terms of
explicit linear operators on cdpolynomials.
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), 389403,
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
cdindex 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), 3242,
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), 121126,
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
c2d
index of oriented matroids,
Journal of Combinatorial Theory Ser. A,
80
(1997), 79105,
with L. J. Billera and R. Ehrenborg.
An explicit method to compute the
cdindex
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
GianCarlo Rota
(Bruce E. Sagan and Richard P. Stanley, eds.),
Birkhauser Boston,
1998,
2340.
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), 273299,
with R. Ehrenborg.
Using the theory of
Newtonian coalgebras,
the cdindex is
shown to be a coalgebra homomorphism.
As a result,
easy to compute
expressions for the cdindex
of a polytope after applying geometric operations
(such as the pyramid and prism) are derived.

The rcubical lattice and a generalization
of the cdindex,
European Journal of Combinatorics,
17
(1996), 709725,
with R. Ehrenborg.
The notion of the cdindex for the cubical lattice
is generalized to an
rcdindex.
The coefficients enumerate augmented André
rsigned permutations.
A hypercube of inequalities
is
found for the Möbius function values of arbitrary
rank selections.

Juggling and applications to
qanalogues,
(gzipped PostScript)
Discrete Math.,
Special issue on Algebraic Combinatorics,
157
(1996), 107125,
with R. Ehrenborg.
By introducing a crossing statistic
in the study of simple juggling patterns,
a qanalogue 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}_{d1}$
is determined.
A combinatorial interpretation of the
qStirling 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
rsigned permutations,
Annales des Sciences Mathématiques
du Québec,
19
(1995), 173196,
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 Rlabelings is extended to linear edgelabelings
to prove an analogue of
Björner
and Stanley's theorem
on Rlabelings.
(These ideas were later used
Bergeron and Sottile in their construction of a quasisymetric
generating function for chains having labels with fixed
descents.)
The paper ends with the construction of a linear analogue
of the 4cubical lattice, similar to the isotropic subspace
lattice.

Extremal problems for the Möbius function
in the face lattice of the noctahedron,
(gzipped PostScript)
Discrete Math.,
Special issue on Algebraic Combinatorics,
139
(1995), 361380.
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 ndimensional crosspolytope are studied.
The case of arbitrary rank selections follows
from an observation of Stanley on the
nonnegativity of the
cdindex of polytopes.
English translator of the French text,
Espèces de structures et combinatoire des
structures arborescentes

Combinatorial Species and Treelike Structures,
by François Bergeron, Gilbert Labelle, and Pierre Leroux,
Encyclopedia of
Mathematics and its Applications,
Cambridge University Press, 1997.
Six of my sequences appear in
The OnLine 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 npointed
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 npointed
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 4signed permutations):
1, 1, 7, 47, 497, 6241, 95767, 1704527,
34741217, 796079041, ...;

A7286
(Alternating augmented 3signed permutations)
1, 1, 5, 26, 205
1936, 22265, 297296, 4544185, 78098176, ...;

A7788
(Augmented André 3signed permutations)
1, 1, 4, 19, 136, 1201, 13024, 165619, 2425216,
40132801,...
margaret.readdy at uky.edu