2008/09/14 by Patricia Hersh, Hersh, Patricia
Computer Science · Mathematics · #05E25 #68R05 #Advanced Combinatorial Mathematics #Algebraic structures and combinatorial models #Combinatorics (math.CO) #FOS: Mathematics #Topological and Geometric Data Analysis #math.CO #msc:05E25 #msc:68R05
paper · pdf · doi:10.48550/arxiv.0809.2414
23 pages
arxiv created 2008/09/14 · openalex publication_date 2008/09/14 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In their work on `Coxeter-like complexes', Babson and Reiner introduced a simplicial complex ΔT associated to each tree T on n nodes, generalizing chessboard complexes and type A Coxeter complexes. They conjectured that ΔT is (n-b-1)-connected when the tree has b leaves. We provide a shelling for the (n-b)-skeleton of Δ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 Δ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 Mm,n with n ≥ 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.