# Why is the right permutohedron order (aka weak order) on $S_n$ a lattice?

This is one of those things I never expected to be hard until I tried to prove it. Why is the right permutohedron order (a.k.a. weak Bruhat order, a.k.a. weak order -- not to be confused with the strong Bruhat order) on the symmetric group $S_n$ a lattice?

Details:

Let $n$ be a nonnegative integer. Consider the symmetric group $S_n$, with multiplication defined by $\left(\sigma\pi\right)\left(i\right)=\sigma\left(\pi\left(i\right)\right)$ for all $\sigma$ and $\pi$ in $S_n$ and all $i \in \left\lbrace 1,2,\cdots ,n \right\rbrace$. The right permutohedron order is a partial order on the set $S_n$ and can be defined in the following equivalent ways:

• Two permutations $u$ and $v$ in $S_n$ satisfy $u \leq v$ in the right permutohedron order if and only if the length of the permutation $v^{-1} u$ equals the length of $v$ minus the length of $u$. Here, the length (also known as "Coxeter length") of a permutation is its number of inversions.

• Two permutations $u$ and $v$ in $S_n$ satisfy $u \leq v$ in the right permutohedron order if and only if every pair $\left(i, j\right)$ of elements of $\{ 1, 2, \cdots, n \}$ such that $i < j$ and $u^{-1}\left(i\right) > u^{-1}\left(j\right)$ also satisfies $v^{-1}\left(i\right) > v^{-1}\left(j\right)$. (In more vivid terms, this condition states that whenever two integers $i$ and $j$ satisfy $i < j$ but $i$ stands to the right of $j$ in the one-line notation of the permutation $u$, the integer $i$ must also stand to the right of $j$ in the one-line notation of the permutation $v$.)

• A permutation $v \in S_n$ covers a permutation $u \in S_n$ in the right permutohedron order if and only if we have $v = u \cdot \left(i, i + 1\right)$ for some $i \in \{ 1, 2, \cdots, n - 1 \}$ satisfying $u\left(i\right) < u\left(i + 1\right)$. Here, $\left(i, i + 1\right)$ denotes the transposition switching $i$ with $i + 1$.

(I have mostly quoted these definitions from a part of Sage documentation I've written a while ago. A "left permutohedron order" also exists, but differs from the right one merely by swapping a permutation with its inverse.)

It is easy to prove the equivalence of the above three definitions using nothing but elementary reasoning about inversions and bubblesort. This made me believe that everything about the permutohedron order is simple.

Now I have read in some sources (which all give either no or badly accessible references) that the poset $S_n$ with the right permutohedron order is a lattice. This is related to the Tamari lattice. (Specifically, there is an injection from the Tamari lattice to the permutohedron-ordered $S_n$ sending each binary search tree to a certain 132-avoiding permutation obtained from a postfix reading of the tree, and there is a surjection in the other direction sending each permutation to its binary search tree. If I am not mistaken, these two maps form a Galois connection.) But I am not able to prove the lattice property! I see some obstructions to the existence of overly simple proofs:

• The strong Bruhat order is not a lattice.

• One might think that the meet of two permutations $u$ and $v$ will be a permutation $p$ whose coinversion set (= the set of all pairs $\left(i, j\right)$ of elements of $\{ 1, 2, \cdots, n \}$ such that $i < j$ and $p^{-1}\left(i\right) > p^{-1}\left(j\right)$) will be the intersection of the coinversion sets of $u$ and $v$. This is not the case. A permutation having such a coinversion set might not exist, and the meet has a smaller coinversion set. In particular, it is not always possible to obtain the meet of $u$ and $v$ by bubblesorting each of $u$ and $v$ without ever killing inversions which are common to $u$ and $v$.

• The permutohedron-order lattice is not distributive.

-
I think Bjorner-Brenti gives proofs or look at articles on Garside groups and monoids. This is important for the dual presentation of the braid group. – Benjamin Steinberg Feb 28 '14 at 16:48
I see that your motivation is the relationship with the Tamari lattice. You might be interested in Nathan Reading's papers on Cambrian Lattices (some of them joint with me) which generalize this story to all Coxeter groups. This survey arxiv.org/abs/1109.5105 is a good starting place. – David Speyer Mar 1 '14 at 0:53
@DavidSpeyer: Thanks for the reference; I've looked at this paper yesterday. Does it contain a proof of the lattice property? (What exactly is the relation between the Cambrian lattices and the weak order? Is the latter a particular case of the former? I'm learning some Coxeter groups right now but I am far from speaking them fluently.) – darij grinberg Mar 1 '14 at 5:25

