Search

We introduce a new class of poset edge labelings for locally finite lattices which we call $SB$-labelings. We prove for finite lattices which admit an $SB$-labeling that each open interval has the homotopy type of a ball or of a sphere of some dimension. Natural examples include the weak order, the Tamari lattice, and the finite distributive lattices., Comment: 16 pages; 3 figures; accepted to Journal of Combinatorial Theory Series A

We prove a conjecture of Thomas Lam that the face posets of stratified spaces of planar resistor networks are shellable. These posets are called uncrossing partial orders. This shellability result combines with Lam's previous result that these same posets are Eulerian to imply that they are CW posets, namely that they are face posets of regular CW complexes. Certain subsets of uncrossing partial orders are shown to be isomorphic to type A Bruhat order intervals; our shelling is shown to coincide on these intervals with a Bruhat order shelling which was constructed by Matthew Dyer using a reflection order. Our shelling for uncrossing posets also yields an explicit shelling for each interval in the face posets of the edge product spaces of phylogenetic trees, namely in the Tuffley posets, by virtue of each interval in a Tuffley poset being isomorphic to an interval in an uncrossing poset. This yields a more explicit proof of the result of Gill, Linusson, Moulton and Steel that the CW decomposition of Moulton and Steel for the edge product space of phylogenetic trees is a regular CW decomposition., 26 pages, 5 figures; additional corollary to the main result added, namely an explicit shelling for each poset interval in the face poset for the edge product space of phylogenetic trees

