Shelling Coxeter-like complexes and sorting on trees

DOI10.1016/J.AIM.2009.01.007MaRDI QIDQ1018417zbMATH OpenOpenAlexFDO

Authors Patricia Hersh

Publication date 19 May 2009

Published in Advances in Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0809.2414

zbMATH Keywords

sortingweak ordershellabilityshellingCoxeter complexchessboard complexgreedy sorting algorithmsimplicial complex associated to treesorting on tree

Mathematics Subject Classification ID

Trees (05C05) Searching and sorting (68P10) Simplicial sets and complexes in algebraic topology (55U10) Combinatorics of partially ordered sets (06A07)

Abstract: In their work on `Coxeter-like complexes', Babson and Reiner introduced a simplicial complex $Delt{a}_T$ associated to each tree $T$ on $n$ nodes, generalizing chessboard complexes and type A Coxeter complexes. They conjectured that $Delt{a}_T$ is $(n-b-1)$-connected when the tree has $b$ leaves. We provide a shelling for the $(n-b)$-skeleton of $Delt{a}_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 $Delt{a}_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 $nge2m-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.

Recommendations

• Shellability of complexes of trees
• scientific article; zbMATH DE number 2077658
• Shellability of complexes of directed trees
• Complexes of trees and nested set complexes
• Shellability and higher Cohen-Macaulay connectivity of generalized cluster complexes

Cites work

• scientific article; zbMATH DE number 47598 (Why is no real title available?)
• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• scientific article; zbMATH DE number 2159639 (Why is no real title available?)
• scientific article; zbMATH DE number 195193 (Why is no real title available?)
• scientific article; zbMATH DE number 863503 (Why is no real title available?)
• Chessboard Complexes and Matching Complexes
• Decompositions and connectivity of matching and chessboard complexes
• Minimal resolutions and the homology of matching and chessboard complexes
• On the Betti numbers of chessboard complexes
• Posets, regular CW complexes and Bruhat order
• Shellability of chessboard complexes
• Some combinatorial and algebraic properties of Coxeter complexes and Tits buildings
• The colored Tverberg's problem and complexes of injective functions
• Topology of matching, chessboard, and general bounded degree graph complexes
• Torsion in the matching complex and chessboard complex
• f-vectors and h-vectors of simplicial posets

Cited in

(2)

• Principal -cone for a tree
• Shellable quasi-forests and their \(h\)-triangles

This page was built for publication: Shelling Coxeter-like complexes and sorting on trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1018417)