[proofplan] We define Björner's edge labelling and verify the EL-condition on an arbitrary interval $[\sigma,\tau] \subseteq \Pi_n$. The interval decomposes according to the blocks of $\tau$: only blocks of $\sigma$ lying in the same block of $\tau$ may be merged. In each target block, the unique increasing chain repeatedly merges the block with smallest current minimum into the remaining blocks in increasing order of their original minima, and the chains for different target blocks are interleaved by lexicographic order of their labels. We prove that any increasing maximal chain must follow exactly this prescription, so it is unique and lexicographically first; shellability then follows from the [EL-shellability theorem](/theorems/6507). [/proofplan] [step:Define the edge labels and the target blocks inside an interval] Fix an interval $[\sigma,\tau]$ in $\Pi_n$. Write the blocks of $\tau$ as \begin{align*} C_1,\dots,C_s \subseteq [n]. \end{align*} For each $j \in \{1,\dots,s\}$, let \begin{align*} \mathcal{B}_j := \{B \in \sigma : B \subseteq C_j\} \end{align*} be the set of blocks of $\sigma$ lying inside the target block $C_j$. Since $\sigma \leq \tau$, every block of $\sigma$ lies in a unique block of $\tau$, and a maximal chain from $\sigma$ to $\tau$ is obtained by merging, for each $j$, all blocks in $\mathcal{B}_j$ into the single block $C_j$. For a cover relation $\pi \lessdot \pi'$ in the interval, the partition $\pi'$ is obtained from $\pi$ by merging two blocks $A$ and $B$ of $\pi$ that are contained in the same block of $\tau$. Define \begin{align*} \lambda(\pi,\pi') := (\min A,\min B) \end{align*} after ordering the two blocks so that $\min A < \min B$. The label set is $\mathbb{N} \times \mathbb{N}$ with lexicographic order: $(a,b) <_{\mathrm{lex}} (c,d)$ if either $a<c$, or $a=c$ and $b<d$. [/step] [step:Construct the candidate increasing maximal chain] For each target block $C_j$, list the blocks in $\mathcal{B}_j$ as \begin{align*} B_{j,1},B_{j,2},\dots,B_{j,r_j} \end{align*} so that \begin{align*} \min B_{j,1} < \min B_{j,2} < \cdots < \min B_{j,r_j}. \end{align*} If $r_j=1$, no merger is needed inside $C_j$. If $r_j \geq 2$, define the prescribed mergers inside $C_j$ by successively merging the current block containing $B_{j,1}$ with $B_{j,2}$, then with $B_{j,3}$, and so on through $B_{j,r_j}$. The labels produced inside $C_j$ are precisely \begin{align*} (\min B_{j,1},\min B_{j,2}),\quad (\min B_{j,1},\min B_{j,3}),\quad \dots,\quad (\min B_{j,1},\min B_{j,r_j}). \end{align*} Now take the union of all these prescribed mergers over all $j \in \{1,\dots,s\}$, and perform them in increasing lexicographic order of their labels. This produces a maximal chain from $\sigma$ to $\tau$, because each merger occurs inside a block of $\tau$ and, after all listed mergers have been performed, every family $\mathcal{B}_j$ has become the single block $C_j$. The label sequence of this chain is increasing by construction, since the prescribed mergers are executed in lexicographic order. [/step] [step:Show that every increasing maximal chain must begin with the smallest available label] Let $\pi$ be any element of $[\sigma,\tau]$ different from $\tau$. For each block $C_j$ of $\tau$, consider the collection of current blocks of $\pi$ contained in $C_j$. Among all cover relations $\pi \lessdot \pi'$ inside $[\sigma,\tau]$, choose the one whose label is lexicographically minimal, and write this minimal label as $(a,b)$. Let $A$ and $B$ denote the two current blocks of $\pi$ that realize this label, ordered so that $\min A=a$ and $\min B=b$. We claim that an increasing maximal chain from $\pi$ to $\tau$ must use the cover merging $A$ and $B$ as its first edge. Suppose instead that such a chain first merges two current blocks $D$ and $E$, ordered so that $\min D=c$ and $\min E=d$, with first label $(c,d)$ satisfying $(a,b)<_{\mathrm{lex}}(c,d)$. Since $A$ and $B$ lie in the same block of $\tau$, the blocks containing $A$ and $B$ must eventually become one block before the chain reaches $\tau$. Let $t$ be the first later edge at which the current block containing $A$ is merged with the current block containing $B$. Immediately before this edge, let $A_t$ and $B_t$ denote those two current blocks, with $A \subseteq A_t$ and $B \subseteq B_t$. The first edge did not merge $A$ with $B$, so $t$ exists and occurs after the first edge. Write \begin{align*} \alpha_t := \min A_t \end{align*} and \begin{align*} \beta_t := \min B_t. \end{align*} Because $A \subseteq A_t$ and $B \subseteq B_t$, we have $\alpha_t \leq a$ and $\beta_t \leq b$. The two blocks $A_t$ and $B_t$ are distinct until time $t$, so their minima are distinct. Therefore the label at time $t$ is either $(\alpha_t,\beta_t)$ or $(\beta_t,\alpha_t)$ after ordering the two entries increasingly. This later label is lexicographically at most $(a,b)$: its smaller entry is at most $a$, and if the smaller entry equals $a$, then the other entry is at most $b$. Hence this later label is strictly smaller than the first label $(c,d)$. Thus the label sequence has a descent, contradicting the assumption that the chain is increasing. Thus no increasing maximal chain can start with a label larger than the minimal available label $(a,b)$. Therefore every increasing maximal chain from $\pi$ to $\tau$ begins with the lexicographically minimal available merger. [guided] We prove a local forcing statement: once we are at a partition $\pi$ inside the interval $[\sigma,\tau]$, the first edge of any increasing chain is forced. The only allowed mergers are mergers of two current blocks of $\pi$ that lie inside the same block of $\tau$. Among all such allowed mergers, choose the lexicographically smallest label and call it $(a,b)$. This means there are two current blocks, say $A$ and $B$, with \begin{align*} \min A = a \end{align*} and \begin{align*} \min B = b, \end{align*} with $a<b$, and no allowed merger has a smaller label. Suppose a maximal chain from $\pi$ to $\tau$ starts with a different merger. Let the two blocks merged at the first edge be $D$ and $E$, ordered so that $\min D=c$ and $\min E=d$. Its first label is $(c,d)$, and because it is not the chosen minimal edge, we are considering the case \begin{align*} (a,b) <_{\mathrm{lex}} (c,d). \end{align*} The blocks $A$ and $B$ lie in the same block of $\tau$, so they cannot remain separated all the way to $\tau$. At some later time, the current block containing $A$ must merge with the current block containing $B$. Let $t$ be the first later edge where this happens. Just before that edge, denote by $A_t$ the current block containing $A$ and by $B_t$ the current block containing $B$. Define their minima by \begin{align*} \alpha_t := \min A_t \end{align*} and \begin{align*} \beta_t := \min B_t. \end{align*} Since blocks only grow by mergers, $A \subseteq A_t$ and $B \subseteq B_t$. Therefore their minima can only decrease: \begin{align*} \alpha_t \leq a \end{align*} and \begin{align*} \beta_t \leq b. \end{align*} The label on the edge at time $t$ is obtained by ordering the two minima increasingly, so it is either $(\alpha_t,\beta_t)$ or $(\beta_t,\alpha_t)$. Why does this force a descent? The smaller entry of the later label is at most $a$. If it is strictly smaller than $a$, then the later label is lexicographically smaller than $(a,b)$. If it is equal to $a$, then the other entry is at most $b$, so the later label is at most $(a,b)$. In either case, the later label is at most $(a,b)$, and hence is strictly smaller than the first label $(c,d)$. Thus postponing the merger of the two blocks that realize the smallest available label forces a smaller label to appear later in the same maximal chain. This gives a descent, so an increasing maximal chain must take the smallest available merger first. [/guided] [/step] [step:Deduce uniqueness of the increasing maximal chain in each interval] Starting at $\sigma$, the previous step forces the first edge of any increasing maximal chain in $[\sigma,\tau]$ to be the cover with the lexicographically smallest available label. After taking that cover, the same argument applies to the smaller interval from the new partition to $\tau$. Repeating this finite induction over the rank difference between $\sigma$ and $\tau$, every increasing maximal chain must take exactly the same sequence of covers. This forced chain is precisely the chain constructed earlier: at each stage it merges, among all still unmerged pairs inside the same target block of $\tau$, the pair whose block minima give the lexicographically smallest available label. Hence the increasing maximal chain in $[\sigma,\tau]$ exists and is unique. [/step] [step:Verify that the unique increasing chain is lexicographically first] Let \begin{align*} \sigma=\pi_0 \lessdot \pi_1 \lessdot \cdots \lessdot \pi_m=\tau \end{align*} be the increasing chain constructed above, and let \begin{align*} \sigma=\rho_0 \lessdot \rho_1 \lessdot \cdots \lessdot \rho_m=\tau \end{align*} be any other maximal chain in $[\sigma,\tau]$. If the two chains are equal, there is nothing to prove. Otherwise, let $q \in \{0,\dots,m-1\}$ be the first index such that $\pi_q=\rho_q$ but $\pi_{q+1}\neq \rho_{q+1}$. At the common partition $\pi_q=\rho_q$, the constructed chain uses the lexicographically smallest available label. Therefore \begin{align*} \lambda(\pi_q,\pi_{q+1}) <_{\mathrm{lex}} \lambda(\rho_q,\rho_{q+1}). \end{align*} The two maximal chains have identical label sequences before index $q$, and the constructed chain has a strictly smaller label at index $q$. Hence its label word is lexicographically smaller than the label word of every other maximal chain in the interval. [/step] [step:Apply the EL-shellability theorem] The preceding steps show that, in every interval $[\sigma,\tau] \subseteq \Pi_n$, there is a unique maximal chain whose label sequence is increasing, and this chain is lexicographically first among all maximal chains in that interval. Therefore $\lambda$ is an EL-labelling of $\Pi_n$. The poset $\Pi_n$ is finite because $[n]$ has only finitely many set partitions, and it is bounded with bottom element the discrete partition and top element the indiscrete partition. By the EL-shellability theorem (citing a result not yet in the wiki: every bounded finite poset admitting an EL-labelling has shellable order complex of its proper part), the order complex of \begin{align*} \Pi_n \setminus \{\hat{0},\hat{1}\} \end{align*} is shellable. This proves both assertions. [/step]