Combinatorial Theory

We reinterpret an inequality, due originally to Sidorenko, for linear extensions of posets in terms of convex subsets of the symmetric group \(\mathfrak{S}_n\). We conjecture that the analogous inequalities hold in arbitrary (not-necessarily-finite) Coxeter groups \(W\), and prove this for the hyperoctahedral groups \(B_n\) and all right-angled Coxeter groups. Our proof for \(B_n\) (and new proof for \(\mathfrak{S}_n\)) use a combinatorial insertion map closely related to the well-studied promotion operator on linear extensions; this map may be of independent interest. We also note that the inequalities in question can be interpreted as a triangle inequalities, so that convex hulls can be used to define a new invariant metric on \(W\) whenever our conjecture holds. Geometric properties of this metric are an interesting direction for future research.

Mathematics Subject Classifications: 05A20, 05C12, 05E16, 20F55

Keywords: Linear extension, promotion, Coxeter group, convex hull, metric