Some papers- Vic Reiner

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 GL_n(F_q) (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 ``7^th variation'' of Schur functions, the other relating to permutation statistics and Hilbert series from the invariant theory of GL_n(F_q)

(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

• defines a Hopf morphism from the Hopf algebra of matroids to the quasisymmetric functions, which is surjective if one uses rational coefficients,
• is a multivariate generating function for integer weight vectors that give minimum total weight to a unique base of the matroid,
• is equivalent, via the Hopf antipode, to a generating function for integer weight vectors which keeps track of how many bases minimize the total weight,
• behaves simply under matroid duality,
• has a simple expansion in terms of $P$-partition enumerators, and
• is a valuation on decompositions of matroid base polytopes.

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 R^d (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 D_n (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 K_n 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 K_n 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 K_n 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 )

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.)

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 GL_n(F_q) (with D. Stanton and P. Webb)

ABSTRACT: Two related results are proven in the modular invariant theory of GL_n(F_q). 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.

(PostScript file, gzipped PostScript file, PDF file DVI file)

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)

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)

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.