In their work on `Coxeter-like complexes', Babson and Reiner introduced a simplicial complex $\Delta_T$ associated to each tree $T$ on $n$ nodes, generalizing chessboard complexes and type A Coxeter complexes. They conjectured that $\Delta_T$ is $(n-b-1)$-connected when the tree has $b$ leaves. We provide a shelling for the $(n-b)$-skeleton of $\Delta_T$, thereby proving this conjecture. In the process, we introduce notions of weak order and inversion functions on the labellings of a tree $T$ which imply shellability of $\Delta_T$, and we construct such inversion functions for a large enough class of trees to deduce the aforementioned conjecture and also recover the shellability of chessboard complexes $M_{m,n}$ with $n \ge 2m-1$. We also prove that the existence or nonexistence of an inversion function for a fixed tree governs which networks with a tree structure admit greedy sorting algorithms by inversion elimination and provide an inversion function for trees where each vertex has capacity at least its degree minus one., Comment: 23 pages

We investigate the ways in which fundamental properties of the weak Bruhat order on a Weyl group can be lifted (or not) to a corresponding highest weight crystal graph, viewed as a partially ordered set; the latter projects to the weak order via the key map. First, a crystal theoretic analogue of the statement that any two reduced expressions for the same Coxeter group element are related by Coxeter moves is proven for all lower intervals in a simply or doubly laced crystal. On the other hand, it is shown that no finite set of moves exists, even in type A, for arbitrary crystal graph intervals. In fact, it is shown that there are relations of arbitrarily high degree amongst crystal operators that are not implied by lower degree relations. Second, for crystals associated to Kac-Moody algebras it is shown for lower intervals that the Mobius function is always 0, 1, or -1, and in finite type this is also proven for upper intervals, with a precise formula given in each case. Moreover, the order complex for each of these intervals is proven to be homotopy equivalent to a ball or to a sphere of some dimension, despite often not being shellable. For general intervals, examples are constructed with arbitrarily large Mobius function, again even in type A. Any interval having Mobius function other than 0, 1, or -1 is shown to contain within it a relation amongst crystal operators that is not implied by the relations giving rise to the local structure of the crystal, making precise a tight relationship between the Mobius function and these somewhat unexpected relations appearing in crystals. New properties of the key map are also derived. The key is shown to be determined entirely by the edge-colored poset-theoretic structure of the crystal, and a recursive algorithm is given for calculating it., Comment: 30 pages, 2 figures. Some results in the first version are extended from finite type to arbitrary symmetrizable Kac-Moody type. Section 8 was added, discussing the relationship between the topology and the Stembridge relations

We introduce a homological approach to exhibiting instances of Stembridge's q=-1 phenomenon. This approach is shown to explain two important instances of the phenomenon, namely that of partitions whose Ferrers diagrams fit in a rectangle of fixed size and that of plane partitions fitting in a box of fixed size. A more general framework of invariant and coinvariant complexes with coefficients taken mod 2 is developed, and as a part of this story an analogous homological result for necklaces is conjectured.

A toric cube is a subset of the standard cube defined by binomial inequalities. These basic semialgebraic sets are precisely the images of standard cubes under monomial maps. We study toric cubes from the perspective of topological combinatorics. Explicit decompositions as CW-complexes are constructed. Their open cells are interiors of toric cubes and their boundaries are subcomplexes. The motivating example of a toric cube is the edge-product space in phylogenetics, and our work generalizes results known for that space., to appear in Rendiconti del Circolo Matematico di Palermo (special issue on Algebraic Geometry)

Geometric lattices are characterized in this paper as those finite, atomic lattices such that every atom ordering induces a lexicographic shelling given by an edge labeling known as a minimal labeling. Equivalently, geometric lattices are shown to be exactly those finite lattices such that every ordering on the join-irreducibles induces a lexicographic shelling. This new characterization fits into a similar paradigm as McNamara's characterization of supersolvable lattices as those lattices admitting a different type of lexicographic shelling, namely one in which each maximal chain is labeled with a permutation of {1,...,n}., Additional results added, expository revisions. 9 pages

The quotient of a Boolean algebra by a cyclic group is proven to have a symmetric chain decomposition. This generalizes earlier work of Griggs, Killian and Savage on the case of prime order, giving an explicit construction for any order, prime or composite. The combinatorial map specifying how to proceed downward in a symmetric chain is shown to be a natural cyclic analogue of the $\mathfrak{sl}_2$ lowering operator in the theory of crystal bases., minor revisions; to appear in IMRN

This paper proves a conjecture of Fomin and Shapiro that their combinatorial model for any Bruhat interval is a regular CW complex which is homeomorphic to a ball. The model consists of a stratified space which may be regarded as the link of an open cell intersected with a larger closed cell, all within the totally nonnegative part of the unipotent radical of an algebraic group. A parametrization due to Lusztig turns out to have all the requisite features to provide the attaching maps. A key ingredient is a new, readily verifiable criterion for which finite CW complexes are regular involving an interplay of topology with combinatorics., accepted to Inventiones Mathematicae; 60 pages; substantially revised from earlier versions

Conditions are provided under which an endomorphism on quasisymmetric functions gives rise to a left random walk on the descent algebra which is also a lumping of a left random walk on permutations. Spectral results are also obtained. Several well-studied random walks are now realized this way: Stanley's QS-distribution results from endomorphisms given by evaluation maps, a-shuffles result from the a-th convolution power of the universal character, and the Tchebyshev operator of the second kind introduced recently by Ehrenborg and Readdy yields traditional riffle shuffles. A conjecture of Ehrenborg regarding the spectra for a family of random walks on ab-words is proven. A theorem of Stembridge from the theory of enriched P-partitions is also recovered as a special case., 25 pages

Steingrimsson's coloring complex and Jonsson's unipolar complex are interpreted in terms of hyperplane arrangements. This viewpoint leads to short proofs that all coloring complexes and a large class of unipolar complexes have convex ear decompositions. These convex ear decompositions impose strong new restrictions on the chromatic polynomials of all finite graphs. Similar results are obtained for characteristic polynomials of submatroids of type B_n arrangements., Comment: 11 pages. To appear in the Journal of Algebraic Combinatorics

Forman introduced discrete Morse theory as a tool for studying CW complexes by essentially collapsing them onto smaller, simpler-to-understand complexes of critical cells in [Fo]. Chari reformulated discrete Morse theory for regular cell complexes in terms of acyclic matchings on face posets in [Ch]. This paper addresses two questions: (1) under what conditions may several gradient paths in a discrete Morse function simultaneously be reversed to cancel several pairs of critical cells, to further collapse the complex, and (2) how to use lexicographically first reduced expressions for permutations (in the sense of [Ed]) to make (1) practical for poset order complexes. Applications include Cohen-Macaulayness of a new partial order, recently introduced by Remmel, on the symmetric group (by refinement on the underlying partitions into cycles) as well as a simple new proof of the homotopy type for intervals in the weak order for the symmetric group. Additional applications appear in [HW]., This update includes fairly significant revisions that were made prior to the original journal publication of the article

This paper verifies a conjecture of Edelman and Reiner regarding the homology of the h-complex of a Boolean algebra. A discrete Morse function with no low-dimensional critical cells is constructed, implying a lower bound on connectivity. This together with an Alexander duality result of Edelman and Reiner implies homology vanishing also in high dimensions. Finally, possible generalizations to certain classes of supersolvable lattices are suggested.

llReiner and Webb (preprint, 2002) compute the S n -module structure for the complex of injective words. This paper refines their formula by providing a Hodge type decomposition. Along the way, this paper proves that the simplicial boundary map interacts in a nice fashion with the Eulerian idempotents. The Laplacian acting on the top chain group in the complex of injective words is also shown to equal the signed random to random shuffle operator. Uyemura-Reyes, 2002, conjectured that the (unsigned) random to random shuffle operator has integral spectrum. We prove that this conjecture would imply that the Laplacian on (each chain group in) the complex of injective words has integral spectrum.