In my opinion, the most elegant proof is by Björner, Edelman and Ziegler (PDF file). They prove the following generalization: Let $\mathcal{H}$ be a finite set of hyperplanes in $\mathbb{R}^n$. Let $\mathcal{D}$ be the set of connected components of $\mathbb{R}^n \setminus \bigcup_{H \in \mathcal{H}} H$. Choose one region in $\mathcal{D}$; call it $D_0$. Put a poset structure on $\mathcal{D}$ as follows: $D_1 \leq D_2$ iff, whenever a hyperplane $H \in \mathcal{H}$ separates $D_1$ from $D_0$, it also separates $D_2$ from $D_0$.

BEZ prove that, if every $D$ in $\mathcal{D}$ is a simplicial cone, then $\mathcal{D}$ is a lattice.

Apply this to the braid arrangement in $\mathbb{R}^{n-1}$ to get weak order on $S_n$.

-
WOW! Their proof is almost abstract nonsense, and yet it works! Stripped of all geometry (which is not necessary in the case of the weak order), their argument is as follows: Due to their Lemma 2.1, it is enough to show that if two permutations $x$ and $y$ both cover another permutation $z$ in the permutohedron order, then they have a join $x\vee y$ in that order. Now this follows from some geometric considerations (apparently the main idea is the "rotatability" of the permutahedron), but since we are only caring about permutations, this can be verified by hand. Thanks for the reference!! – darij grinberg Mar 1 '14 at 5:44
I assume the same idea can be used for the Tamari lattice (in which the covering relations are given by right rotations of binary trees). – darij grinberg Mar 1 '14 at 5:57

Berge has a nice proof in Principles of Combinatorics, reproduced in the solution to Exercise 3.185(b) of my book Enumerative Combinatorics, vol. 1. Namely, $v\leq w$ in weak order if and only if the inversion sets $I_v$ and $I_w$ satisfy $I_v\subseteq I_w$. It follows that $v\vee w$ is defined by $I_{v\vee w}=\overline{I_v\cup I_w}$, where the overline denotes transitive closure. Hence the weak order is a join-semilattice. Since it is a finite poset with a unique minimal element, it is in fact a lattice.

Addendum. Here are some more details. If $w=w_1 w_2\cdots w_n$, then define the inversion set $I_w = \{ (w_i,w_j)\,\colon\, i<j, w_i>w_j\}$. A well-known characterization of inversion sets is that they are those subsets $S$ of $X=\{(i,j)\,\colon\, n\geq i >j\geq 1\}$ such that $S$ and its complement $X-S$ are transitive. Thus we need to show that the complement $Y$ of $\overline{I_v\cup I_w}$ is transitive. Hence if $(i,j),(j,k)\in Y$, then we need to show that $(i,k)\in Y$. This only depends on $i,j,k$, i.e., we need only verify it for the subword of $w$ consisting of the letters $i,j,k$. This is a routine verification.

-
Hmm. Thanks for the reference but I feel that I've just learnt a new meaning of the words "follows readily". I don't even understand Berge's proof. I know that the "$ac \notin E(f) \cap E(g)$" on page 139 should be "$ac \notin E(f) \cup E(g)$", but how does this imply the next line? (I assume "relabeling" means "switching"?) – darij grinberg Mar 1 '14 at 5:23
I don't have access to Berge's book now, but see the addendum to my answer. – Richard Stanley Mar 2 '14 at 17:18
Berge's book (might not stay there forever): f3.tiera.ru/2/M_Mathematics/MA_Algebra/MAc_Combinatorics/… – darij grinberg Mar 2 '14 at 17:58
Thanks for the details! I understand the characterization of inversion sets. What I don't see yet is why the transitivity claim is really local to three points $i,j,k$. Since $Y$ itself is a transitive closure, the existing relations $(i,j),(j,k)\in Y$ might themselves come from long chains of alternating $v$- and $w$-inversions. – darij grinberg Mar 2 '14 at 18:00
@Darij, one way to prove this is by induction on $k-i$, the base case $k-i=2$ being clear. Is this enough of a hint? – Richard Stanley Mar 3 '14 at 14:37

This is a reply to the questions about the Tamari lattice, not to the question in the title. The Tamari lattice is both a sublattice and a quotient lattice of $S_n$, with the inclusion and quotient maps you have described.

Regarding the fact that the map $S_n \to \mathrm{Tamari}$ is a map of lattices, Nathan Reading writes

The starting point of the present research is the observation that the Tamari lattice is a lattice-homomorphic image of the right weak order on the symmetric group. This fact has, to our knowledge, never appeared in the literature, although essentially all the ingredients of a proof were assembled by Björner and Wachs

So Nathan's paper may be the first reference for this fact in print. See Theorem 6.2 for the fact that the quotient map is a map of lattices and 6.5 for the fact that the inclusion is a map of lattices. Nathan writes that, for the Tamari lattice, the result about the inclusion is already in Björner and Wachs.

