SHELLING COXETER-LIKE COMPLEXES AND SORTING ON TREES

Abstract. 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 Cox-eter 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 inver-sion functions on the labellings of a tree T which imply shellabil-ity 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 eac