Séminaire Lotharingien de Combinatoire, 84B.7 (2020), 12 pp.

Christian Gaetz and Yibo Gao

Separable Elements: Linear Extensions, Graph Associahedra, and Splittings of Weyl Groups

Abstract. We introduce separable elements in finite Weyl groups, generalizing the well-studied class of separable permutations. We prove that the principal upper and lower order ideals in weak Bruhat order generated by a separable element are rank-symmetric and rank-unimodal, and that the product of their rank generating functions equals that of the whole group, answering an open problem of Fan Wei (2012), who proved this result in type A.

We prove that the multiplication map W/V x V -> W for a generalized quotient of the symmetric group is always surjective when V is an order ideal in right weak order; interpreting these sets of permutations as linear extensions of 2-dimensional posets gives the first direct combinatorial proof of an inequality due originally to Sidorenko in 1991, answering an open problem Morales, Pak, and Panova. We show that this multiplication map is a bijection if and only if V is an order ideal in right weak order generated by a separable element, thereby classifying those generalized quotients which induce splittings of the symmetric group, answering a question of Björner and Wachs (1988). All of these results are conjectured to extend to arbitrary finite Weyl groups.

Next, we show that separable elements in W are in bijection with the faces of all dimensions of two copies of the graph associahedron of the Dynkin diagram of W. This correspondence associates to each separable element w a certain nested set; we give elegant product formulas for the rank generating functions of the principal upper and lower order ideals generated by w in terms of these nested sets.

Finally we show that separable elements, although initially defined recursively, have a non-recursive characterization in terms of root system pattern avoidance in the sense of Billey and Postnikov.


Received: November 20, 2019. Accepted: February 20, 2020. Final version: April 30, 2020.

The following versions are available: