Search

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

Backelin proved that the multigraded Poincare series for resolving a residue field over a polynomial ring modulo a monomial ideal is a rational function. The numerator is simple, but until the recent work of Berglund there was no combinatorial formula for the denominator. Berglund's formula gives the denominator in terms of ranks of reduced homology groups of lower intervals in a certain lattice. We now express this lattice as the intersection lattice L A ( I ) of a subspace arrangement A ( I ) , use Crapo's Closure Lemma to drastically simplify the denominator in some cases (such as monomial ideals generated in degree two), and relate Golodness to the Cohen–Macaulay property for associated posets. In addition, we introduce a new class of finite lattices called complete lattices, prove that all geometric lattices are complete and provide a simple criterion for Golodness of monomial ideals whose lcm-lattices are complete.

This paper shows how to construct a discrete Morse function with a relatively small number of critical cells for the order complex of any finite poset with 0 ^ \hat {0} and 1 ^ \hat {1} from any lexicographic order on its maximal chains. Specifically, if we attach facets according to the lexicographic order on maximal chains, then each facet contributes at most one new face which is critical, and at most one Betti number changes; facets which do not change the homotopy type also do not contribute any critical faces. Dimensions of critical faces as well as a description of which facet attachments change the homotopy type are provided in terms of interval systems associated to the facets. As one application, the Möbius function may be computed as the alternating sum of Morse numbers. The above construction enables us to prove that the poset Π n / S λ \Pi _n/S_{\lambda } of partitions of a set { 1 λ 1 , … , k λ k } \{ 1^{\lambda _1 },\dots ,k^{\lambda _k }\} with repetition is homotopy equivalent to a wedge of spheres of top dimension when λ \lambda is a hook-shaped partition; it is likely that the proof may be extended to a larger class of λ \lambda and perhaps to all λ \lambda , despite a result of Ziegler (1986) which shows that Π n / S λ \Pi _n/S_{\lambda } is not always Cohen-Macaulay.

We study the multiplicity bS(n) of the trivial representation in the symmetric group representations βS on the (top) homology of the rank-selected partition lattice ΠnS. We break the possible rank sets S into three cases: (1) 1∉S, (2) S=1,…,i for i⩾1, and (3) S=1,…,i,j1,…,jl for i,l⩾1, j1>i+1. It was previously shown by Hanlon that bS(n)=0 for S=1,…,i. We use a partitioning for Δ(Πn)/Sn due to Hersh to confirm a conjecture of Sundaram [S. Sundaram, The homology representations of the symmetric group on Cohen–Macaulay subposets of the partition lattice, Adv. Math. 104 (1994) 225–296] that bS(n)>0 for 1∉S. On the other hand, we use the spectral sequence of a filtered complex to show bS(n)=0 for S=1,…,i,j1,…,jl unless a certain type of chain of support S exists. The partitioning for Δ(Πn)/Sn allows us then to show that a large class of rank sets S=1,…,i,j1,…,jl for which such a chain exists do satisfy bS(n)>0. We also generalize the partitioning for Δ(Πn)/Sn to Δ(Πn)/Sλ; when λ=(n−1,1), this partitioning leads to a proof of a conjecture of Sundaram about (S1×Sn−1)-representations on the homology of the partition lattice.

We study the quotient complex Δ(B lm )/S l ≀S m as a means of deducing facts about the ring k[x 1 ,…,x lm ] S l ≀S m . It is shown in Hersh (preprint, 2000) that Δ(B lm )/S l ≀S m is shellable when l =2, implying Cohen–Macaulayness of k[x 1 ,…,x 2m ] S 2 ≀S m for any field k . We now confirm for all pairs ( l , m ) with l >2 and m >1 that Δ(B lm )/S l ≀S m is not Cohen–Macaulay over Z /2 Z , but it is Cohen–Macaulay over fields of characteristic p > m (independent of l ). This yields corresponding characteristic-dependent results for k[x 1 ,…,x lm ] S l ≀S m . We also prove that Δ(B lm )/S l ≀S m and the links of many of its faces are collapsible, and we give a partitioning for Δ(B lm )/S l ≀S m .

We introduce a notion of lexicographic shellability for pure, balanced boolean cell complexes, modelled after the CL-shellability criterion of Bjorner and Wachs (Adv. in Math. 43 (1982), 87–100) for posets and its generalization by Kozlov (Ann. of Comp. 1(1) (1997), 67–90) called CC-shellability. We give a lexicographic shelling for the quotient of the order complex of a Boolean algebra of rank 2n by the action of the wreath product S2 w Sn of symmetric groups, and we provide a partitioning for the quotient complex Δ(Πn)/Sn. Stanley asked for a description of the symmetric group representation βS on the homology of the rank-selected partition lattice ΠnS in Stanley (J. Combin. Theory Ser. A 32(2) (1982), 132–161), and in particular he asked when the multiplicity bS(n) of the trivial representation in βS is 0. One consequence of the partitioning for Δ(Πn)/Sn is a (fairly complicated) combinatorial interpretation for bS(n)s another is a simple proof of Hanlon's result (European J. Combin. 4(2) (1983), 137–141) that b1,…,i(n) e 0. Using a result of Garsia and Stanton from (Adv. in Math. 51(2) (1984), 107–201), we deduce from our shelling for Δ(B2n)/S2 w Sn that the ring of invariants k[x1,…,x2n]S2 w Sn is Cohen-Macaulay over any field k.

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

Algebraic complexes whose "faces'' are indexed by partitions and plane partitions are introduced, and their homology is proven to be concentrated in even dimensions with homology basis indexed by fixed points of an involution, thereby explaining topologically two quite important instances of Stembridge's $q=-1$ phenomenon. 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 topological result for necklaces is conjectured., Complexes algébriques dont les "faces'' sont indexées par des partitions et des partitions planes sont introduits. Il est démontré que leur homologie est concentrée en dimensions paires, avec base de homologie indexée par des points fixes d'une involution. Ce résultat explique d'une manière topologique deux instances du phénomène $q=-1$ dû a Stembridge. De plus, un cadre plus général des complexes invariants et coinvariants dont les coefficients sont pris modulo $2$ est développé. Comme part de cette histoire, nous conjecturons un résultat analogue pour des colliers.

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.