Cyclotomic factors of the descent set polynomial.
submitted, with D. Chebikin, R. Ehrenborg, and P. Pylyavskyy (20 pages).
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.
submitted, with R. Ehrenborg and M. Slone (28 pages).
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.
The Tchebyshev transforms of the first and second kind.
to appear, Annals of Combinatorics, with R. Ehrenborg (35 pages).
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.
Exponential Dowling structures,
to appear, European Journal of Combinatorics, with R. Ehrenborg (17 pages).
We extend Stanley's theory of exponential structures to that of exponential Dowling structures.
The
Möbius
function of partitions with restricted
block sizes.
with R. Ehrenborg Advances in Applied Math. 39 (2007), 283-292.
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.
with R. Ehrenborg, Journal of Combinatorial Theory Ser. A. 114 (2007), 339-359.
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.
with R. Ehrenborg
European Journal of Combinatorics, 23 (2002), 919-927.
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.
with R. Ehrenborg and M. Levin
Journal of Combinatorial Theory Ser. A, 98 (2002), 150-162.
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.
with R. Ehrenborg
J. Combin. Theory Ser. A, 91 (2000), 322-333.
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.
with R. Ehrenborg, D. Johnston and R. Rajagopalan
Discrete and Computational Geometry, 23 (2000), 261-271.
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.
with R. Ehrenborg
Discrete and Computational Geometry, 21 (1999), 389-403.
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.
with R. Ehrenborg
Advances in Mathematics, 134 (1998), 32-42.
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.
with R. Ehrenborg and E. Steingrímsson
Journal of Combinatorial Theory Ser. A, 81 (1998), 121-126.
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.
with L. J. Billera and R. Ehrenborg
Journal of Combinatorial Theory Ser. A, 80 (1997), 79-105.
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.
with R. Ehrenborg
Journal of Algebraic Combinatorics, 8 (1998), 273-299.
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.
with R. Ehrenborg
European Journal of Combinatorics, 17 (1996), 709-725.
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.
with R. Ehrenborg
Discrete Math., Special issue on Algebraic Combinatorics, 157 (1996), 107-125.
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.
with R. Ehrenborg
Annales des Sciences Mathématiques du Québec, 19 (1995), 173--196.
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:
-
Five of my sequences appear in
The On-Line Encyclopedia
of Integer Sequences,
ed. by N. J. A. Sloane:
- 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,...
readdy at ms.uky.edu