Permutree Sorting, Lattice Quotients, and Automata

Abstract: We define permutree sorting which generalizes Knuth's stack sorting and Reading's Coxeter sorting algorithms. (U,D)-permutree sorting consists of an algorithm that succeeds or fails for a permutation depending if it contains or avoids certain patterns determined by the sets U and D. We present this algorithm through a family of automata that read reduced words and show that the accepted reduced words form a search-tree structure related to lattice quotients of the weak order. This is joint work with Vincent Pilaud and Viviane Pons.

combinatorics

Audience: researchers in the topic

York University Applied Algebra Seminar