Polyhedral Subdivisions and Projections of Polytopes Jörg Rambau Dissertation (Advisor: Günter M. Ziegler, TU Berlin)

   
Higher Bruhat Orders

In this section we recall the basic definitions and theorems in the framework of higher Bruhat orders and answer a question by ZIEGLER [74]. Let $\mathcal{L}$ be a linearly ordered finite set. The reader may consider $\mathcal{L}$ as the set $[n]$, without loss of generality.

Definition 3.7.1   (MANIN & SCHECHTMAN [48], ZIEGLER [74])

• For some $(k+1)$-subset $P := (p_1, \dots , p_{k+1})$ of $\mathcal{L}$, the set of its $k$-subsets
  
  $$\mathcal{P} = \tbinom{P}{k} = \setof{P \sm p_{\nu}}{\nu = 1, \dots , k+1}$$
  
  
  is a   $k$-packet of $\mathcal{L}$. It is naturally ordered by $P \sm p_{\nu} < P \sm p_{\mu} \iff \mu < \nu$, the   lexicographic order.
• An ordering $\alpha$ of $\tbinom{\mathcal{L}}{k}$ is   admissible if the elements of any $(k+1)$-packet appear in lexicographic or in reverse-lexicographic order. Two orderings $\alpha$ and $\alpha '$ are   equivalent if they differ by a sequence of interchanges of two neighbors that do not lie in a common packet.
• The   inversion set $\inv (\alpha )$ of an admissible ordering $\alpha$ is the set of all $(k+1)$-subsets of $\mathcal{L}$ whose $k$-subsets appear in reverse-lexicographic order in $\alpha$.
• A set $U$ of $(k+1)$-subsets of $\mathcal{L}$ is   consistent if its intersection with any $(k+1)$-packet $\mathcal{P}$ of $\mathcal{L}$ is a beginning or an ending segment of $\mathcal{P}$ with respect to the lexicographic order on $\mathcal{P}$.
• The set of all equivalence classes of admissible orders of $\tbinom{\mathcal{L}}{k}$, partially ordered by single-step-inclusion of inversion sets. That is, $[\alpha ] \le [\alpha ']$ if and only if
  
  $$\inv (\alpha ) = U_1 \subset U_2 \subset \dots \subset U_K = \inv(\alpha ')$$
  
  
  with $\char93 U_{\nu} \sm U_{\nu - 1} = 1$ and all $U_{\nu}$ are admissible -- is the   higher Bruhat order $\mathcal{B}(\mathcal{L},k)$, where $\mathcal{B}(n,k)$ denotes $\mathcal{B}([n],k)$.
• For an inversion set $U \in \mathcal{B}(\mathcal{L},k)$, define  
  
  $$\partial U := \bigsetof{I \in \tbinom{\mathcal{L}}{k+2}}{I \sm i_1 \notin U, I \sm i_{k+2} \in U}.$$
  
  

The structure of $\mathcal{B}(\mathcal{L},k)$ does of course only depend on the cardinality of  $\mathcal{L}$, but the general setting leads to some advantages in the notation of functorial constructions. For simplicity, however, we switch now to $\mathcal{B}(n,k)$.

Theorem 3.7.2   (MANIN & SCHECHTMAN [48], ZIEGLER [74]) The higher Bruhat order $\mathcal{B}(n,k)$ is a ranked poset with rank function $r(U) = \char93 U$. Moreover, it has a unique minimal element  $\Hat{0}_{n,k} = \emptyset$ and a unique maximal element  $\Hat{1}_{n,k} = \tbinom{[n]}{k+1}$.

The following Theorem gives a more geometric insight into the structure of higher Bruhat orders.

Theorem 3.7.3   (ZIEGLER [74]) The higher Bruhat order $\mathcal{B}(n,k)$ is isomorphic to

1.

the set of all consistent sets $U$ of $(k+1)$-subsets of $[n]$ with single-step-inclusion-order,

2.

the set of (equivalence classes of) extensions of the cyclic hyperplane arrangement $X^{n,n-k-1}$ by a new pseudo-hyperplane in general position, partially ordered by single-step-inclusion of the sets of vertices on ``the negative side,''

3.

the set of maximal chains of inversion sets in $\mathcal{B}(n,k-1)$ -- corresponding to orders of $k$-sets -- modulo equivalence of admissible orders.

The following notations for deletion and contraction in $\mathcal{B}(n,k)$ provide intuition via the corresponding notions in $X^{n,n-k-1}$.

Definition 3.7.4   For $U \in \mathcal{B}(n,k)$, define     $$\begin{align*}U/n &:= \setof{I \sm n}{n \in I, I \in U}, \tag*{\text{(contracti... ...U \sm n &:= \setof{I \in U}{n \notin I}. \tag*{\text{(deletion)}} \end{align*}$$

In order to construct inversion sets in $\mathcal{B}(n+1,k+1)$ from inversion sets in $\mathcal{B}(n,k)$ and in $\mathcal{B}(n,k+1)$, the following Theorem is useful.

Theorem 3.7.5   (ZIEGLER [74]) Let $U$ be an inversion set in $\mathcal{B}(n,k)$, and let $V$ be an inversion set in $\mathcal{B}(n,k+1)$. Then $U' := V \cup U * (n+1)$ is consistent if and only if

$$\partial U \subseteq V \quad \text{and} \quad \partial \complement U \subseteq \complement V.\tag*{\qed}$$

Corollary 3.7.6   The following maps from $\mathcal{B}(n,k)$ to $\mathcal{B}(n+1,k+1)$ are injective:     $$\begin{align*}U \mapsto \widetilde{U} &:= U * (n+1) \cup \partial U, \tag*{\tex... ...gsetof{I \in \tbinom{[n]}{k+2}}{I \sm i_{k+2} \in U}. \tag*{\qed} \end{align*}$$

The extension is not order-preserving in general. But the following definition yields a canonical single-step-inclusion order for the expansion of $U$ from an arbitrary single-step-inclusion order of $U$.

Definition 3.7.7   For some $U \in \mathcal{B}(n,k)$ with a given single-step-inclusion-order $\Omega (U) = (\Omega (U'), I)$, define the following order  $\Hat{\Omega}$: For $n = k + 1$, start with

$$\Hat{\Omega}\bigl(\{[n]\}\sphat\,\bigr) := \left([n+1]\right)$$

corresponding to $\Omega (\{[n]\}) = ([n])$ in $\mathcal{B}(n,k)$. If $n > k + 1$ and $\Hat{\Omega}(\Hat{U'})$ is already constructed then define

$$\Hat{\Omega}(\Hat{U}) := \left( \Hat{\Omega}(\Hat{U'}), \... ...cup \{n+1\}, \Hat{\Omega}(\delta I \sm \partial I) \right),$$

where the orders on $\partial I$ and $\delta I \sm \partial I$ are given by restriction of $\Hat{\Omega}\bigl((U \sm n)\sphat\,\bigr)$.

Proposition 3.7.8   For all  $U \in \mathcal{B}(n,k)$ and all single-step-inclusion orders $\Omega$ of $U$, the order $\Hat{\Omega}$ is a single-step-inclusion order of the expansion $\Hat{U}$ of $U$ in $\mathcal{B}(n+1,k)$.

Proof:The following properties make sure that no cycles are produced:

$$\begin{align*}\delta (U) \sm n &= \delta (U \sm n),\\ \partial (U) \sm n &= \partial (U \sm n). \end{align*}$$ At each single-step-inclusion step all packets in $\mathcal{B}(n,k+1)$ are consistent by induction. From the remaining packets only those containing  $I \cup \{n+1\}$ are involved.

If $n \notin I$ then the order increases just by $I \cup \{n\}$ which is consistent because $\Omega$ is a single-step-inclusion order of $U$ and $\Hat{U'}$ is already ordered consistently.

Let $n$ be in $I$. For all packets  $\mathcal{P}$ containing  $I \cup \{n+1\}$, either $\mathcal{P} / n+1$ is completely contained in $U$ or only $I$ meets $U$. In the first case the only element $P \sm a'$ of $\mathcal{P} \sm n+1$ comes before $I \cup \{n+1\}$ in  $\Hat{\Omega}$, in the second case $I \cup \{n+1\}$ is positioned after $P \sm n+1$ in  $\Hat{\Omega}$; both cases lead to consistent orders on  $\mathcal{P}$.

From this we derive the promised result.

Theorem 3.7.9   The expansion

$$\Hat{\cdot}: \left\{ \begin{array}{rcl} \mathcal{B}(n,k) ... ...{B}(n+1,k+1),\\ U & \mapsto & \Hat{U}, \end{array} \right.$$

is an order-preserving embedding that maps $\widehat{0}_{n,k}$ to $\widehat{0}_{n+1,k+1}$ and $\widehat{1}_{n,k}$ to $\widehat{1}_{n+1,k+1}$.