Some papers- Vic Reiner

Koszulity, supersolvability and Stirling Representations (with Ayah Almousa and Sheila Sundaram)
Supersolvable hyperplane arrangements and matroids are known to give rise to certain Koszul algebras, namely their Orlik-Solomon algebras and graded Varchenko-Gel'fand algebras. We explore how this interacts with group actions, particularly for the braid arrangement and the action of the symmetric group, where the Hilbert functions of the algebras and their Koszul duals are given by Stirling numbers of the first and second kinds, respectively. The corresponding symmetric group representations exhibit branching rules that interpret Stirling number recurrences, which are shown to apply to all supersolvable arrangements. They also enjoy representation stability properties that follow from Koszul duality.
(Math arXiv preprint arXiv:2404.10858 )
Sandpile groups for cones over trees (with Dorian Smith)
Sandpile groups are a subtle graph isomorphism invariant, in the form of a finite abelian group, whose cardinality is the number of spanning trees in the graph. We study their group structure for graphs obtained by attaching a cone vertex to a tree. For example, it is shown that the number of generators of the sandpile group is at most one less than the number of leaves in the tree. For trees on a fixed number of vertices, the paths and stars are shown to provide extreme behavior, not only for the number of generators, but also for the number of spanning trees, and for Tutte polynomial evaluations that count the recurrent sandpile configurations by their numbers of chips.
(Math arXiv preprint arXiv:2402.15453 )
Chow rings of matroids as permutation representations (with Robert Angarone and Anastasia Nathanson)
Given a matroid and a group of its matroid automorphisms, we study the induced group action on the Chow ring of the matroid. This turns out to always be a permutation action. Work of Adiprasito, Huh and Katz showed that the Chow ring satisfies Poincaré duality and the Hard Lefschetz theorem. We lift these to statements about this permutation action, and suggest further conjectures in this vein.
(Math arXiv preprint arXiv:2309.14312 )
Equivariant resolutions over Veronese rings (with Ayah Almousa, Michael Perlman, Alexandra Pevzner, Keller VandeBogert)
Working in a polynomial ring S=k[x1,...,xn] where k is an arbitrary commutative ring with 1, we consider the dth Veronese subalgebras R=S(d), as well as natural R-submodules M=S(≥r,d) inside S. We develop and use characteristic-free theory of Schur functors associated to ribbon skew diagrams as a tool to construct simple GLn(k)-equivariant minimal free R-resolutions for the quotient ring k=R/R+ and for these modules M. These also lead to elegant descriptions of TorRi(M,M') for all i and HomR(M,M') for any pair of these modules M,M'.
(Math arXiv preprint arXiv:2210.16342, journal version)
Invariant theory for the free left-regular band and a q-analogue (with Sarah Brauner and Patricia Commins))
We examine from an invariant theory viewpoint the monoid algebras for two monoids having large symmetry groups: the free left-regular band on n letters, acted on by the symmetric group, and one of its q-analogues, acted on by the finite general linear group. In both cases, we show that the invariant subalgebras are semisimple commutative algebras, and characterize them using Stirling and q-Stirling numbers. We then use results from the theory of random walks and random-to-top shuffling to decompose the entire monoid algebra into irreducibles, simultaneously as a module over the invariant ring and as a group representation. Our irreducible decompositions are described in terms of derangement symmetric functions introduced by Désarménien and Wachs.
(Math arXiv preprint arXiv:2206.11406 )
Topology of augmented Bergman complexes (with E. Bullock, A. Kelley, K. Ren, G. Shemy, D. Shen, B. Sun, A. Tao, J. Zhang)
The augmented Bergman complex of a matroid is a simplicial complex introduced recently in work of Braden, Huh, Matherne, Proudfoot and Wang. It may be viewed as a hybrid of two well-studied pure shellable simplicial complexes associated to matroids: the independent set complex and Bergman complex. It is shown here that the augmented Bergman complex is also shellable, via two different families of shelling orders. Furthermore, comparing the description of its homotopy type induced from the two shellings re-interprets a known convolution formula counting bases of the matroid. The representation of the automorphism group of the matroid on the homology of the augmented Bergman complex turns out to have a surprisingly simple description. This last fact is generalized to closures beyond those coming from a matroid.
(Math arXiv preprint arXiv:2108.13394)
The "Grothendieck to Lascoux" conjecture (with A. Yong)
This report formulates a conjectural combinatorial rule that positively expands Grothendieck polynomials into Lascoux polynomials. It generalizes one such formula expanding Schubert polynomials into key polynomials, and refines another one expanding stable Grothendieck polynomials.
(Math arXiv preprint arXiv:2102.12399)
A colorful Hochster formula and universal parameters for face rings (with A. Adams)
This paper has two related parts. The first generalizes Hochster's formula on resolutions of Stanley-Reisner rings to a colorful version, applicable to any proper vertex-coloring of a simplicial complex. The second part examines a universal system of parameters for Stanley-Reisner rings of simplicial complexes, and more generally, face rings of simplicial posets. These parameters have good properties, including being fixed under symmetries, and detecting depth of the face ring. Moreover, when resolving the face ring over these parameters, the shape is predicted, conjecturally, by the colorful Hochster formula.
(Math arXiv preprint arXiv:2007.13021, journal version,)
Cyclic sieving for cyclic codes (with A. Mason and S. Sridhar)
Prompted by a question of Jim Propp, this paper examines the cyclic sieving phenomenon (CSP) in certain cyclic codes. For example, it is shown that, among dual Hamming codes over Fq, the generating function for codedwords according to the major index statistic (resp. the inversion statistic) gives rise to a CSP when q=2 or q=3 (resp. when q=2). A byproduct is a curious characterization of the irreducible polynomials in F2[x] and F3[x] that are primitive.
(Math arXiv preprint arXiv:2004.11998)
Invariant theory for coincidental complex reflection groups (with A.V. Shepler and E. Sommers)
V.F. Molchanov considered the Hilbert series for the space of invariant skew-symmetric tensors and dual tensors with polynomial coefficients under the action of a real reflection group, and speculated that it had a certain product formula involving the exponents of the group. We show that Molchanov's speculation is false in general but holds for all coincidental complex reflection groups when appropriately modified using exponents and co-exponents. These are the irreducible well-generated (i.e., duality) reflection groups with exponents forming an arithmetic progression and include many real reflection groups and all non-real Shephard groups, e.g., the Shephard-Todd infinite family G(d,1,n). We highlight consequences for the q-Narayana and q-Kirkman polynomials, giving simple product formulas for both, and give a q-analogue of the identity transforming the h-vector to the f-vector for the coincidental finite type cluster/Cambrian complexes of Fomin--Zelevinsky and Reading.
(Math arXiv preprint arXiv:1908.02663)
Whitney numbers for poset cones (with G. Dorpalen-Barry and Jang Soo Kim)
Hyperplane arrangements dissect Rn into connected components called chambers, and a well-known theorem of Zaslavsky counts chambers as a sum of nonnegative integers called Whitney numbers of the first kind. His theorem generalizes to count chambers within any cone defined as the intersection of a collection of halfspaces from the arrangement, leading to a notion of Whitney numbers for each cone. This paper focuses on cones within the braid arrangement, consisting of the reflecting hyperplanes xi=xj inside Rn for the symmetric group, thought of as the type An-1 reflection group. Here cones correspond to posets, chambers within the cone correspond to linear extensions of the poset, and the Whitney numbers of the cone interestingly refine the number of linear extensions of the poset. We interpret this refinement explicitly for two families of posets: width two posets, and disjoint unions of chains. In the latter case, this gives a geometric re-interpretation to Foata's theory of cycle decomposition for multiset permutations, and leads to a simple generating function compiling these Whitney numbers.
(Math arXiv preprint arXiv:1906.00036)
Cyclic quasi-symmetric functions (with R. Adin, I.M. Gessel, and Y. Roichman)
The ring of cyclic quasi-symmetric functions and its non-Escher subring are introduced in this paper. A natural basis consists of fundamental cyclic quasi-symmetric functions; for the non-Escher subring they arise as toric P-partition enumerators, for toric posets P with a total cyclic order. The associated structure constants are determined by cyclic shuffles of permutations. We then prove the following positivity phenomenon: for every non-hook shape λ, the coefficients in the expansion of the Schur function sλ in terms of fundamental cyclic quasi-symmetric functions are nonnegative. The proof relies on the existence of a cyclic descent map on the standard Young tableaux (SYT) of shape λ. The theory has applications to the enumeration of cyclic shuffles and SYT by cyclic descents. We conclude by providing a cyclic analogue of Solomon's descent algebra.
(Math arXiv preprint arXiv:1811.05440)
Weak order and descents for monotone triangles (with Z. Hamaker)
Monotone triangles are a rich extension of permutations that biject with alternating sign matrices. The notions of weak order and descent sets for permutations are generalized here to monotone triangles, and shown to enjoy many analogous properties. It is shown that any linear extension of the weak order gives rise to a shelling order on a poset, recently introduced by Terwilliger, whose maximal chains biject with monotone triangles; among these shellings are a family of EL-shellings. The weak order turns out to encode an action of the 0-Hecke monoid of type A on the monotone triangles, generalizing the usual bubble-sorting action on permutations. It also leads to a notion of descent set for monotone triangles, having another natural property: the surjective algebra map from the Malvenuto- Reutenauer Hopf algebra of permutations into quasisymmetric functions extends in a natural way to an algebra map out of the recently-defined Cheballah-Giraudo-Maurice algebra of alternating sign matrices.
(Math arXiv preprint arXiv:1809.10571)
On configuration spaces and Whitehouse's lifts of the Eulerian representations (with N. Early)
S. Whitehouse's lifts of the Eulerian representations of the symmetric group Sn to Sn+1 are reinterpreted, topologically and ring-theoretically, with inspiration from A. Ocneanu's theory of permutohedral blades.
(Math arXiv preprint arXiv:1808.04007)
On cyclic descents for tableaux (with R. Adin and Y. Roichman)
The notion of descent set, for permutations as well as for standard Young tableaux (SYT), is classical. Cellini introduced a natural notion of cyclic descent set for permutations, and Rhoades introduced such a notion for SYT --- but only for rectangular shapes. In this work we define cyclic extensions of descent sets in a general context, and prove existence and essential uniqueness for SYT of almost all shapes. The proof applies nonnegativity properties of Postnikov's toric Schur polynomials, providing a new interpretation of certain Gromov-Witten invariants.
(Math arXiv preprint arXiv:1710.06664)
The Koszul homology algebra of the second Veronese is generated by the lowest strand (with Aldo Conca and Lukas Katthän)
We show that the Koszul homology algebra of the second Veronese subalgebra of a polynomial ring over a field of characteristic zero is generated, as an algebra, by the homology classes corresponding to the syzygies of its linear strand.
(Math arXiv preprint arXiv:1710.04293)
A refined count of Coxeter element factorizations (with Elise delMas and Thomas Hameister)
For well-generated complex reflection groups, Chapuy and Stump gave a simple product for a generating function counting reflection factorizations of a Coxeter element by their length. This is refined here to record the number of reflections used from each orbit of hyperplanes. The proof is case-by-case via the classification of well-generated groups. It implies a new expression for the Coxeter number, expressed via data coming from a hyperplane orbit; a case-free proof of this due to J. Michel is included.
(Math arXiv preprint arXiv:1708.06292)
Critical groups for Hopf algebra modules (with Darij Grinberg and Jia Huang)
This paper considers an invariant of modules over a finite-dimensional Hopf algebra, called the critical group. This generalizes the critical groups of complex finite group representations studied by Benkart, Klivans, Reiner and Gaetz. A formula is given for the cardinality of the critical group generally, and the critical group for the regular representation is described completely. A key role in the formulas is played by the greatest common divisor of the dimensions of the indecomposable projective representations.
(Math arXiv preprint arXiv:1704.03778, journal version. )
Invariant derivations and differential forms for reflection groups (with Anne V. Shepler)
Classical invariant theory of a complex reflection group W highlights three beautiful structures: When W is a duality (or well-generated) group, we give an explicit description of the isotypic component within the differential forms of the irreducible reflection representation. This resolves a conjecture of Armstrong, Rhoades and the first author, and relates to Lie-theoretic conjectures and results of Bazlov, Broer, Joseph, Reeder, and Stembridge, and also Deconcini, Papi, and Procesi. We establish this result by examining the space of W-invariant differential derivations; these are derivations whose coefficients are not just polynomials, but differential forms with polynomial coefficients. For every complex reflection group W, we show that the space of invariant differential derivations is finitely generated as a module over the invariant differential forms by the basic derivations together with their exterior derivatives. When W is a duality group, we show that the space of invariant differential derivations is free as a module over the exterior subalgebra of W-invariant forms generated by all but the top-degree exterior generator. (The basic invariant of highest degree is omitted.) Our arguments for duality groups are case-free, i.e., they do not rely on any reflection group classification.
(Math arXiv preprint arXiv:1612.01031)
Weyl group q-Kreweras numbers and cyclic sieving (with Eric Sommers)
The paper concerns a definition for q-Kreweras numbers for finite Weyl groups W, refining the q-Catalan numbers for W, and arising from work of the second author. We give explicit formulas in all types for the q-Kreweras numbers. In the classical types A, B, C, we also record formulas for the q-Narayana numbers and in the process show that the formulas depend only on the Weyl group (that is, they coincide in types B and C). In addition we verify that in the classicial types A,B,C,D that the q-Kreweras numbers obey the expected cyclic sieving phenomena when evaluated at appropriate roots of unity.
(Math arXiv preprint arXiv:1605.09172, journal version).
Poset edge densities, nearly reduced words, and barely set-valued tableaux (with Bridget Eileen Tenner and Alexander Yong)
In certain finite posets, the expected down-degree of their elements is the same whether computed with respect to either the uniform distribution or the distribution weighting an element by the number of maximal chains passing through it. We show that this coincidence of expectations holds for Cartesian products of chains, connected minuscule posets, weak Bruhat orders on finite Coxeter groups, certain lower intervals in Young's lattice, and certain lower intervals in the weak Bruhat order below dominant permutations. Our tools involve formulas for counting nearly reduced factorizations in 0-Hecke algebras; that is, factorizations that are one letter longer than the Coxeter group length.
(Math arXiv preprint arXiv:1603.09589, journal link)
Circuits and Hurwitz action in finite root systems (with Joel Brewster Lewis)
In a finite real reflection group, two factorizations of a Coxeter element into an arbitrary number of reflections are shown to lie in the same orbit under the Hurwitz action if and only if they use the same multiset of reflection conjugacy classes. The proof uses a surprising lemma, derived from a classification of the minimal linear dependences (matroid circuits) in finite root systems: any set of roots forming a minimal linear dependence with positive coefficients always has a disconnected graph of pairwise acuteness.
(Math arXiv preprint arXiv:1603.05969, journal version)
Chip firing on Dynkin diagrams and McKay quivers (with Georgia Benkart and Caroline Klivans)
Two classes of avalanche-finite matrices and their critical groups (integer cokernels) are studied from the viewpoint of chip-firing/sandpile dynamics, namely, the Cartan matrices of finite root systems and the McKay-Cartan matrices for finite subgroups G of general linear groups. In the root system case, the recurrent and superstable configurations are identified explicitly and are related to minuscule dominant weights. In the McKay-Cartan case for finite subgroups of the special linear group, the cokernel is related to the abelianization of the subgroup G. In the special case of the classical McKay correspondence, the critical group and the abelianization are shown to be isomorphic.
(Math arXiv preprint arXiv:1601.06849, journal version)
Absolute order in general linear groups (with Jia Huang and Joel Brewster Lewis)
This paper studies a partial order on the general linear group GL(V) called the absolute order, derived from viewing GL(V) as a group generated by reflections, that is, elements whose fixed space has codimension one. The absolute order on GL(V) is shown to have two equivalent descriptions, one via additivity of length for factorizations into reflections, the other via additivity of fixed space codimensions. Other general properties of the order are derived, including self-duality of its intervals. Working over a finite field Fq, it is shown via a complex character computation that the poset interval from the identity to a Singer cycle (or any regular elliptic element) in GLn(Fq) has a strikingly simple formula for the number of chains passing through a prescribed set of ranks.
(Math arXiv preprint arXiv:1506.03332, journal version)
Representation stability for cohomology of configuration spaces in Rd (with Patricia Hersh)
This paper studies representation stability in the sense of Church and Farb for representations of the symmetric group Sn on the cohomology of the configuration space of n ordered points in Rd. This cohomology is known to vanish outside of dimensions divisible by d-1; it is shown here that the Sn-representation on the i(d-1)st cohomology stabilizes sharply at n=3i (resp. n=3i+1) when d is odd (resp. even). The result comes from analyzing Sn-representations known to control the cohomology: the Whitney homology of set partition lattices for d even, and the higher Lie representations for d odd. A similar analysis shows that the homology of any rank-selected subposet in the partition lattice stabilizes by n ≥ 4i, where i is the maximum rank selected. Further properties of the Whitney homology and more refined stability statements for Sn-isotypic components are also proven, including conjectures of J. Wiltshire-Gordon.
(Math arXiv preprint arXiv:1505.04196, PDF file)
On non-conjugate Coxeter elements in well-generated reflection groups (with Vivien Ripoll and Christian Stump)
ABSTRACT: Given an irreducible well-generated complex reflection group W with Coxeter number h, we show that the class of regular elements of order h form a single orbit in W under the action of reflection automorphisms. For Coxeter and Shephard groups, this implies that an element c is h-regular if and only if there exists a simple system S of reflections such that c is the product of the generators in S. We moreover deduce multiple further implications of this property. In particular, we obtain that all noncrossing partition lattices of W associated to different regular elements of order h are isomorphic. We also prove that there is a simply transitive action of the Galois group of the field of definition of W on the conjugacy classes of h-regular elements. Finally, we extend several of these properties to regular elements of arbitrary order. We show that the action of reflection automorphisms also preserves, and is transitive on, the set of regular elements of a given order d, and we study the action of the Galois group on conjugacy classes of d-regular elements.
(Math arXiv preprint arXiv:1404.5522)
Invariants of GLn(Fq) mod Frobenius powers (with Joel Lewis and Dennis Stanton)
ABSTRACT: Conjectures are given for Hilbert series related to polynomial invariants of finite general linear groups, one for invariants mod Frobenius powers of the irrelevant ideal, one for cofixed spaces of polynomials.
(Math arXiv preprint arXiv:1403.6521, journal version (Proc. Roy. Soc. Edinburgh) )
Pseudodeterminants and perfect square spanning tree counts (with Jeremy Martin, Molly Maxwell, and Scott O. Wilson)
ABSTRACT: The pseudodeterminant pdet(M) of a square matrix is the last nonzero coefficient in its characteristic polynomial; for a nonsingular matrix, this is just the determinant. If A is a symmetric or skew-symmetric matrix then pdet(A At)=pdet(A)2. Whenever A is the kth boundary map of a self-dual CW-complex X, this linear-algebraic identity implies that the torsion-weighted generating function for cellular k-trees in X is a perfect square. In the case that X is an antipodally self-dual CW-sphere of odd dimension 2k-1, the pseudodeterminant of its kthcellular boundary map can be interpreted directly as a torsion-weighted generating function both for k-trees and for (k-1)-trees, complementing the analogous result for even-dimensional spheres given by the second author. The argument relies on the topological fact that any self-dual even-dimensional CW-ball can be oriented so that its middle boundary map is skew-symmetric.
(PDF file)
What is ... cyclic sieving? (with Dennis Stanton and Dennis White)
ABSTRACT: This is a short article for the Notices of the AMS on what we call the cyclic sieving phenomenon.
(PDF file)
Reflection factorizations of Singer cycles (with Joel Lewis and Dennis Stanton)
ABSTRACT: The number of shortest factorizations into reflections for a Singer cycle in GL(n,F_q) is shown to be (q^n −1)^(n−1). Formulas counting factorizations of any length, and counting those with reflections of fixed conjugacy classes are also given.
(Math arXiv preprint arXiv:1308.1468, PDF file)
Critical groups of covering, voltage and signed graphs (with Dennis Tseng)
ABSTRACT: Graph coverings are known to induce surjections of their critical groups. Here we describe the kernels of these morphisms in terms of data parametrizing the covering. Regular coverings are parametrized by voltage graphs, and the above kernel can be identified with a naturally defined voltage graph critical group. For double covers, the voltage graph is a signed graph, and the theory takes a particularly pleasant form, leading also to a theory of double covers of signed graphs.
(Math arXiv preprint arXiv:1301.2977)
Toric partial orders (with Mike Develin and Matthew Macauley)
ABSTRACT: We define toric partial orders, corresponding to regions of graphic toric hyperplane arrangements, just as ordinary partial orders correspond to regions of graphic hyperplane arrangements. Combinatorially, toric posets correspond to finite posets under the equivalence relation generated by converting minimal elements into maximal elements, or sources into sinks. We derive toric analogues for several features of ordinary partial orders, such as chains, antichains, transitivity, Hasse diagrams, linear extensions, and total orders.
(Math arXiv preprint arXiv:1211.4247, journal offprint)
A universal coefficient theorem for Gauss's Lemma (with William Messing)
ABSTRACT: We prove a version of Gauss’s Lemma that recursively constructs polynomials {ck} for k=0,...,m+n in Z[ai,Ai,bj,Bj] for i=0,1,...,m,j=0,1,...,n, of degree at most m+n, such that whenever Σk Ck Xk = (Σ i Ai Xi) (Σj Bj Xj) and 1=Σi ai Ai =Σj bj Bj, one has 1=Σk ck Ci.
(Math arXiv preprint arXiv:1209.6307)
Parking spaces (with Drew Armstrong and Brendon Rhoades)
ABSTRACT: Let W be a Weyl group with root lattice Q and Coxeter number h. The elements of the finite torus Q=(h+1)Q are called the W-parking functions, and we call the permutation representation of W on the set of W-parking functions the (standard) W-parking space. Parking spaces have interesting connections to enumerative combinatorics, diagonal harmonics, and rational Cherednik algebras. In this paper we define two new W-parking spaces, called the noncrossing parking space and the algebraic parking space, with the following features: Our Main Conjecture is that the two new parking spaces are isomorphic to each other as permutation representations of W x C. This conjecture ties together several threads in the Catalan combinatorics of finite reflection groups. We provide evidence for the conjecture, proofs of some special cases, and suggest further directions for the theory.
(Math ArXiv preprint arXiv:1204.1760)
A survey of the higher Stasheff-Tamari orders (with Joerg Rambau)
ABSTRACT:The Tamari lattice, thought as a poset on the set of triangulations of a convex polygon with n vertices, generalizes to the higher Stasheff-Tamari orders on the set of triangulations of a cyclic d-dimensional polytope having n vertices. This survey discusses what is known about these orders, and what one would like to know about them.
(PDF file of the survey appearing in Progress in Mathematics, Vol. 299, Birkhauser 2012)
Fake degrees for reflection actions on roots (with Zhiwei Yun)
ABSTRACT: A finite irreducible real reflection group of rank l and Coxeter number h has root system of cardinality h*l. It is shown that the fake degree for the permutation action on its roots is divisible by [h]q = 1+q+q2+...+qh-1, and that in simply-laced types, it equals [h]q times the summation of qei-1 where ei runs through the exponents, so that ei-1 are the codegrees.
(Math ArXiv preprint arXiv:1201.0032)
The negative q-binomial (with S. Fu, D. Stanton, and N. Thiem)
ABSTRACT: Interpretations for the q-binomial coefficient evaluated at -q are discussed. A (q,t)-version is established, including an instance of a cyclic sieving phenomenon involving unitary spaces.
(Math ArXiv preprint arxiv:1108.4702)
A multivariate "inv" hook formula for forests (with F. Hivert)
ABSTRACT: Björner and Wachs provided two q-generalizations of Knuth’s hook formula counting linear extensions of forests: one involving the major index statistic, and one involving the inversion number statistic. We prove a multivariate generalization of their inversion number result, motivated by specializations related to the modular invariant theory of finite general linear groups.
(Math ArXiv preprint arXiv:1107.3508)
P-partitions revisited (with V. Féray)
ABSTRACT: We compare a traditional and non-traditional view on the subject of P-partitions, leading to formulas counting linear extensions of certain posets.
(Math ArXiv preprint arXiv:1106.6235)
Spectra of symmetrized shuffling operators (with F. Saliola and V. Welker)
ABSTRACT: For a finite real reflection group W and a a conjugacy class of its parabolic subgroups, we introduce a statistic on elements of W. We study the operator of right-multiplication within the group algebra of W by the element whose coefficients are given by this statistic. We interpret this geometrically in terms of the reflection arrangement for W, and show that these operators are self-adjoint and positive semidefinite, via two explicit factorizations into a symmetrized form A^t A. In one of these factorizations, A comes from the the Bidigare-Hanlon-Rockmore random walks on the chambers of an arrangement.
(Math ArXiv preprint arXiv:1102.2460, PDF file)
The cyclotomic polynomial topologically (with G. Musiker)
ABSTRACT: We interpret the coefficients of the cyclotomic polynomial in terms of simplicial homology.
(Math ArXiv preprint arXiv:1012.1844)
Linear extension sums as valuations of cones (with A. Boussicault, V. Feray and A. Lascoux)
ABSTRACT: The geometric and algebraic theory of valuations on cones is applied to understand identities involving summing certain rational functions over the set of linear extensions of a poset.
(Math ArXiv preprint arXiv:1008.3278)
Constructions for cyclic sieving phenomena (with A. Berget and S.-P. Eu)
ABSTRACT: We show how to derive new instances of the cyclic sieving phenomenon from old ones via elementary representation theory. Examples are given involving objects such as words, parking functions, finite fields, and graphs.
(Math ArXiv preprint arXiv:1004.0747)
Diameter of reduced words (with Y. Roichman)
ABSTRACT: For finite reflection groups of types A and B, we determine the diameter of the graph whose vertices are reduced words for the longest element and whose edges are braid relations. This is deduced from a more general theorem that applies to supersolvable hyperplane arrangements.
(Math ArXiv preprint arXiv:0906.4768)
Koszul incidence algebras, affine semigroups, and Stanley-Reisner ideals (with D. Stamate)
ABSTRACT: We prove a theorem unifying three results from combinatorial homological and commutative algebra, characterizing the Koszul property for incidence algebras of posets and affine semigroup rings, and characterizing linear resolutions of squarefree monomial ideals. The characterization in the graded setting is via the Cohen-Macaulay property of certain posets or simplicial complexes, and in the more general nongraded setting, via the sequential Cohen-Macaulay property.
(Math ArXiv preprint arXiv:0904.1683)
The critical group of a line graph (with Andrew Berget, Andrew Manion, Molly Maxwell, Aaron Potechin)
ABSTRACT: The critical group of a graph is a finite abelian group whose order is the number of spanning forests of the graph. This paper provides three basic structural results on the critical group of a line graph. The first deals with connected graphs containing no cut-edge. Here the number of independent cycles in the graph, which is known to bound the number of generators for the critical group of the graph, is shown also to bound the number of generators for the critical group of its line graph. The second gives, for each prime p, a constraint on the p-primary structure of the critical group, based on the largest power of p dividing all sums of degrees of two adjacent vertices. The third deals with connected graphs whose line graph is regular. Here known results relating the number of spanning trees of the graph and of its line graph are sharpened to exact sequences which relate their critical groups. The first two results interact extremely well with the third. For example, they imply that in a regular nonbipartite graph, the critical group of the graph and that of its line graph determine each other uniquely in a simple fashion.
(Math ArXiv preprint arXiv:0904.1246)
Differential posets and Smith normal forms (with A. Miller)
ABSTRACT: We conjecture a strong property for the up and down maps U and D in an r-differential poset: DU+tI and UD+tI have Smith normal forms over Z[t]. In particular, this would determine the integral structure of the maps U, D, UD, DU, including their ranks in any characteristic. As evidence, we prove the conjecture for the Young-Fibonacci lattice YF studied by Okada and its r-differential generalizations Z(r), as well as verifying many of its consequences for Young's lattice Y and the r-differential Cartesian products Y^r.
(Math ArXiv preprint arXiv:0811.1983)
Presenting the cohomology of a Schubert variety (with A. Woo and A. Yong)
ABSTRACT: We extend the short presentation due to [Borel '53] of the cohomology ring of a generalized flag manifold to a relatively short presentation of the cohomology of any of its Schubert varieties. Our result is stated in a root-system uniform manner by introducing the essential set of a Coxeter group element, generalizing and giving a new characterization of [Fulton '92]'s definition for permutations. Further refinements are obtained in type A.
(Math ArXiv preprint arXiv:0809.2981)
Extending the Coinvariant Theorems of Chevalley, Shephard--Todd, Mitchell and Springer (with A.Broer, L. Smith and P. Webb)
ABSTRACT: We extend in several directions invariant theory results of Chevalley, Shephard and Todd, Mitchell and Springer. Their results compare the group algebra for a finite reflection group with its coinvariant algebra, and compare a group representation with its module of relative coinvariants. Our extensions apply to arbitrary finite groups in any characteristic.
(Math ArXiv preprint arXiv:0805.3694)
(q,t)-analogues and GLn(Fq) (with D. Stanton)
ABSTRACT: We start with a (q,t)-generalization of a binomial coefficient. It can be viewed as a polynomial in t that depends upon an integer q, with combinatorial interpretations when q is a positive integer, and algebraic interpretations when q is the order of a finite field. These (q,t)-binomial coefficients and their interpretations generalize further in two directions, one relating to column-strict tableaux and Macdonald's ``7th variation'' of Schur functions, the other relating to permutation statistics and Hilbert series from the invariant theory of GLn(Fq)
(Math ArXiv preprint arXiv:0804.3074)
Betti numbers of monomial ideals and shifted skew shapes (with U. Nagel)
ABSTRACT: We present two new problems on lower bounds for resolution Betti numbers of monomial ideals generated in a fixed degree. The first concerns any such ideal and bounds the total Betti numbers, while the second concerns ideals that are quadratic and bihomogeneous with respect to two variable sets, but gives a more finely graded lower bound. These problems are solved for certain classes of ideals that generalize (in two different directions) the edge ideals of threshold graphs and Ferrers graphs. In the process, we produce particularly simple cellular linear resolutions for strongly stable and squarefree strongly stable ideals generated in a fixed degree, and combinatorial interpretations for the Betti numbers of other classes of ideals, all of which are independent of the coefficient field.
(Math ArXiv preprint arXiv:0712.2537)
Bimahonian distributions (with H. Barcelo and D. Stanton)
ABSTRACT: Motivated by permutation statistics, we define for any complex reflection group W a family of bivariate generating functions. They are defined either in terms of Hilbert series for W-invariant polynomials when W acts diagonally on two sets of variables, or equivalently, as sums involving the fake degrees of irreducible representations for W. It is also shown that they satisfy a ``bicyclic sieving phenomenon'', which combinatorially interprets their values when the two variables are set equal to certain roots of unity.
(Math ArXiv preprint math.CO/0703479)
Alternating subgroups of Coxeter groups (with F. Brenti and Y. Roichman)
ABSTRACT: We study combinatorial properties of the alternating subgroup of a Coxeter group, using a presentation of it due to Bourbaki.
(Math ArXiv preprint math.CO/0702177)
Cyclic sieving of noncrossing partitions for complex reflection groups (with D. Bessis)
ABSTRACT: We prove an instance of the cyclic sieving phenomenon, occurring in the context of noncrossing parititions for well-generated complex reflection groups.
(Math ArXiv preprint math.CO/0701792)
Shifted set families, degree sequences, and plethysm (with C. Klivans)
ABSTRACT: We study, in three parts, degree sequences of k-families (or k-uniform hypergraphs) and shifted k-families. The first part collects for the first time in one place, various implications such as: Threshold implies Uniquely Realizable implies Degree-Maximal implies Shifted, which are equivalent concepts for 2-families (=simple graphs), but strict implications for k-families with k > 2. The implication that uniquely realizable implies degree-maximal seems to be new. The second part recalls Merris and Roby's reformulation of the characterization due to Ruch and Gutman for graphical degree sequences and shifted 2-families. It then introduces two generalizations which are characterizations of shifted k-families. The third part recalls the connection between degree sequences of k-families of size m and the plethysm of elementary symmetric functions e_m[e_k]. It then uses highest weight theory to explain how shifted k-families provide the ``top part'' of these plethysm expansions, along with offering a conjecture about a further relation.
(Math ArXiv preprint math.CO/0610787)
Faces of Generalized Permutohedra (with A. Postnikov and L. Williams)
ABSTRACT: The aim of the paper is to calculate face numbers of simple generalized permutohedra, and study their f-, h- and gamma-vectors. These polytopes include permutohedra, associahedra, graph-associahedra, graphical zonotopes, nestohedra, and other interesting polytopes. We give several explicit formulas involving descent statistics and calculate generating functions. Additionally, we discuss the relationship with Simon Newcomb's problem and express h-vectors for path-like graph-associahedra in terms of the Narayana numbers. We give a combinatorial interpretation for gamma-vectors of tree-associahedra, confirming Gal's conjectural nonnegativity of gamma-vectors in this case. Included is an Appendix on deformations of simple polytopes.
(Math ArXiv preprint math.CO/0609184)
A quasisymmetric function for matroids (with L.J. Billera and N. Jia)
ABSTRACT: A new isomorphism invariant of matroids is introduced, in the form of a quasisym metric function. This invariant This last property leads to an interesting application: it can sometimes be used to prove that a matroid base polytope has no decompositions into smaller matroid base polytopes. Existence of such decompositions is a subtle issue arising in work of Lafforgue, where lack of such a decomposition implies the matroid has only a finite number of realizations up to scalings of vectors and overall change-of-basis.
(Math ArXiv preprint math.CO/0606646)
Acyclic sets of linear orders via the Bruhat orders (with A. Galambos)
ABSTRACT: We describe Abello's acyclic sets of linear orders as the permutations visited by commuting equivalence classes of maximal reduced decompositions. This allows us to strengthen Abello's structural result: we show that acyclic sets arising from this construction are distributive sublattices of the weak Bruhat order. This, in turn, shows that Abello's acyclic sets are, in fact, the same as Chameni-Nembua's "distributive covering sublattices". Fishburn's "alternating scheme" is shown to be a special case of the Abello/Chameni-Nembua acyclic sets. Any acyclic set that arises in this way can be represented by an arrangement of pseudolines, and we use this representation to derive a simple closed form for the cardinality of the alternating scheme. The higher Bruhat orders prove to be a natural mathematical framework for this approach to the acyclic sets problem.
(PostScript file, gzipped PostScript file, PDF file)
Coincidences among skew Schur functions (with K. Shaw and S. van Willigenburg)
ABSTRACT: New sufficient conditions and necessary conditions are developed for two skew diagrams to give rise to the same skew Schur function. The sufficient conditions come from a variety of new operations related to ribbons (also known as border strips or rim hooks). The necessary conditions relate to the extent of overlap among the rows or among the columns of the skew diagram.
(Math ArXiv preprint math.CO/0602634)
Bergman complexes, Coxeter arrangements, and graph associahedra (with F. Ardila and L. Williams)
ABSTRACT: Tropical varieties play an important role in algebraic geometry. The Bergman complex B(M) and the positive Bergman complex B+(M) of an oriented matroid M generalize to matroids the notions of the tropical variety and positive tropical variety associated to a linear ideal. Our main result is that if A is a Coxeter arrangement of type Phi with corresponding oriented matroid M_Phi, then B+(M_Phi) is dual to the graph associahedron of type Phi, and B(M_Phi) equals the nested set complex of A. In addition, we prove that for any orientable matroid M, one can find |mu(M)| different reorientations of M such that the corresponding positive Bergman complexes cover B(M), where mu(M) denotes the Mobius function of the lattice of flats of M.
(Math ArXiv preprint math.CO/0508240, Seminaire Lotharingien de Combinatoire, Vol. B54Aj (2006), 25 pp )
Rigidity theory for matroids (with M. Develin and J. Martin)
ABSTRACT: Combinatorial rigidity theory seeks to describe the rigidity or flexibility of bar-joint frameworks in R^d in terms of the structure of the underlying graph G. The goal of this article is to broaden the foundations of combinatorial rigidity theory by replacing G with an arbitrary representable matroid M. The ideas of rigidity independence and parallel independence, as well as Laman's and Recski's combinatorial characterizations of 2-dimensional rigidity for graphs, can naturally be extended to this wider setting. As we explain, many of these fundamental concepts really depend only on the matroid associated with G (or its Tutte polynomial), and have little to do with the special nature of graphic matroids or the real field. Our main result is a ``nesting theorem'' relating the various kinds of independence. Immediate corollaries include generalizations of Laman's Theorem, as well as the equality of 2-rigidity and 2-parallel independence. A key tool in our study is the space of photos of M, a natural algebraic variety whose irreducibility is closely related to the notions of rigidity independence and parallel independence. The number of points on this variety, when working over a finite field, turns out be an interesting Tutte polynomial evaluation.
(PostScript file, gzipped PostScript file, PDF file DVI file)
Springer's regular elements over arbitrary fields (with D. Stanton and P. Webb)
ABSTRACT: Springer's theory of regular elements in complex reflection groups is generalized to arbitrary fields. Consequences for the cyclic sieving phenomenon in combinatorics are discussed.
(PostScript file, gzipped PostScript file, PDF file DVI file)
Stanley's simplicial poset conjecture, after M. Masuda (with E. Miller)
ABSTRACT: M. Masuda recently provided the missing piece proving a conjecture of R.P. Stanley on the characterization of f-vectors for Gorenstein* simplicial posets. We propose a slight simplification of Masuda's proof.
(PDF file from journal, or PS file, DVI file, PDF file of preprint)
Finer rook equivalence for Ferrers boards: classification of Ding's partition Schubert varieties (with M. Develin and J. Martin)
ABSTRACT: K. Ding studied a class of Schubert varieties in type A partial flag manifolds, indexed by integer partitions and in bijection with dominant permutations. He observed that the Schubert cell structure of such a variety is indexed by maximal rook placements on the Ferrers board, and that the integral cohomology groups of two such varieties are additively isomorphic exactly when the Ferrers boards satisfy the combinatorial condition of rook-equivalence. We classify these varieties up to isomorphism, distinguishing them by their graded cohomology rings with integer coefficients. The crux of our approach is studying the nilpotence orders of linear forms in the cohomology ring.
(PostScript file, gzipped PostScript file, DVI file, PDF file)
Reciprocal domains and Cohen-Macaulay d-complexes in Rd (with E. Miller)
ABSTRACT: We extend a reciprocity theorem of Stanley about enumeration of integer points in polyhedral cones when one exchanges strict and weak inequalities. The proof highlights the roles played by Cohen-Macaulayness and canonical modules. The extension raises the issue of whether a Cohen--Macaulay complex of dimension d embedded piecewise-linearly in d-space is necessarily a d-ball. This is observed to be true for d at most 3, but false for d=4.
(PostScript file, gzipped PostScript file, DVI file, PDF file)
Cyclotomic and simplicial matroids (with J. Martin)
ABSTRACT: Two naturally occurring matroids representable over Q are shown to be dual: the cyclotomic matroid represented by the n-th roots of unity inside a cyclotomic extension, and a direct sum of copies of a certain simplicial matroid, considered originally by Bolker in the context of transportation polytopes. A result of Adin leads to an upper bound for the number of Q-bases for the cyclotomic extension among the n-th roots of unity, which is tight if and only if n has at most two odd prime factors. In addition, we study the Tutte polynomial in the case that n has two prime factors.
(PostScript file, gzipped PostScript file, PDF file)
The cyclic sieving phenomenon (with D. Stanton and D. White)
ABSTRACT: The cyclic sieving phenomenon is defined for generating functions of a set affording a cyclic group action, generalizing Stembridge's q=-1 phenomenon. The phenomenon is shown to appear in various situations, involving q-binomial coefficients, Polya theory, polygon dissections, non-crossing partitions, finite reflection groups, and some finite field q-analogues.
(PostScript file, gzipped PostScript file, PDF file DVI file)
Noncrossing partitions for the group Dn (with C. A. Athanasiadis)
ABSTRACT: The poset of noncrossing partitions can be naturally defined for any finite Coxeter group W. It is a self-dual, graded lattice which reduces to the classical lattice of noncrossing partitions of {1, 2, ... ,n} defined by Kreweras (1970) when W is the symmetric group S_n, and to its type B analogue defined by the second author (1997) when W is the hyperoctahedral group. We give a combinatorial description of this lattice in terms of noncrossing planar graphs in the case of the Coxeter group of type D_n, thus answering a question of Bessis. Using this description, we compute a number of fundamental enumerative invariants of this lattice, such as the rank sizes, number of maximal chains and Moebius function. We also extend to the type D case the statement that noncrossing partitions are equidistributed to nonnesting partitions by block sizes, previously known for types A, B and C. This leads to a (case-by-case) proof of a theorem valid for all root systems: the noncrossing and nonnesting subspaces within the intersection lattice of the Coxeter hyperplane arrangement have the same distribution according to W-orbits.
(PostScript file, gzipped PostScript file, PDF file DVI file)
Note on the expected number of Yang-Baxter moves applicable to reduced decompositions
ABSTRACT: It is observed that the expected number of Yang-Baxter moves applicable to reduced decompositions of the longest element in the symmetric group is always 1.
(PostScript file, gzipped PostScript file, PDF file DVI file)
Factorizations of some weighted spanning tree enumerators (with J. Martin)
ABSTRACT: For two classes of graphs, threshold graphs and Cartesian products of complete graphs, full or partial factorizations are given for spanning tree enumerators that keep track of fine weights related to degree sequences and edge directions.
(PostScript file, gzipped PostScript file, PDF file DVI file)
On the Charney-Davis and Neggers-Stanley Conjectures (with V. Welker)
ABSTRACT: For a graded naturally labelled poset P, it is shown that the the P-Eulerian polynomial which counts linear extensions of P by their number of descents has (symmetric and) unimodal coefficients. This is deduced from McMullen's g-Theorem, by exhibiting a simplicial polytopal sphere whose h-polynomial coincides with this P-Eulerian polynomial. This simplicial sphere turns out to be flag, that is, its minimal non-faces all have cardinality two. As a consequence, the Neggers-Stanley Conjecture on real zeroes for the P-Eulerian polynomial is shown to imply the Charney-Davis Conjecture for this flag simplicial sphere. It is speculated that the proper context in which to view both of these conjectures may be the theory of Koszul algebras, and evidence for this is presented.
(PostScript file, gzipped PostScript file, PDF file DVI file)
The Charney-Davis quantity for certain graded posets (with D. Stanton and V. Welker)
ABSTRACT: Given a naturally labelled graded poset P with r ranks, the sum over its linear extensions of (-1) to the number of descents is an instance of a quantity occurring in the Charney-Davis Conjecture on flag simplicial spheres. When |P|-r is odd this quantity vanishes. When |P|-r is even and P satisfies the Neggers-Stanley Conjecture, it has sign (-1)^{(|P|-r)/2}. We interpret this quantity combinatorially for several classes of graded posets P, including certain disjoint unions of chains and products of chains. These interpretations involve alternating multiset permutations, Baxter permutations, Catalan numbers, and Franel numbers.
(LaTeX file, PostScript file, gzipped PostScript file, PDF file, DVI file)
Geochemical phase diagrams and Gale diagrams (with P.H. Edelman, S.W. Peterson, and J.H. Stout)
ABSTRACT: The problem of predicting the possible topologies of a geochemical phase diagram, based on the chemical formula of the phases involved, is shown to be intimately connected with and aided by well-studied notions in discrete geometry: Gale diagrams, triangulations, secondary fans, and oriented matroids.
(PostScript file, gzipped PostScript file, PDF file)
Coxeter-like complexes (with E. Babson)
ABSTRACT: Motivated by the Coxeter complex associated to a Coxeter system (W,S), we introduce a simplicial regular cell complex with a G-action associated to any pair (G,S) where G is a group and S is a finite set of generators for G which is minimal with respect to inclusion. We examine the topology of this complex (G,S), and in particular the representations of G on its homology groups. We look closely at the case of the symmetric group on n letters along with a choice of a minimal set of generating transpositions. This corresponds to a choice of a spanning tree on vertex set {1,2,...,n}. This naturally leads to the study of a slightly larger class of simplicial complexes, including not only the Coxeter complexes of type A and all of their type-selected subcomplexes, but also the well-studied chessboard complexes.
( Journal page in DMTCS, PostScript file, gzipped PostScript file, PDF file DVI file)
Equivariant fiber polytopes
ABSTRACT: The equivariant generalization of Billera and Sturmfels' fiber polytope construction is described. This gives a new relation between the associahedron and cyclohedron, a different natural construction for the type B permutohedron, and leads to a family of order-preserving maps between the face lattice of the type B permutohedron and that of the cyclohedron.
(Journal page in Doc. Math., PostScript file, gzipped PostScript file, PDF file DVI file)
The combinatorics of the bar resolution in group cohomology (with P. Webb)
ABSTRACT: We study a combinatorially-defined double complex structure on the ordered chains of any simplicial complex. Its columns turn out to be related to the cell complex Kn whose face poset is isomorphic to the subword ordering on words without repetition from an alphabet of size n. This complex is known to be shellable and we provide two applications of this fact. First, the action of the symmetric group on the homology of Kn gives a representation theoretic interpretation for derangement numbers and a related symmetric function considered by Desarmenien and Wachs. Second, the vanishing of homology below the top dimension for Kn and the links of its faces provides a crucial step in understanding one of the two spectral sequences associated to the double complex. We analyze also the other spectral sequence arising from the double complex in the case of the bar resolution for a group. This spectral sequence converges to the cohomology of the group and provides a method for computing group cohomology in terms of the cohomology of subgroups. Its behavior is influenced by the complex of oriented chains of the simplicial complex of finite subsets of the group, and we examine the Ext class of this complex.
(PostScript file, gzipped PostScript file, PDF file DVI file)
Local cohomology modules of Stanley-Reisner rings with supports in general monomial ideals (with V. Welker and K. Yanagawa)
ABSTRACT: We study the local cohomology modules of a Stanley-Reisner ring associated to a simplicial complex with support in the ideal corresponding to a subcomplex. We give a combinatorial topological formula for the multigraded Hilbert series, and in the case where the ambient complex is Gorenstein, compare this with a second combinatorial formula that generalizes results of Mustata and Terai. The agreement between these two formulae is seen to be a disguised form of Alexander duality. Other results include a comparison of the local cohomology with certain Ext modules, results about when it it is concentrated in a single homological degree, and combinatorial topological interpretations of some vanishing theorems.
(PostScript file, DVI file, LaTeX file)
The sign representation for Shephard groups (with A.V. Shepler and P. Orlik)
ABSTRACT: Shephard groups are unitary reflection groups arising as the symmetries of regular complex polytopes. For a Shephard group, we identify the representation carried by the principal ideal in the coinvariant algebra generated by the image of the product of all linear forms defining reflecting hyperplanes. This representation turns out to have many equivalent guises making it analogous to the sign representation of a finite Coxeter group. One of these guises is (up to a twist) the homology of the Milnor fiber for the isolated singularity at $0$ in the hypersurface defined by any homogeneous invariant of minimal degree.
(PostScript file, DVI file, LaTeX file)
Convex, acyclic, and free sets of an oriented matroid (with P.H. Edelman and V. Welker)
ABSTRACT: We study the global and local topology of three objects associated to an oriented matroid: the lattice of convex sets, the simplicial complex of acyclic sets, and the simplicial complex of free sets. Special cases of these objects and their homotopy types have appeared in several places in the literature. The global homotopy types of all three are shown to coincide, and are either spherical or contractible depending on whether the oriented matroid is totally cyclic. Analysis of the homotopy type of links of vertices in the complex of free sets yields a generalization and more conceptual proof of a recent result counting the interior points of a point configuration.
(PostScript file, DVI file, LaTeX file, two necessary encapsulated PostScript figures: Figure 1, Figure 2 )
Cohomology of smooth Schubert varieties in partial flag manifolds (with V. Gasharov)
ABSTRACT: We use the fact that smooth Schubert varieties in partial flag manifolds are iterated fiber bundles over Grassmannians to give a simple presentation for their integral cohomology ring, generalizing Borel's presentation for the cohomology of the partial flag manifold itself. More generally, such a presentation is shown to hold for a larger class of subvarieties of the partial flag manifolds (which we call subvarieties defined by inclusions). The Schubert varieties which lie within this larger class are characterized combinatorially by a pattern avoidance condition.
(LaTeX file, DVI file PostScript file)
Note on a theorem of Eng
ABSTRACT: We reprove a recent theorem of O. Eng that gives an instance of Stembridge's "q=-1 phenomenon" occurring in finite Coxeter groups. Eng's proof relied on the classification of irreducible finite Coxeter groups, whereas our proof is uniform for Weyl groups. We apply a fact from Hodge theory to the cohomology of the homogeneous spaces G/P, where G is a semisimple algebraic group and P a parabolic subgroup.
(LaTeX file, DVI file PostScript file)
Shifted simplicial complexes are Laplacian integral (with A. Duval)
ABSTRACT: We show that the combinatorial Laplace operators associated to the boundary maps in a shifted simplicial complex have all integer spectra. We give a simple combinatorial interpretation for the spectra in terms of vertex degree sequences, generalizing a theorem of Merris for graphs. We also conjecture a majorization inequality for the spectra of these Laplace operators in an arbitrary simplicial complex, with equality achieved if and only if the complex is shifted. This generalizes a conjecture of Grone and Merris for graphs.
(LaTeX file, DVI file PostScript file)
The signature of a toric variety (with N.C. Leung)
ABSTRACT: We identify a combinatorial quantity (the alternating sum of the h-vector) defined for any simple polytope as the signature of a toric variety. This quantity was introduced by Charney and Davis in their work, which in particular showed that its non-negativity is closely related to a conjecture of Hopf on the Euler characteristic of a non-positively curved manifold. We prove positive (or non-negative) lower bounds for this quantity under geometric hypotheses on the polytope. These hypotheses lead to ampleness (or weaker conditions) for certain line bundles on toric divisors, and then the lower bounds follow from calculations using the Hirzebruch Signature Formula. Moreoever, we show that under these hypotheses on the polytope, the i-th L-class of the corresponding toric variety is (-1)^i times an effective class for any i.
(LaTeX file, DVI file PostScript file)
Counting the interior points of a point configuration (with P. H. Edelman)
ABSTRACT: We prove a formula conjectured by Ahrens, Gordon, and McMahon for the number of interior points for a point configuration in affine space. Our method is to show that the formula can be interpreted as a sum of Euler characteristics of certain complexes associated with the point configuration, and then compute the homology of these complexes. This method extends to other examples of convex geometries. We sketch these applications, replicating an earlier result of Gordon, and proving a new result related to ordered sets.
(LaTeX file, DVI file, PostScript file)
On the linear syzygies of a Stanley-Reisner ideal
(with Volkmar Welker) ABSTRACT: We give an elementary description of the maps in the linear strand of the minimal free resolution of a square-free monomial ideal, that is, the Stanley-Reisner ideal associated to a simplicial complex K. The description is in terms of the homology of the canonical Alexander dual complex K*.
(LaTeX file, DVI file, PostScript file)
A homological lower bound for order dimension of lattices (with Volkmar Welker).
ABSTRACT: We prove that the proper part of a finite lattice of order dimension d has vanishing homology in dimensions d-1 and higher with any coefficients.
(PostScript file, DVI file, Plain-TeX file )
The distribution of descents and length in a Coxeter group
ABSTRACT: We give a method for computing the "q-Eulerian distribution" W(t,q) for a Coxeter system (W,S) as a rational function in t and q, where W(t,q) counts the elements of W by their length and their number of descents (= number of elements of S which shorten them). Using this we compute generating functions encompassing these W(t,q) of the classical infinite families of finite and affine Weyl groups.
(Elec. J. Combinatorics Volume 2(1), 1995, article R25.)

