Shelling Coxeter-like Complexes and Sorting on Trees

Abstract

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.

23 pages