A homological obstruction to weak order on trees
Wednesday, May 2, 2007 - 11:15am - 12:15pm
When sorting data on a network of computers, it is natural to ask which data swaps between neighbors constitute progress. In a linear array, the answer is simple, by virtue of the fact that permutations admit pleasant notions of inversions and weak order. I will discuss how the topology of chessboard complexes constrains the extent to which these ideas may carry over to other trees; it turns out that there are homological obstructions telling us that a tree does not admit an inversion function unless each node has at least as much capacity as its degree minus one. On the other hand, we construct an inversion function and weak order for all trees that do meet this capacity requirement, and we prove a connectivity bound conjectured by Babson and Reiner for 'Coxeter-like complexes' along the way.