The goal of Nathan (and later my) work is to define a similar sub-and-quotient lattice story for any Coxeter group and any orientation of the Dynkin diagram; the Tamari lattice corresponds to $A_{n-1}$ with all arrows oriented in the same direction. If we stay in $S_n$ but look at other orientations of the Dynkin diagram, we get other posets whose Hasse diagrams are all various orientations of the $1$-skeleton of the associahedron. See sections 4-6 of Reading's linked paper for what this construction does in type A.

Nathan's paper linked above mostly makes a definition and gives proofs in types A and B. Later research has focused on other types and connections to other areas of math. Here what I consider the other main papers in this vein.

-
About Reading's claim that This fact has, to our knowledge, never appeared in the literature'': it appears in arXiv:math/0102066v1 by Loday and Ronco (2001) as Corollary 2.6. (I am not 100% sure if the map $\psi_n$ is the same as the map Reading constructs due to the many different conventions used.) – darij grinberg Mar 3 '14 at 3:08
Thanks for the literature review! These are lots of papers written in a foreign language to me, and it is good to have an idea how they translate into standard combinatorial terms in the $A_n$ case. Maybe I'll get to understand this theory eventually... – darij grinberg Mar 3 '14 at 3:11
@darij: The Loday and Ronco Corollary is only the assertion that the map is order-preserving. The assertion that the map is a lattice homomorphism is stronger. (It needs to preserve meets and joins in the same sense that a group homomorphism preserves products.) – Nathan Reading Mar 6 '14 at 21:13
Ah, so this is what "lattice-homomorphic" means! Am I seeing it right that this follows immediately from the fact that the functor "binary search tree" from the weak order lattice to the Tamari lattice (where lattices are regarded as categories) has adjoints on both sides (which send a binary search tree to its postfix reading, in left-to-right or right-to-left orders depending on which side we want) and thus preserves both limits and colimits? (I assume this can be reworded in terms of Galois connections, but I'm more familiar with functorial terminology.) – darij grinberg Mar 6 '14 at 21:16
Thanks, David for providing these summaries. One correction: Sortable elements and Cambrian lattices doesn't directly prove any of the conjectures, but provides a link in the chain of proving them: the original Cambrian lattices paper gives a general lattice-theoretic definition of Cambrian lattices; the "Coxeter-sortable elements" paper introduces sortable elements; and "Sortable elements and Cambrian lattices" makes the connection between the two definitions. Most of the original conjectures are phrased in terms of Cambrian lattices & proved in the later papers using sortable elements. – Nathan Reading Mar 6 '14 at 21:33

Stembridge in his article "On the fully commutative elements of Coxeter groups" says "by a theorem of Björner [3], one knows that every subinterval of the weak order is at least a lattice."

The reference is to Anders Björner's paper "Orderings of Coxeter groups" available online here. But I cannot figure out how to get MIT libproxy to let me read this article, so I cannot say for sure.

-
Thanks for reminding me of Björner -- it turns out there is a proof in §3.2 of Björner/Brenti "Combinatorics of Coxeter Groups". I'm going to see what it translates to in the $S_n$ case... – darij grinberg Feb 28 '14 at 5:02
Oh, "Polygon Posets and the Weak Order of Coxeter Groups" by Kimmo Eriksson seems to also have it! ( ftp4.de.freesbie.org/pub/misc/EMIS/journals/JACO/Volume4_3/… ) – darij grinberg Feb 28 '14 at 5:05
The Björner reference announces the lattice result but does not prove it. (The proof is said to be in "The weak ordering of a Coxeter group", in preparation, but apparently this paper never appeared. It is not in MathSciNet anyway.) – Nathan Reading Mar 6 '14 at 21:18

I've just got a glimpse of a proof by induction. Given two vertices of a permutohedron, the smallest face containing them is a product of permutohedra. If they are of lower dimension then by induction it is a lattice whose top and bottom will give join and meet of the corresponding permutations. The only case when there is no dimension drop is when the smallest face is the whole permutohedron, and then the join is the top (...321) and the meet is the bottom (123...).

The argument depends on the fact that the product order on the mentioned product of permutohedra coincides with the induced order on the face. This is more or less clear from the geometric picture: the Hasse diagram can be given by the edge graph of the permutohedron, with each edge pointing from bigger value of $c_1\sigma(1)+c_2\sigma(2)+c_3\sigma(3)+...$ to smaller, where $c_1<c_2<c_3<...$ can be arbitrary. I think this can be used to make it clear that the induced orientations of the edges are the same as the original ones on each factor of the product, since these factors correspond to freezing some of the $\sigma(k)$ in the ambient permutohedron.

Hope this can be made into an actual proof...

-

A proof is in George Markowsky, "Permutation Lattices Revisited," Mathematical Social Sciences 27 (1994), 59-72. http://www.umcs.maine.edu/~markov/permutationlattices.pdf

-