Shelling Coxeter-like Complexes and Sorting on Trees
| dc.creator | Hersh, Patricia | |
| dc.date | 2008-09-14 | |
| dc.date.accessioned | 2026-07-07T10:02:48Z | |
| dc.date.available | 2026-07-07T10:02:48Z | |
| dc.description | 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 $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. | |
| dc.description | 23 pages | |
| dc.identifier | https://arxiv.org/abs/0809.2414 | |
| dc.identifier | http://arxiv.org/abs/0809.2414 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/169102 | |
| dc.subject | Combinatorics | |
| dc.subject | 05E25, 68R05 | |
| dc.title | Shelling Coxeter-like Complexes and Sorting on Trees | |
| dc.type | text |