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