Combinatorial Theory

We show that a Weyl group element is boolean if and only if it avoids a set of Billey-Postnikov patterns, which we describe explicitly. Our proof is based on analysis of inversion sets, and it is in large part type-uniform. We also introduce the notion of linear pattern avoidance, and show that boolean elements are characterized by avoiding just \(3\) linear patterns in types \(A_2\), \(A_3\), and \(D_4\), respectively.

We also consider the more general case of \(k\)-boolean Weyl group elements. We say that a Weyl group element \(w\) is \(k\)-boolean if every reduced expression for \(w\) contains at most \(k\) copies of each generator. We show that the \(2\)-boolean elements of the symmetric group are characterized by avoiding the patterns \(3421,4312,4321,\) and \(456123\), and obtain their generating function.

Mathematics Subject Classifications: 05A05, 20F55

Keywords: Boolean permutations, Bruhat orders, Billey-Postnikov patterns, Weyl groups