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.
Best Answer
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$.