Shelling Coxeter-like complexes and sorting on trees

Abstract: In their work on ‘Coxeter-like complexes’, Babson and Reiner introduced a simplicial complex associated to each tree T on n nodes, generalizing chessboard complexes and type A Coxeter complexes. They conjectured that is -connected when the tree has b leaves. We provide a shelling for the -skeleton of , 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 , 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 with . 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. [Copyright &y& Elsevier]