Some even older ones...

  • Signed permutation statistics
  • Signed permutation statistics and cycle type
  • Signed permutation statistics and upper binomial posets
  • Signed posets
  • My PhD thesis (scanned, with help from D. Grinberg. Lost the TeX file, sorry!)

    • Papers with undergraduate (summer REU) students

    The critical group of a threshold graph (with H. Christianson, Summer 2001 REU)
    ABSTRACT: The critical group of a connected graph is a finite abelian group, whose order is the number of spanning trees in the graph. The structure of this group is a subtle isomorphism invariant that has received much attention recently, partly due to its relation to the graph Laplacian and chip-firing games. However, the group structure has been determined for relatively few classes of graphs. We conjecture a relation between the group structure and the Laplacian spectrum for a large class of graphs having integer spectra (the decomposable graphs of Kelmans). Based on computer evidence, we conjecture the exact group structure for the well-studied subclass of threshold graphs, and prove this conjecture for the subclass which we call generic threshold graphs.
    (PostScript file, gzipped PostScript file, DVI file)
    Note on the Pfaffian Matrix-Tree Theorem (with S. Hirschman, Summer 2002 REU)
    ABSTRACT: The Pfaffian Matrix-Tree Theorem of Masbaum and Vaintrob gives a generating function for 3-trees in a 3-uniform hypergraph, analogous to Kirchoff's Matrix-Tree Theorem counting trees in graphs. They prove their result via the analogue of deletion-contraction induction. This paper gives a proof via a sign-reversing involution, analogous to the proof of Kirchoff's Theorem due to Chaiken.
    (PostScript file, gzipped PostScript file, PDF file)
    Critical groups for complete multipartite graphs and Cartesian products of complete graphs
     (with B. Jacobson and A. Niedermaier, Summer 2002 REU)
    ABSTRACT: The critical group of a connected graph is a finite abelian group, whose order is the number of spanning trees in the graph, and which is closely related to the graph Laplacian. Its group structure has been determined for relatively few classes of graphs, e.g. complete graphs, and complete bipartite graphs. For complete multipartite graphs, we describe the critical group structure completely. For Cartesian products of complete graphs, we generalize results of H. Bai on the k-dimensional cube, by bounding the number of invariant factors in the critical group, and describing completely its p-primary structure for all primes p that divide none of the sizes of the complete graph factors.
    (PostScript file, gzipped PostScript file, PDF file)
    Note on 1-crossing partitions
    (with M. Bergerson, A. Miller, A. Pliml, P. Shearer, D. Stanton, and N. Switala, from Summer 2006 REU)
    ABSTRACT: It is shown that there are (2n-r-1 choose n-r) noncrossing partitions of an n-set together with a distinguished block of size r, and (n choose k-1)(n-r-1 choose k-2) of these have k blocks, generalizing a result of Bona on partitions with one crossing. Furthermore, when one evaluates natural q-analogues of these formulae for q an n-th root of unity of order d, one obtains the number of such objects having d-fold rotational symmetry.
    (PDF file)

    Unpublished manuscripts and notes for the fun of it

    Characters and inversions in the symmetric group. (with A. de Medicis and M. Shimozono)
    ABSTRACT: We consider sums over permutations in the symmetric group of the value of a skew character times q^inversions. Our main result gives a lower bound on the number of factors of 1+q and 1-q which divide the sum, and is shown to be sharp when the skew shape is a hook shape.
    (This appeared as an extended abstract in the proceedings of the 6th Formal Power Series and Algebraic Combinatorics conference, at DIMACS in May 1994.)
    (PostScript file, Gzipped PostScript file, PDF file, DVI file)
    On some instances of the generalized Baues problem.
    ABSTRACT: We present an approach applicable to certain instances of the generalized Baues problem of Billera, Kapranov, and Sturmfels. This approach involves two applications of Alexander/Spanier-Whitehead duality. We use this to show that the generalized Baues problem has a positive answer for the surjective map of cyclic polytopes C(n,d) --> C(n,2) if n < 2d and d is at least 10.
    (These results were later superseded by results of Athanasiadis, Rambau, and Santos which verified the Baues problem positively for all of the maps C(n,d) --> C(n,d') between cyclic polytopes.)
    (LaTeX file, DVI file, PostScript file)
    Bernstein's Theorem over fields with discrete valuation (with S. Sperber; appendix by W. Messing)
    ABSTRACT: For fields complete with respect to a discrete valuation, we prove a refinement of Bernstein's theorem counting the generic number of solutions to a system of n polynomial equations in n unknowns. The refinement predicts the number of solutions whose coordinates have given valuations, generalizing to several variables the classical use of Newton polygons for determining the valuations of the roots of a polynomial in one variable.
    ( We later discovered that this result was independently found by Smirnov. )
    (PostScript file, gzipped PostScript file, PDF file DVI file)
    Conjectures on the cohomology of the Grassmannian (with G. Tudose)
    ABSTRACT: We give a series of successively weaker conjectures on the cohomology ring of the Grassmannian, starting with the Hilbert series of a certain natural filtration
    ArXiv link
    Springer's theorem for modular coinvariants of GLn(Fq) (with D. Stanton and P. Webb)
    ABSTRACT: Two related results are proven in the modular invariant theory of GLn(Fq). The first is a finite field analogue of a result of Springer on coinvariants of the symmetric group in characteristic zero. The second result is a related statement about parabolic invariants and coinvariants.
    (PostScript file, gzipped PostScript file, PDF file DVI file)
    The Tutte polynomial of a finite projective space (with M. Barany)
    ABSTRACT: We give a generating function for the Tutte polynomials for the arrangements of all hyperplanes in a finite projective space.
    (PostScript file, PDF file)
    Notes on Poincare series of finite and affine Coxeter groups
    ABSTRACT: There are two famous formulae relating the Poincare series of a a finite/affine Weyl groups to the degrees of fundamental invariants for the finite Weyl group. We review the classical proof of the finite formula that uses the Coxeter complex, and sketch Steinberg's analogous proof of the affine (Bott) formula using the ``toroidal'' Coxeter complex.
    (PDF file, and L. Grau's Masters Thesis from Karlsruhe, explicating this topic further)
    An old, but cute, proof of the Catalan formula
    ABSTRACT: A few years ago, my colleague Bill Messing suggested to me a cute proof that I'd never seen, and rather liked, of the formula for the Catalan number. It turns out to be an old proof, but it's worth knowing.
    (PostScript file, gzipped PostScript file, PDF file DVI file)
    Some notes on Pólya's Theorem, Kostka numbers and the RSK correspondence (with D. White)
    ABSTRACT: These are notes that followed up on the "Pólya vs. Schensted" problems raised in Dennis White's last U. Minn. combinatorics seminar talk on Nov. 30, 2012, titled "Unfinished business".
    (PDF file)
    Hopf algebras in Combinatorics (with D. Grinberg)
    ABSTRACT: Notes on Hopf algebras in combinatorics originating from a one-semester topics class at the University of Minnesota.
    (arXiv link)

    Book reviews

    Single and multivariable calculus , an open-source text by David Guichard (co-reviewed with Albert Schueller)
    (MAA review)
    Combinatorics of minuscule representations, Cambridge Tracts in Mathematics 199, by Richard M. Green
    (review in PDF, Bull. Lond. Math. Soc. web page)

    Semi-humorous songs honoring the mathematical legacy of one's advisor

    Countin' like the wind (with C. Chan, I. Gessel, J. Propp, L. Rose, and B. Sagan)
    ABSTRACT: This work honors one of the greats of enumeration (and was sung at the 60th birthday Fest for Richard P. Stanley).
    (PostScript file, gzipped PostScript file, PDF file DVI file)

    Humorous songs written by others honoring the mathematical legacy of one's advisor

    EC1 (lyrics by Jim Propp, music by Frank Loesser from "Guys and Dolls" arranged by Noam Elkies, performed by S. Billey, C. Chan, K. Edwards, T. Roby, L. Rose, M. Skandera, L. Williams, P. Winkler )
    ABSTRACT: (This transpired at the Stanley@70 conference banquet on June 23, 2014.)
    (Lyrics in PowerPoint, Lyrics in PDF)

    The view and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.