Shelling Coxeter-like Complexes and Sorting on Trees

Details Shelling Coxeter-like Complexes and Sorting on Trees Shelling Coxeter-like Complexes and Sorting on Trees

2008-09-14

arxiv.org/abs/0809.2414v1

Mathematics

Combinatorics

23 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Shelling Coxeter-like Complexes and Sorting on Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Shelling Coxeter-like Complexes and Sorting on Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shelling Coxeter-like Complexes and Sorting on Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-156240