text:
# Maps between higher Bruhat orders and higher Stasheff-Tamari posets

## 1. Introduction

The higher Bruhat orders $`B(n,d)`$ were introduced by Manin and Schechtman \[MS\] in connection to discriminental hyperplane arrangements. They give a combinatorial definition of $`B(n,d)`$ which we shall review in the next section. The choice of name stems from the fact that $`B(n,1)`$ is isomorphic to weak Bruhat order on the symmetric group.

Shortly following the definition of the higher Bruhat orders, Kapranov and Voevodsky wrote a paper \[KV\] which presented two alternative interpretations for the higher Bruhat orders, in terms of oriented matroids, and in terms of convex geometry. The oriented matroid approach was later taken up by Ziegler \[Zi\]. The convex geometric approach has not been significantly written about since. It is the focus of the first part of our paper.

The convex-geometric approach to the higher Bruhat orders is as follows. Consider the $`n`$-cube $`[1,1]^n`$. Let $`B(n,0)`$ denote the set of vertices of the cube, with the usual Cartesian product order, so that $`B(n,0)`$ is a Boolean lattice. Its minimum element is $`(1,\mathrm{},1)`$, and its maximum element is $`(1,\mathrm{},1)`$. Now let $`B(n,1)`$ be the set of increasing paths along edges of the cube from $`(1,\mathrm{},1)`$ to $`(1,\mathrm{},1)`$. There are $`n!`$ of these, and they are naturally in bijection with $`S_n`$. We put an order on this set by defining covering relations: $`\sigma \tau `$ if $`\sigma `$ and $`\tau `$ coincide except on the boundary of some 2-face, where $`\sigma `$ uses the top two edges of the face, and $`\tau `$ uses the bottom two edges. (We will be more explicit about how to understand “bottom” and “top” in the next section.) Under this order, the poset $`B(n,1)`$ is isomorphic to weak Bruhat order on the symmetric group.

Now consider collections of 2-faces of the cube which form a homotopy from the minimum path to the maximum path, and which are non-backtracking. (This non-backtracking condition generalizes the “increasing” condition in the dimension 1 case. We shall give more precise definitions in the next section.) These homotopies form the elements of $`B(n,2)`$. As before, the order on $`B(n,2)`$ is defined by specifying covering relations: $`\sigma \tau `$ if $`\sigma `$ and $`\tau `$ coincide except on the boundary of a 3-face, where $`\sigma `$ uses the top three facets, and $`\tau `$ uses the bottom three facets. The other $`B(n,d)`$ are defined similarly. The first goal of this paper is to write down this description explicitly, and to show that it is equivalent to the combinatorial definition of \[MS\].

In order to describe the second goal of the paper, we must now turn to the higher Stasheff-Tamari posets. In fact, there are two different Stasheff-Tamari posets structures $`S_1(n,d)`$ and $`S_2(n,d)`$ defined on the same set of objects $`S(n,d)`$. We shall only be interested in the first of these posets, so we shall suppress the subscript. $`S(n,d)`$ is usually viewed as the set of triangulations of the cyclic polytope $`C(n,d)`$. We will give an equivalent definition, analogous to the one above for higher Bruhat orders where the cube has been replaced by a simplex.

In order to define $`S(n,d)`$, start with an $`n1`$-simplex, with vertices labelled from $`1`$ to $`n`$. $`S(n,0)`$ is the set of vertices, with the order given by the labelling. The objects of $`S(n,1)`$ are the increasing paths from the bottom vertex to the top vertex. The order is by reverse refinement: the bottom path is the path that includes every vertex, and the top path is the one that uses only $`1`$ and $`n`$. The objects of $`S(n,2)`$ are the sets of 2-faces of the simplex which form a non-backtracking homotopy from the bottom path to the top path. The order on $`S(n,2)`$ is defined by specifying covering relations: $`ST`$ if $`S`$ and $`T`$ coincide except on the boundary of a 3-simplex, where $`S`$ contains the upper faces and $`T`$ the lower faces. The higher $`S(n,d)`$ are defined similarly.

In \[KV\], a map called $`f`$ from $`B(n,d)`$ to $`S([0,n+1],d+1)`$ was described as follows. (We write $`S([0,n+1],d+1)`$ to indicate that the vertices are labelled by the numbers from 0 to $`n+1`$.) There is a poset isomorphism from vertices of the $`n`$-cube (i.e. $`B(n,0)`$) to elements of $`S([0,n+1],1)`$: namely, the coordinates of the vertex which are negative tell you which vertices belong in the path in addition to $`0`$ and $`n+1`$. Now, an element of $`B(n,1)`$, which is a path through the $`n`$-cube, determines a sequence of vertices of the cube. We apply the map from $`B(n,0)`$ to $`S([0,n+1],1)`$ to each vertex in succession, to get a sequence of paths through the $`n+1`$-simplex. Two successive paths differ in that one vertex which is present in the first path is not present in the second. To each pair of successive paths, we associate the triangle whose vertices are the removed vertex and its two neighbours along the path. These triangles form a homotopy from the bottom path (which contains all the vertices) to the top path (which contains only the end-points), and hence define an element of $`S([0,n+1],2)`$. In the example below, the bold path through the cube on the left gives rise to the triangulation shown on the right.

It is claimed in \[KV\] that one can define a similar map $`f:B(n,d)S([0,n+1],d+1)`$ for all $`d`$, and further that this map is surjective for all $`d`$. Rambau \[Ra1\] constructed an explicit map from $`B(n,d)`$ to $`S([0,n+1],d+1)`$, but he did not show that it coincided with the map described in \[KV\]. In the second part of the paper, we prove that the map described in \[KV\] does indeed coincide with that defined in \[Ra1\], and that it is surjective for $`d2`$.

In the second part of the paper, we also give geometric interpretations of two maps associated to $`f`$. For $`SS([0,n+1],d+1)`$, $`\mathrm{lk}_0(S)`$ is the link of $`S`$ at zero, which can be viewed in a natural way as lying in $`S(n+1,d)`$. We can also take $`\mathrm{lk}_{\{0,n+1\}}(S)`$; this lies in $`S(n,d1)`$. We show that, for $`\pi B(n,d)`$, $`\mathrm{lk}_{\{0,n+1\}}(f(\pi ))`$ coincides with the vertex figure of $`\pi `$ at $`(1,\mathrm{},1)[1,1]^n`$. We also give a similar interpretation for $`\mathrm{lk}_0(f(\pi ))`$.

The third part of our paper consists of the construction of a map $`g:S(n,d)B(n1,d)`$. As already explained, $`S(n,0)`$ is a chain of $`n`$ elements which we view as the vertices of an $`n1`$-simplex. We map vertex $`a`$ to the corner of $`[1,1]^{n1}`$ whose final $`a1`$ coordinates are +1, and the others -1. An element of $`S(n,1)`$ is mapped to an increasing path through the $`n1`$-cube which passes through the vertices corresponding to the vertices on the path through the $`n1`$-simplex. For $`SS(n,2)`$, $`g(S)`$ is defined as the unique homotopy from the minimal path through the cube to the maximal path through the cube which passes through all the paths corresponding to paths through the $`n1`$-simplex along edges in $`S`$. An analogous statement holds for $`d>2`$.

We give several equivalent definitions for $`g`$, including two which are explicit and non-inductive. We also show that the map $`g`$ is a poset embedding, and we give an explicit criterion to determine if an element of $`B(n1,d)`$ is in the image of $`g`$. This amounts to giving a new equivalent definition of $`S(n,d)`$ without reference to convex geometry.

## 2. Higher Bruhat orders

We begin by recalling the definition of the higher Bruhat order $`B(n,d)`$ for $`dn`$ positive integers, given by Manin and Schechtman \[MS\]. We write $`\left(\genfrac{}{}{0pt}{}{[n]}{d}\right)`$ for the set of subsets of $`[n]`$ of size $`d`$. A $`d`$-packet consists of the subsets of size $`d`$ of a set of $`d+1`$ integers. A total order on $`\left(\genfrac{}{}{0pt}{}{[n]}{d}\right)`$ is admissible if every $`d`$-packet occurs in either lexicographic order or its reverse. The set of admissible orders on $`\left(\genfrac{}{}{0pt}{}{[n]}{d}\right)`$ is called $`A(n,d)`$.

Two admissible orders are said to be equivalent if they differ by a sequence of transpositions of adjacent elements not both lying simultaneously in any $`d`$-packet. If $`\pi `$ is an admissible order, we write $`[\pi ]`$ for its equivalence class.

$`B(n,d)`$ is a poset whose elements are the equivalence classes of admissible orders on $`\left(\genfrac{}{}{0pt}{}{[n]}{d}\right)`$. The order is given by specifying covering relations. Let $`\pi A(n,d)`$. Suppose there is some $`d`$-packet which occurs consecutively in $`\pi `$, and in lexicographic order. Let $`\sigma `$ denote the (automatically admissible) order obtained by reversing this $`d`$-packet. Then $`[\pi ][\sigma ]`$ in $`B(n,d)`$. The order on $`B(n,d)`$ is the transitive closure of these covering relations.

There are two orders on $`\left(\genfrac{}{}{0pt}{}{[n]}{d}\right)`$ which are clearly admissible. Let $`\widehat{0}_d`$, $`\widehat{1}_d`$ denote the class in $`B(n,d)`$ of the lexicographic order and its reverse respectively. It is clear that these elements are minimal and maximal respectively in $`B(n,d)`$; in fact, they are its minimum and maximum elements, see \[MS\].

There is a map $`I:A(n,d)𝒫(\left(\genfrac{}{}{0pt}{}{[n]}{d+1}\right))`$ which associates to any $`\pi A(n,d)`$ the set of $`d`$-packets which occur in reverse order. $`I(\pi )`$ is called the inversion set of $`\pi `$. This generalizes the usual notion of inversion set for a permutation. It is clear that $`I`$ is constant on equivalence classes, and so passes to $`B(n,d)`$. As a map from $`B(n,d)`$, $`I`$ is injective.

A subset of $`\left(\genfrac{}{}{0pt}{}{[n]}{d+1}\right)`$ is said to be consistent if its restriction to any $`(d+1)`$-packet consists of either an initial or a final subset with respect to lex order. Ziegler showed in \[Zi\] that a subset of $`\left(\genfrac{}{}{0pt}{}{[n]}{d+1}\right)`$ is in the image of $`I`$ iff it is consistent.

It will be convenient to define $`B(n,0)`$ to be the set of subsets of $`[n]`$, ordered by inclusion. The inversion set of an element of $`B(n,0)`$ is just the set itself. $`\widehat{1}_0=[n]`$; $`\widehat{0}_0=\mathrm{}`$.

We now give the convex-geometric definition of the higher Bruhat orders, formalizing ideas from \[KV\]. $`[1,1]^n`$ will be our standard $`n`$-cube. We shall keep track of its faces as maps from $`[n]`$ to the set $`\{1,,1\}`$, where a $`d`$-face will have $``$ occurring in $`d`$ places, these being the dimensions in which the face extends. We will sometimes refer to a set of faces of the cube when what we mean is the union of the set of faces.

For $`G`$ a set, let $`\mathrm{\Xi }_G(x)=1`$ if $`xG`$ and $`1`$ otherwise. For $`X=\{a_1,\mathrm{},a_d\}_<[n]`$, $`yX`$, define:

$$p(y,X)=\{\begin{array}{cc}1& y<a_1\\ (1)^i& a_i<y<a_{i+1}\\ (1)^d& a_d<y\end{array}$$

Fix $`\alpha B(n,d)`$. For each $`X\left(\genfrac{}{}{0pt}{}{[n]}{d}\right)`$, let

$$F_X^\alpha (i)=\{\begin{array}{cc}& iX\\ p(i,X)\mathrm{\Xi }_{I(\alpha )}(X\{i\})& iX\end{array}$$

Let $`K(\alpha )`$ consist of the $`F_X^\alpha `$ for all $`X`$.

We identify linear maps from $`^n`$ to $`^d`$ with $`d\times n`$ matrices. We say that a map $`T:^n^d`$ is totally positive if the determinants of all its minors are positive. (Note that there are many totally positive matrices, for example, a Vandermonde matrix $`T_{ij}=c_j^i`$ with $`0<c_1<\mathrm{}<c_n`$. The determinant of any minor of this matrix equals a Vandermonde determinant times a Schur function, both of which are positive.)

We say that a collection of convex sets tiles a region if the region is the union of the convex sets and the sets overlap only on boundaries.

The main theorem of this section is the following:

###### Theorem 2.1

For any $`\alpha B(n,d)`$, the set $`K(\alpha )`$ of $`d`$-faces of the standard $`n`$-cube is homeomorphic to a disk, has boundary $`K(\widehat{0}_{d1})K(\widehat{1}_{d1})`$, and the image of the $`K(\alpha )`$ under any totally positive map $`T`$ from $`^n`$ to $`^d`$ forms a tiling of the image of the standard $`n`$-cube under $`T`$.

Conversely, given a set $`K`$ of $`d`$-faces of the standard $`n`$-cube, such that the images under some totally positive map $`T`$ of the faces in $`K`$ tile the image of the standard $`n`$-cube, it follows that $`K=K(\alpha )`$ for some $`\alpha B(n,d)`$.

###### Demonstration Proof

Given a convex polytope in $`^d`$, we say that a facet is an upper facet if the polytope lies below it with respect to the final co-ordinate, and similarly for lower facets. A facet parallel to $`e_d`$ is neither upper nor lower, but the cases in which we shall be interested will exclude that possibility, so that every facet is either upper or lower. We now prove a simple lemma about upper and lower facets of images of cubes:

###### Lemma 2.1

Let $`W`$ be a totally positive map from $`^d`$ to $`^d`$. The upper facets of the image under $`W`$ of $`[1,1]^d`$ are the $`T_i`$ defined by

$$T_i(j)=\{\begin{array}{cc}& ji\\ (1)^{d+j}& j=i\end{array},$$

while the lower facets are the $`L_i`$ defined by

$$L_i(j)=\{\begin{array}{cc}& ji\\ (1)^{d+j+1}& j=i\end{array}.$$

###### Demonstration Proof

Since $`W`$ is totally positive, its inverse satisfies $`\mathrm{sign}((W^1)_{ij})=(1)^{i+j}`$. Thus, the inverse image under $`W`$ of $`(0,0,\mathrm{},0,1)`$ will be alternating in sign, with its last entry positive, and the desired result follows.

Observe that if $`T`$ is a totally positive map from $`^n`$ to $`^d`$, then the restriction of $`T`$ to any $`d`$-dimensional co-ordinate subspace of $`^n`$ is a map to which Lemma 2.1 applies. Thus, Lemma 2.1 tells us about the upper and lower facets of the image under $`T`$ of any $`d`$-dimensional face of $`[1,1]^n`$. We shall sometimes speak of the upper or lower facets of a face of $`[1,1]^n`$ when what we mean is facets whose images are upper or lower in the image of the face under any totally positive map.

We now begin to prove the forward direction of the theorem. The proof is by induction on $`d`$. It is clear for $`d=0`$. Assume it holds for all dimensions less than $`d`$.

Let $`\pi A(n,d)`$. Let $`Y_1,\mathrm{},Y_{\left(\genfrac{}{}{0pt}{}{n}{d}\right)}`$ be the elements of $`\left(\genfrac{}{}{0pt}{}{[n]}{d}\right)`$ under the order $`\pi `$. Let $`\mathrm{In}_i(\pi )`$ denote $`\{Y_1,\mathrm{},Y_i\}`$. Observe that for $`0i\left(\genfrac{}{}{0pt}{}{n}{d}\right)`$, $`\mathrm{In}_i(\pi )`$ is consistent. Thus, we may define a sequence $`\alpha _jB(n,d1)`$ by $`I(\alpha _j)=\mathrm{In}_i(\pi )`$. Note that $`\alpha _0=\widehat{0}_{d1}`$; $`\alpha _{\left(\genfrac{}{}{0pt}{}{n}{d}\right)}=\widehat{1}_{d1}`$.

Let $`\mathrm{Pr}`$ denote the map from $`^d`$ to $`^{d1}`$ forgetting the last coordinate. Let $`T^{}=\mathrm{Pr}T`$. Then $`T^{}`$ is totally positive, so by the induction hypothesis, for $`0j\left(\genfrac{}{}{0pt}{}{n}{d}\right)`$, the images under $`T^{}`$ of $`K(\alpha _j)`$ define tilings of $`T^{}([1,1]^n)`$. Let $`\mathrm{\Gamma }_j`$ be the image under $`T`$ of $`K(\alpha _j)`$. Then for each $`xT^{}([1,1]^n)`$, $`\mathrm{\Gamma }_j\mathrm{Pr}^1(x)`$ consists of a single point.

Fix $`0i<\left(\genfrac{}{}{0pt}{}{n}{d}\right)`$. For $`Z\left(\genfrac{}{}{0pt}{}{[n]}{d1}\right)`$, $`F_Z^{\alpha _i}`$ and $`F_Z^{\alpha _{i+1}}`$ are the corresponding faces of $`K(\alpha _i)`$ and $`K(\alpha _{i+1})`$. $`F_Z^{\alpha _i}`$ and $`F_Z^{\alpha _{i+1}}`$ coincide except for $`ZY_{i+1}`$. The $`d`$ faces of each not shared by the other are the $`2d`$ faces of $`F_{Y_{i+1}}^{[\pi ]}`$. So $`\mathrm{\Gamma }_i`$ and $`\mathrm{\Gamma }_{i+1}`$ coincide except that each of them contains $`d`$ of the $`2d`$ faces of $`T(F_{Y_{i+1}}^{[\pi ]})`$. One checks using Lemma 2.1 that $`\mathrm{\Gamma }_i`$ contains the lower faces and $`\mathrm{\Gamma }_{i+1}`$ contains the upper faces.

Thus it follows that if $`i<j`$, for any point $`xT^{}([1,1]^n)`$, the intersection of $`\mathrm{\Gamma }_i`$ with $`\mathrm{Pr}^1(x)`$ lies on or below the intersection of $`\mathrm{\Gamma }_j`$ with $`\mathrm{Pr}^1(x)`$.

Thus, the images of the $`K([\pi ])`$ intersect only on boundaries, since they are separated by the $`\mathrm{\Gamma }_i`$, and they therefore tile the region between the images of $`K(\widehat{0}_{d1})`$ and $`K(\widehat{1}_{d1})`$. Also, since this holds for any $`\pi `$, it follows that the region between the images of $`K(\widehat{0}_{d1})`$ and $`K(\widehat{1}_{d1})`$ is the entire image of $`[1,1]^n`$ under $`T`$, as desired. It also follows from this that the images of the $`K(\widehat{0}_{d1})`$ are exactly the bottom facets of the image under $`T`$ of $`[1,1]^n`$, while the images of the $`K(\widehat{1}_{d1})`$ are its top facets.

Another result of what we have shown so far is that every face in every $`K(\alpha _i)`$ occurs as a facet of either one or two faces in $`K([\pi ])`$: one if the face we are interested in is $`K(\widehat{0}_{d1})`$ or $`K(\widehat{1}_{d1})`$ and two otherwise. This allows us to conclude that $`T`$ restricted to $`K([\pi ])`$ is a homeomorphism to the image of $`[1,1]^n`$, which is clearly (homeomorphic to) a disk.

We now turn to the converse direction of the theorem. The proof is again by induction on $`d`$. Again, it is obvious for $`d=0`$, so we assume $`d>0`$, and that the converse holds for dimension $`d1`$.

Fix $`K`$ a set of $`d`$-faces of the standard $`n`$-cube, as in the statement of the theorem. We will now define a sequence $`\alpha _0,\mathrm{},\alpha _{\left(\genfrac{}{}{0pt}{}{n}{d}\right)}`$ of elements of $`B(n,d1)`$ such that any face in $`K(\alpha _i)`$ for any $`i`$ occurs as a facet of some face in $`K`$.

Let $`\alpha _0=\widehat{0}_{d1}`$. Inductively, given $`\alpha _i`$, for $`i<\left(\genfrac{}{}{0pt}{}{n}{d}\right)`$, we will define $`\alpha _{i+1}`$ as follows. Let $`\mathrm{\Gamma }_i`$ be the image of $`K(\alpha _i)`$ under $`T`$. $`\mathrm{\Gamma }_i`$ divides the faces of $`K`$ into those whose images are above $`\mathrm{\Gamma }_i`$ and those below it. I claim that there exists some $`d`$-face in $`K`$ all of whose lower facets are in $`K(\alpha _i)`$. We will pick one such, and call it $`Y_{i+1}`$. To find such a $`Y_{i+1}`$, pick any $`XK`$ which lies above $`\mathrm{\Gamma }_i`$. If $`X`$ has some lower facet not in $`K(\alpha _i)`$, replace $`X`$ by the face in $`K`$ which contains this lower facet of $`X`$ as an upper facet. This new face still has its image under $`T`$ lying above $`\mathrm{\Gamma }_i`$, but its topmost point is lower than that of the old face. Thus, this process cannot loop back on itself, but must terminate, and it must terminate in a face $`Y_{i+1}`$ which has all its lower facets in $`K(\alpha _i)`$. (A similar statement for cyclic polytopes is proved in \[Ra1\].)

Now, let $`J`$ denote $`K(\alpha _i)`$ with the lower facets of $`Y`$ replaced by its upper facets. It is clear that $`J`$ satisfies the conditions of the theorem, and thus that, by induction, we can define $`\alpha _{i+1}`$ by saying that $`K(\alpha _{i+1})=J`$. We check that $`I(\alpha _{i+1})=I(\alpha _i)\{Y_{i+1}\}`$.

Now let $`\pi `$ denote the order on $`\left(\genfrac{}{}{0pt}{}{[n]}{d}\right)`$ given by $`Y_1,\mathrm{},Y_{\left(\genfrac{}{}{0pt}{}{n}{d}\right)}`$. Since $`\mathrm{In}_i(\pi )=I(\alpha _i)`$, and the $`I(\alpha _i)`$ are all consistent, it follows that $`\pi `$ is an admissible order.

Finally, we observe that $`K([\pi ])=K`$ because both $`K`$ and $`K([\pi ])`$ can be characterized as the set of faces between $`\alpha _i`$ and $`\alpha _{i+1}`$ for some $`i`$. This completes the proof of Theorem 2.1.

We have shown that the elements of $`B(n,d)`$ can be represented as sets of $`d`$-faces of the standard $`n`$-cube. To describe the order relation on $`B(n,d)`$ in terms of this description, we have the following proposition:

###### Proposition 2.1

For $`\sigma ,\tau B(n,d)`$, $`\sigma \tau `$ iff $`K(\sigma )`$ and $`K(\tau )`$ coincide except on the facets of a $`d+1`$-cube, where $`K(\sigma )`$ contains the upper facets and $`K(\tau )`$ contains the lower facets.

###### Demonstration Proof

Suppose that $`\sigma \tau `$. So $`I(\sigma )=I(\tau )\{Y\}`$. Choose an admissible order $`\pi `$ on $`\left(\genfrac{}{}{0pt}{}{[n]}{d+1}\right)`$ so that $`I(\tau )`$ preceds $`Y`$ precedes the rest of $`\left(\genfrac{}{}{0pt}{}{[n]}{d+1}\right)`$. Now, as in the proof of Theorem 2.1, we see that $`\sigma `$ and $`\tau `$ differ only on the boundary of $`F_Y^{[\pi ]}`$: $`\sigma `$ contains its upper facets, and $`\tau `$ its lower facets, as desired.

To prove the converse, observe that since $`K(\sigma )`$ and $`K(\tau )`$ coincide outside the boundary of a $`d+1`$-face, say $`Y`$, $`I(\sigma )`$ and $`I(\tau )`$ must coincide except as regards containment of $`Y`$, and the desired result follows.

## 3. The higher Stasheff-Tamari posets

As explained in the introduction, the usual way of thinking of the higher Stasheff-Tamari posets $`S(n,d)`$ is as a poset on the set of triangulations of a cyclic polytope. To motivate the existence of a connection to the higher Bruhat orders, a different definition, one analogous to the convex-geometric definition of $`B(n,d)`$ given above, will be more relevant. To avoid confusion, we shall give the poset we define in this manner a new name, $`T(n,d)`$, and then prove that $`T(n,d)`$ coincides with $`S(n,d)`$.

The standard $`n1`$-simplex, $`\mathrm{\Delta }_{n1}`$, is the convex hull of the basis vectors in $`^n`$. Its $`d`$-faces are indexed by $`d+1`$-subsets of $`[n]`$, which designate which vertices lie on the face.

If $`W:^n^d`$, let $`\overline{W}`$ be the linear map from $`^n`$ to $`^{d+1}`$ defined by setting $`\overline{W}(e_i)=(1,W(e_i))`$. In terms of matrices, we can say that the matrix for $`\overline{W}`$ is obtained from that for $`W`$ by adding a first row of all ones. We say that $`W`$ is affinely positive if $`\overline{W}`$ is totally positive.

We now prove a lemma analogous to Lemma 2.1, but concerning simplices, not cubes.

###### Lemma 3.1

Let $`W`$ be an affinely positive map from $`^{d+1}`$ to $`^d`$. The top facets of the image of $`\mathrm{\Delta }_d`$ are those which omit a vertex with the same parity as $`d`$; the bottom facets are those which omit a vertex of opposite parity to $`d`$.

###### Demonstration Proof

Consider the totally positive map $`\overline{W}:^{d+1}^{d+1}`$. Let $`x=\overline{W}^1(e_{d+1})`$. Then $`x`$ is parallel to the affine span of $`\mathrm{\Delta }_{n1}`$, and, as in the proof of Lemma 2.1, we are interested in whether $`x`$ points into or out of each facet of $`\mathrm{\Delta }_{n1}`$. This is equivalent to asking whether $`x`$ points into or out of the corresponding facet of the cone over $`\mathrm{\Delta }_{n1}`$ with cone point the origin, and now we use the fact that, as in Lemma 2.1, $`x`$ alternates in sign.

Since this does not depend on the choice of $`W`$, this allows us to refer to “upper” or “lower” facets of a face of $`\mathrm{\Delta }_{n1}`$, meaning facets whose images are upper or lower in the image of the face under any affinely positive map.

We can now define $`T(n,d)`$.

###### Definition of $T(n,d)$

An element $`S`$ of $`T(n,d)`$ is a set of $`d`$-faces of $`\mathrm{\Delta }_{n1}`$, with the property that under some affinely positive map $`W`$, the images under $`W`$ of the faces in $`S`$ tile $`W(\mathrm{\Delta }_{n1})`$. The order on $`T(n,d)`$ is defined by giving covering relations: $`ST`$ iff $`S`$ and $`T`$ coincide except on the boundary of a $`d+1`$-simplex, where $`S`$ contains the upper facets of the simplex and $`T`$ contains the lower facets.

###### Proposition 3.1

If $`ST(n,d)`$ then for any affinely positive map $`V`$, the images under $`V`$ of the faces in $`S`$ form a tiling of $`V(\mathrm{\Delta }_{n1})`$.

###### Demonstration Proof

First, we show how much information we need about a set of points to be able to determine when a collection of simplices forms a tiling.

###### Lemma 3.2

Given $`n`$ points in $`^d`$ no $`d+1`$ of which lie on any affine hyperplane:

(i) The boundary facets of the convex hull of the set of vertices are the $`d`$-sets of vertices having the property that all the other vertices lie on the same side of their affine span.

(ii) A collection of $`d+1`$-sets of vertices (“simplices”) forms a tiling iff every facet of every simplex is either a boundary facet of the convex hull and appears as a facet of exactly one simplex, or else appears as a facet of exactly two simplices, and the vertices of these two simplices not on the shared facet lie on opposite sides of the affine span of the shared facet.

###### Demonstration Proof

Part (i) is obvious. To establish part (ii), let $`P`$ be the convex hull of the points. Let $`S`$ be a set of simplices. If $`S`$ is a tiling, it is clear that it has the above properties. Now, we assume it has the above properties, and we wish to show that $`S`$ forms a tiling.

Pick an arbitrary direction vector $`v`$. Now, pick a line with direction vector $`v`$ which passes through $`P`$, and does not intersect any simplex in $`S`$ in a face of codimension more than $`1`$. We say that a point on the line is bad if it neither lies on the boundary of a simplex in $`S`$, nor lies in exactly one simplex of $`S`$. Let $`x`$ be the point furthest along the line in the closure of the set of bad points.

First, consider the case where $`x`$ is in the interior of $`P`$. Since the points just beyond $`x`$ are good, they lie in exactly one simplex, say $`A`$, of $`S`$, and clearly $`x`$ lies on the boundary of $`A`$. The facet of $`A`$ containing $`x`$ lies in exactly one other simplex of $`S`$, say $`B`$. Since the vertex of $`B`$ not lying on the facet containing $`x`$ lies on the opposite side from $`A`$, the points immediately before $`x`$ lie in $`B`$. This shows that the vertices just before $`x`$ lie in at least one simplex of $`S`$. Suppose they lie in another one as well, say $`C`$. Then $`x`$ must lie on the boundary of $`C`$, and, as before, the points just past $`x`$ must lie in another simplex, say $`D`$. But since the points just past $`x`$ were assumed to be good, this is impossible. The case where $`x`$ is on the boundary of $`P`$ is similar.

We have now showed that the points not on any boundary face of a simplex of $`S`$, lying on a line in direction $`v`$ which doesn’t intersect any faces of $`S`$ in codimension more than 1, all lie in exactly one simplex of $`S`$. But this set is dense in $`P`$, so the simplices of $`S`$ form a tiling, as desired. This completes the proof of Lemma 3.2.

Proposition 3.1 will now follow from Lemma 3.2 and the following lemma:

###### Lemma 3.3

Let $`V`$ be an affinely positive map from $`^n`$ to $`^d`$. Let $`x_i=V(e_i)`$. Then no $`d+1`$ of the $`x_i`$ lie on a common affine hyperplane, and for any $`a_1,\mathrm{},a_{d+1},i,j`$ distinct integers in $`[n]`$, whether or not $`x_i`$ and $`x_j`$ lie on opposite sides of the affine hyperplane spanned by $`x_{a_1},\mathrm{},x_{a_{d+1}}`$ does not depend on $`V`$.

###### Demonstration Proof

We begin with a lemma:

###### Lemma 3.4

Let $`T`$ be a totally positive map from $`^n`$ to $`^{d+1}`$. Let $`x`$ be a non-zero vector in $`\mathrm{ker}(T)`$. Then $`x`$ has at least $`d+2`$ non-zero components. For any set of $`d+2`$ components, there is an $`x\mathrm{ker}(T)`$ with exactly those components non-zero. If $`x\mathrm{ker}(T)`$ has exactly $`d+2`$ non-zero components, then its non-zero components alternate in sign.

###### Demonstration Proof

Since $`T`$ is totally positive, its restriction to any co-ordinate subspace of dimension $`d+1`$ is non-singular, so no non-zero element of any of these subspaces could be in the kernel of $`T`$. Thus $`x\mathrm{ker}(T)`$ implies that $`x`$ has at least $`d+2`$ non-zero components.

The restriction of $`T`$ to any co-ordinate subspace of dimension $`d+2`$ must have a non-zero kernel, but if $`x`$ is a non-zero element of the kernel, by what we have already shown, it must have all $`d+2`$ components non-zero. This shows that for any choice of $`d+2`$ components, there is an element of the kernel of $`T`$ with exactly those componenets non-zero.

Assume $`x`$ has exactly $`d+2`$ non-zero components: $`x=_{i=1}^{d+2}c_ie_{a_i}`$ with $`a_1<\mathrm{}<a_{d+2}`$. Let $`S`$ be the restriction of $`T`$ to the span of the $`e_{a_i}`$ for $`1id+1`$. Let $`y=c_{d+2}T(e_{a_{d+2}})`$. Then $`S^1(y)=_{i=1}^{d+1}c_ie_{a_i}`$. Computing $`S^1(y)`$, we see that its coefficients in the $`e_{a_i}`$ are determinants of minors of $`T`$, up to an alternating sign, which proves the final statement.

We now return to the proof of Lemma 3.3. Let $`V`$ be an affinely positive map from $`^n`$ to $`^d`$. Let $`x_k=V(e_k)`$. No $`d+1`$ of the $`x_k`$ lie on any affine hyperplane, since this would imply a linear dependence among the corresponding $`\overline{V}(e_k)`$, which is impossible because $`\overline{V}`$ is totally positive.

Now suppose $`x_i`$ and $`x_j`$ lie on opposite sides of the affine span of $`x_{a_1},\mathrm{},x_{a_d}`$. Then there exists $`0<c<1`$ such that $`cx_i+(1c)x_j`$ lies in the affine span of $`x_{a_1},\mathrm{},x_{a_d}`$, or in other words that there is some $`0<c<1`$ and some $`b_1,\mathrm{},b_d`$ summing to 1 such that $`cx_i+(1c)x_j=b_kx_{a_k}`$. Thus, $`ce_i+(1c)e_jb_ke_{a_k}`$ lies in the kernel, not merely of $`W`$, but in fact of $`\overline{W}`$. By Lemma 3.4, we know that this implies that there are an even number of $`a_k`$ lying between $`i`$ and $`j`$. Conversely, if there are an even number of $`a_k`$ lying between $`i`$ and $`j`$, we can reverse the argument to show that $`x_i`$ and $`x_j`$ lie on opposite sides of the affine span of the $`x_{a_k}`$. Thus, we see that whether or not $`x_i`$ and $`x_j`$ lie on opposite sides of the affine span of $`x_{a_1},\mathrm{},x_{a_d}`$ does not depend on the choice of $`V`$. This completes the proof of Lemma 3.3 (and hence also of Proposition 3.1).

We can now define two elements of $`T(n,d)`$, $`\widehat{1}_d`$ and $`\widehat{0}_d`$, as follows. Let $`W`$ be an affinely positive map from $`^n`$ to $`^d`$. As we have already shown (Lemma 3.2 (i)), the boundary facets of the the image of $`\mathrm{\Delta }_n`$ under $`W`$ do not depend on $`W`$, so let $`\widehat{1}_d`$ consist of the faces of $`\mathrm{\Delta }_{n1}`$ corresponding to upper boundary facets of $`W(\mathrm{\Delta }_{n1})`$, and let $`\widehat{0}_d`$ consist of its lower boundary facets. We remark that $`\widehat{1}_d`$ is clearly a maximal element of $`T(n,d)`$, and $`\widehat{0}_d`$ is clearly a minimal element. They are in fact maximum and minimum respectively, which we know from \[Ra1\] (once we know that $`T(n,d)`$ coincides with $`S(n,d)`$).

The following proposition is now clear:

###### Proposition 3.2

If $`ST(n,d)`$, the faces in $`S`$ are homeomorphic to a disk, and their boundary equals $`\widehat{0}_{d1}\widehat{1}_{d1}`$.

Finally, we show that $`T(n,d)`$ coincides with the poset $`S(n,d)`$ as conventionally defined. We begin by reviewing the definition of $`S(n,d)`$.

Fix $`d`$ a positive integer. Let $`M(t)=(t,t^2,\mathrm{},t^d)`$. Choose $`n`$ real numbers $`t_1<\mathrm{}<t_n`$. Let $`P`$ be the convex hull of the $`M(t_i)`$. $`P`$ is called a cyclic polytope.

Many combinatorial properties of $`P`$ depend only on $`d`$ and $`n`$, and not on the choice of $`t_i`$. Let $`I`$ be a $`d`$-set contained in $`[n]`$. Then whether or not the $`M(t_i)`$ for $`iI`$ form a boundary facet of $`P`$ does not depend on the choice of $`i`$. (In fact, the boundary facets are described by the well-known “Gale’s Evenness Criterion,” see \[Gr\].) Further, let $`S\left(\genfrac{}{}{0pt}{}{[n]}{d+1}\right)`$. To each $`AS`$, we can associate a simplex contained in $`P`$. And again, whether or not this collection of simplices forms a triangulation of $`P`$ does not depend on the choice of the $`t_i`$. Thus, we shall usually refer to “the” cyclic polytope in dimension $`d`$ with $`n`$ vertices, and denote it $`C(n,d)`$. When we wish to emphasize the choice of some particular $`t_i`$, we speak of a geometric realization of $`C(n,d)`$.

The partial order on $`S(n,d)`$ is given by describing its covering relations. If one is familiar with the language of bistellar flips, one can say that the covering relations $`S<T`$ are given by pairs $`S`$ and $`T`$ which are related by a single bistellar flip, where bistellar flips are given a certain natural orientation to determine whether $`S`$ precedes $`T`$ or vice versa. The reader interested in a thorough explanation of this can consult \[ER\].

More explicitly, we can define the covering relations as follows, following \[Ra1\]. Let $`M^{}(t)=(t,t^2,\mathrm{},t^{d+1})^{d+1}`$. Pick $`t_1<\mathrm{}<t_n`$. This yields geometric realizations of $`C(n,d+1)`$ and $`C(n,d)`$, where the map forgetting the last co-ordinate maps $`C(n,d+1)`$ down to $`C(n,d)`$. A triangulation $`SS(n,d)`$ defines a section $`\mathrm{\Gamma }_S^{d+1}`$ over $`C(n,d)`$ by lifting its vertices $`M(t_i)`$ to $`M^{}(t_i)`$ and then extending linearly over the simplices of $`S`$. Now, $`S<T`$ precisely if $`\mathrm{\Gamma }_S`$ and $`\mathrm{\Gamma }_T`$ coincide except within the convex hull of $`d+2`$ vertices, where $`\mathrm{\Gamma }_S`$ forms the bottom facets and $`\mathrm{\Gamma }_T`$ the top facets of a $`d+1`$-dimensional simplex.

Now we are ready to prove the following proposition:

###### Proposition 3.3

The poset $`T(n,d)`$ and the poset $`S(n,d)`$ coincide.

###### Demonstration Proof

Choose some $`0<t_1<\mathrm{}<t_n`$. If we define a map $`W`$ from $`^n`$ to $`^d`$ by setting $`W_{ij}=t_j^i`$, then $`W`$ is affinely positive (since the determinants of its minors are given by a Schur function times a Vandermonde determinant, both of which are positive), and the image under $`W`$ of $`\mathrm{\Delta }_{n1}`$ is exactly the geometric realization of $`C(n,d)`$ with parameters $`t_1,\mathrm{},t_n`$. Thus, by what we have already proven, the elements of $`T(n,d)`$ are in one-to-one correspondence with tilings of $`C(n,d)`$ by simplices whose vertices are among the vertices of $`C(n,d)`$. In general, a tiling by simplices is not necessarily a triangulation, but because no $`d+1`$ of the vertices of $`C(n,d)`$ lie on an affine hyperplane, the two notions coincide.

It is also easy to see that the covering relations in the two partially ordered sets coincide. This completes the proof of Proposition 3.3.

Since we have shown that $`T(n,d)`$ and $`S(n,d)`$ coincide, we shall use the conventional notation of $`S(n,d)`$, but the reader is advised that we will tacitly use the intuition that the elements of $`S(n,d)`$ can be considered as sets of $`d`$-faces of an $`n1`$-simplex.

## 4. The map from $`B(n,d)`$ to $`S([0,n+1],d+1)`$

We will now proceed to elucidate the poset map sketched in \[KV\] from $`B(n,d)`$ to $`S([0,n+1],d+1)`$. The definition is by induction.

###### Definition 1

If $`\alpha B(n,0)`$, then $`f_1(\alpha )`$ is the path whose vertices are the elements of $`[0,n+1]`$ not in $`\alpha `$, in increasing order.

For $`d>0`$, let $`\pi A(n,d)`$. Define $`\alpha _i`$ by $`I(\alpha _i)=\mathrm{In}_i(\pi )`$. Let $`S_i=f(\alpha _i)S([0,n+1],d)`$. We claim that for all $`i`$, either $`S_i`$ and $`S_{i+1}`$ coincide, or they differ precisely in that $`S_i`$ contains the bottom facets of some $`d+1`$-simplex $`A_{i+1}`$, while $`S_{i+1}`$ contains its top facets. Then, $`f_1([\pi ])`$ consists of the collection of the $`A_{i+1}`$ for all $`i`$ for which $`S_i`$ and $`S_{i+1}`$ are different.

Because of the reliance on the claim mentioned, this definition doesn’t establish the existence of $`f_1`$. We shall now give an explicit definition of $`f_2`$, essentially the map called $`𝒯_{\text{dir}}`$ in \[Ra1\]. An induction argument will then show that $`f_2`$ satisfies Definition 1.

If $`X=\{a_1,\mathrm{},a_d\}_<\left(\genfrac{}{}{0pt}{}{[n]}{d}\right)`$. Let $`x_X^\alpha `$ be the greatest positive integer less than $`a_1`$ such that $`F_X^\alpha (x_X^\alpha )=1`$, and set $`x_X^\alpha =0`$ if there is no such integer. Similarly, set $`z_X^\alpha `$ to be the least integer less than or equal to $`n`$ such that $`F_X^\alpha (z_X^\alpha )=1`$, and set $`z_X^\alpha =n+1`$ if there is no such integer.

###### Definition 2

For $`d=0`$, define $`f_2`$ as in Definition 1.

For $`d>0`$, let $`\alpha B(n,d)`$. Let $`X=\{a_1,\mathrm{},a_d\}_<\left(\genfrac{}{}{0pt}{}{[n]}{d}\right)`$. If, $`yX`$ such that $`a_1<y<a_d`$, $`F_X^\alpha (y)=1`$, then we associate to $`X`$ a simplex $`\{x_X^\alpha ,a_1,\mathrm{},a_d,z_X^\alpha \}`$. Define $`f_2(\alpha )`$ to be the set of simplices associated to some $`X`$.

We remark that it is by no means obvious that $`f_2(\alpha )`$ forms a triangulation; this will follow from the following theorem.

###### Theorem 4.1

The map $`f_2`$ satisfies Definition 1. More specifically, fix $`\pi A(n,d)`$. Let $`Y_1,\mathrm{},Y_{\left(\genfrac{}{}{0pt}{}{n}{d}\right)}`$ be the elements of $`\left(\genfrac{}{}{0pt}{}{[n]}{d}\right)`$ under the order $`\pi `$. Define $`\alpha _i`$ and $`S_i`$ as in Definition 1. Then if $`S_i=S_{i+1}`$ then $`f_2`$ associates no simplex to $`Y_{i+1}`$, and if $`S_i`$ and $`S_{i+1}`$ do not coincide, then $`f_2`$ does associate a simplex to $`Y_{i+1}`$, and $`S_i`$ and $`S_{i+1}`$ differ in that $`S_i`$ contains the bottom facets of this simplex and $`S_{i+1}`$ contains its top facets.

###### Demonstration Proof

The proof is by induction on $`d`$. The assertion is clear for $`d=0`$. It is also straightforward to check for $`d=1`$. So assume $`d>1`$.

Fix some $`0i<\left(\genfrac{}{}{0pt}{}{n}{d}\right)`$. For simplicity, we will denote $`Y_i`$ by $`Y`$. Let $`Y=\{a_1,\mathrm{},a_d\}_<`$. For $`1kd`$, let $`L_k`$ be the $`d1`$-dimensional face

$$L_k(j)=\{\begin{array}{cc}F_Y^{[\pi ]}(j)& ja_k\\ (1)^{k+d+1}& j=a_k\end{array}$$

Let $`T_k`$ be the face:

$$T_k(j)=\{\begin{array}{cc}F_Y^{[\pi ]}(j)& ia_k\\ (1)^{k+d}& j=a_k\end{array}$$

By Lemma 2.1, the $`L_k`$ are the lower faces of $`F_Y^{[\pi ]}`$, and $`T_k`$ are its upper faces. Thus, the $`L_k`$ are in $`K(\alpha _i)`$, while the $`T_k`$ are in $`K(\alpha _{i+1})`$.

We now calculate the images of the $`L_k`$ and $`T_k`$ under $`f_2`$. Suppose first that there is some $`jY`$, $`a_2<j<a_{d1}`$, such that $`F_Y^{[\pi ]}(j)=1`$. In this case, $`F_Y^{[\pi ]}`$ has no simplex associated to it, and none of the $`L_k`$ or $`T_k`$ have a simplex associated to them. Thus, it follows that $`S_i=S_{i+1}`$. So Definition 1 says there should be no simplex associated to $`Y`$. And in this Definition 2 concurs.

Suppose next that there is some $`a_1<j<a_2`$ and some $`a_{d1}<j^{}<a_d`$, such that $`F_Y^{[\pi ]}(j)=1`$ and $`F_Y^{[\pi ]}(j^{})=1`$. In this case, the same thing happens: none of the faces have simplices associated to them.

Suppose now that there is no $`a_{d1}<j^{}<a_d`$ with $`F_Y^{[\pi ]}(j^{})=1`$, but there is some $`a_1<j<a_2`$ such that $`F_Y^{[\pi ]}(j)=1`$. Let $`j`$ be the greatest such. Then the only one among the $`L_k`$ which has a simplex associated to it is $`L_1`$, and the simplex associated to it is $`\{j,a_2,\mathrm{},a_d,z_Y^{[\pi ]}\}`$. Similarly, the only one among the $`T_k`$ which has a simplex associated to it is $`T_1`$, and again, the simplex associated to it is $`\{j,a_2,\mathrm{},a_d,z_Y^{[\pi ]}\}`$. Thus, Definition 1 says there should be no simplex associated to $`Y`$, and Definition 2 concurs.

The case where there is no $`a_1<j<a_2`$ with $`F_Y^{[\pi ]}(j)=1`$, but there is some $`a_{d1}<j^{}<a_d`$ with $`F_Y^{[\pi ]}(j^{})=1`$, is dealt with in exactly the same way.

Finally, we consider the case where there is no $`jY`$, $`a_1<j<a_d`$, such that $`F_Y^{[\pi ]}(j)=1`$. Then there is a simplex associated to $`L_k`$ for all $`k`$ of the opposite parity to $`d`$, to $`k=d`$, and to $`k=1`$ regardless of the parity of $`d`$. Similarly, there is a simplex associated to $`T_k`$ for all $`k`$ of the same parity as $`d`$, and also for $`k=1`$ regardless of the parity of $`d`$. It is straightforward to check that the simplices associated to the $`L_k`$ and those associated to the $`T_k`$ are form the bottom and top of the simplex $`\{x_Y^{[\pi ]},a_1,\mathrm{},a_d,z_Y^{[\pi ]}\}`$, which is the simplex associated to $`Y`$. This completes the proof of the theorem.

We shall denote by $`f`$ the map defined by the two equivalent definitions above.

###### Proposition 4.1

The map $`f:B(n,d)S([0,n+1],d+1)`$ is order-preserving.

###### Demonstration Proof

We will show that if $`\beta \gamma `$ in $`B(n,d)`$ then either $`f(\beta )=f(\gamma )`$ or $`f(\beta )f(\gamma )`$.

It is shown in \[MS\] that $`\widehat{0}_d`$ is the minimum element of $`B(n,d)`$, and $`\widehat{1}_d`$ is the maximum element. This implies that there is an unrefinable chain from $`\widehat{0}_d`$ to $`\gamma `$, and an unrefinable chain from $`\beta `$ to $`\widehat{1}_d`$. At each step along these chains, the inversion set increases by a single element. The order in which these elements are added defines an admissible ordering $`\pi A(n,d+1)`$ which has the property that $`I(\gamma )`$ and $`I(\beta )`$ occur as initial subsequences.

Define $`\alpha _iB(n,d)`$ by $`I(\alpha _i)=\mathrm{In}_i(\pi )`$, and let $`S_i=f(\alpha _i)`$. Definition 1 of $`f([\pi ])`$ tells us that $`S_i`$ and $`S_{i+1}`$ either coincide or $`S_iS_{i+1}`$. There is some $`k`$ such that $`\alpha _k=\gamma `$ and $`\alpha _{k+1}=\beta `$, so either $`f(\gamma )=f(\beta )`$ or $`f(\gamma )f(\beta )`$, as desired.

For completeness we give yet another definition of $`f`$, also from \[Ra1\].

###### Definition 3

Let $`\beta B(n,d)`$. Let $`I(\beta )=\{X_1,\mathrm{},X_r\}`$ where the $`X_i`$ are ordered so that every initial subsequence is also consistent. Set $`T_0=\widehat{0}_dS([0,n+1],d)`$. Define $`T_i`$ by induction: if $`T_{i1}`$ contains the bottom facets of a simplex with vertices $`\{x\}X_i\{z\}`$ for some $`x`$ less than any element of $`X_i`$ and $`z`$ greater than any element of $`X_i`$, then let $`T_i`$ consist of the facets of $`T_{i1}`$ with these bottom facets replaced by the simplex’s corresponding top facets. Otherwise, let $`T_i=T_{i1}`$. Then set $`f_3(\beta )=T_r`$.

###### Theorem 4.2 \[Ra1\]

The map $`f_3`$ is well-defined and coincides with the map $`f`$.

###### Demonstration Proof

It is shown in \[Ra1\] that Definition 2 and Definition 3 are equivalent. We give a somewhat different proof. In the proof, we fix $`n`$ and $`d`$, and induct on $`r`$, the size of the inversion set of $`\beta B(n,d)`$. Define $`\gamma B(n,d)`$ by $`I(\gamma )=\{X_1,\mathrm{},X_{r1}\}`$. By the induction hypothesis, $`f_2(\gamma )=f_3(\gamma )`$. Now $`K(\gamma )`$ and $`K(\beta )`$ differ in that there is some $`d+1`$-face $`F`$ of the standard $`n`$-cube such that $`K(\beta )`$ includes the top facets and $`K(\gamma )`$ the bottom facets.

As in the proof of Proposition 4.1, we construct an order $`\pi A(n,d+1)`$, $`\alpha _iB(n,d)`$ such that $`I(\alpha _i)=\mathrm{In}_i(\pi )`$, so that there exists some $`k`$ such that $`\alpha _k=\gamma `$ and $`\alpha _{k+1}=\beta `$.

Now, as shown in the proof of Theorem 4.1, exactly one of three things can happen:

i) The map $`f_2:B(n,d)S([0,n+1],d+1)`$ doesn’t associate a simplex to any of the facets of $`F`$, and $`f_2(\gamma )=f_2(\beta )`$.

ii) The map $`f_2`$ as above associates a simplex to exactly one upper facet of $`F`$ and one lower facet of $`F`$ and $`f_2(\gamma )=f_2(\beta )`$.

iii) We have $`f_2(\gamma )f_2(\beta )`$.

In cases (i) and (ii), it is easy to check that $`f_3(\gamma )`$ does not contain the bottom facets of a $`d+1`$-simplex with vertices $`\{x\}X_r\{z\}`$ as above, so $`f_3(\beta )=f_3(\gamma )=f_2(\gamma )=f_2(\beta )`$, as desired.

In case (iii), $`f_3(\gamma )`$ contains the bottom facets of a simplex of the desired form, and $`f_2(\beta )`$ consists of $`f_2(\gamma )`$ with these bottom facets replaced by the corresponding top facets. Thus $`f_3(\beta )=f_2(\beta )`$, as desired.

It is claimed (without proof) in \[KV\] that $`f:B(n,d)S([0,n+1],d+1)`$ is surjective for all $`n`$ and $`d`$. We cannot prove this in general. In the following two sections, we will consider the cases $`d=1`$, where surjectivity will turn out to be equivalent to known results, and $`d=2`$, where surjectivity is new.

## 5. The map $`B(n,1)S([0,n+1],2)`$

In this section we show that the map $`B(n,1)S([0,n+1],d)`$ is essentially the same as a very familiar map from permutations to planar binary trees (see \[St1, 1.3.13\],\[BW1\],\[LR1\],\[To\]). Because this map appears in many guises, we will give our own definition which is equivalent to all the others.

Let $`Y_n`$ denote the planar binary trees with $`n`$ internal vertices. For $`(a_1,\mathrm{},a_p)`$ a sequence of $`p`$ distinct numbers, let $`\mathrm{std}(a_1,\mathrm{},a_p)`$, the standardization of $`(a_1,\mathrm{},a_p)`$, denote the sequence of numbers from 1 to $`p`$ arranged in the same order. Define $`\psi :B(n,1)Y_n`$ inductively, as follows: for $`n`$=0, $`\psi `$ applied to the empty permutation is an empty tree; and for $`n1`$, $`\pi B(n,1)`$, write $`\pi =(a_1\mathrm{}a_pnb_1\mathrm{}b_q)`$, and then let $`\psi (\pi )`$ be the tree consisting of one parent node with left subtree $`\psi (\mathrm{std}(a_1,\mathrm{},a_p))`$, and right subtree $`\psi (\mathrm{std}(b_1,\mathrm{},b_q))`$.

We recover the map $`f:B(n,1)S([0,n+1],2)`$ by composing $`\psi `$ with a standard bijection $`\theta `$ between triangulations of an $`n+2`$-gon and planar binary trees with $`n`$ internal vertices, as follows. Choose a geometric realization of $`C([0,n+1],2)`$, which we will refer to as $`P`$. Fix $`SS([0,n+1],2)`$. $`S`$ can be viewed as a triangulation of $`P`$. Put a vertex inside each triangle of $`S`$. Connect two vertices if their triangles share a common edge. Orient the edge joining the vertices so that it points from the triangle above the edge to the one below the edge (“above” and “below” are with respect to the second coordinate). For each external edge of $`P`$, except that between 0 and $`n+1`$, attach a leaf to the vertex corresponding to the triangle containing that edge. Because of the way we drew $`P`$, every triangle has one upper edge and two lower edges, which we may view as a left edge and a right edge. Thus, the tree we have drawn can be viewed as a planar binary tree, whose root is the vertex associated to the triangle containing the edge from $`0`$ to $`n+1`$. Let this planar binary tree be denoted $`\theta (S)`$. In the diagram below, we see a triangulation of a $`5`$-gon and its corresponding tree superimposed. It is clear that $`\theta `$ is a bijection.

###### Proposition 5.1

For $`\pi B(n,1)`$, $`f(\pi )=\theta ^1(\psi (\pi ))`$.

###### Demonstration Proof

The proof is a simple inductive check.

We now wish to describe the fibre of $`f`$ over $`SS([0,n+1],2)`$. These results have already appeared in the literature; see \[LR1\], \[LR2\], \[BW1\], \[BW2\].

Any triangle in $`S`$ has a unique middle vertex, the vertex between the two bottom edges. If the vertices of the triangle are $`a<b<c`$, the middle vertex is $`b`$. Each vertex of $`P`$ other than $`0`$ and $`n+1`$ is the middle vertex of a unique triangle of $`S`$: the triangle with $`b`$ as a middle vertex is the one containing $`b`$ and points immediately above it.

We move briefly into greater generality. Let $`TS([0,n+1],d)`$. A linear order on its simplices is said to be ascending if for any pair of simplices sharing a facet, the simplex lying above the intersection facet follows the simplex below the intersection. It is shown in \[Ra1\] that there exist ascending orders on the simplices of any triangulation of a cyclic polytope of arbitrary dimension.

A linear order on the triangles of $`S`$ corresponds to a permutation of $`[n]`$ by mapping triangles to middle vertices.

###### Proposition 5.2

The fibre of $`f`$ over $`S`$ consists of the permutations corresponding to ascending orders on the triangles of $`S`$.

###### Demonstration Proof

The proof is immediate from Definition 1.

This motivates us to inquire further about the ascending orders on the triangles of $`S`$. We see that the final triangle must be the one containing the edge $`\{0,n+1\}`$, which we shall denote $`A`$. Preceding it must be a shuffle of an ascending order on the triangles to the left of $`A`$ and an ascending order on the triangles to the right of $`A`$. This allows us to prove the following (already known) proposition:

###### Proposition 5.3

There are maps $`\mathrm{Min},\mathrm{Max}:S([0,n+1],2)B(n,1)`$ such that the fibre of $`f`$ over $`SS([0,n+1],2)`$ is the non-empty closed interval $`[\mathrm{Min}(S),\mathrm{Max}(S)]`$ in $`B(n,1)`$.

###### Demonstration Proof

Let $`A`$ be the triangle of $`S`$ containing the edge $`\{0,n+1\}`$, and let its bottom vertex be $`a`$. Let $`P_l`$ and $`P_r`$ be the subpolygons of $`P`$ to the left and right respectively of $`A`$. Let $`S_l`$ and $`S_r`$ be the restrictions of $`S`$ to $`P_l`$ and $`P_r`$ respectively. By induction, there is a permutation of $`\mathrm{Min}(S_l)`$ of $`\{1,\mathrm{},a1\}`$ which is the mininimum among those ascending with respect to $`S_l`$, and similarly a permutation $`\mathrm{Min}(S_r)`$ of $`\{a+1,\mathrm{},n\}`$ which is the minimum among those ascending with respect to $`S_r`$, and similarly permutation $`\mathrm{Max}(S_l)`$ and $`\mathrm{Max}(S_r)`$. Now it is clear that the minimum ascending order with respect to $`S`$ is $`(\mathrm{Min}(S_l)\mathrm{Min}(S_r)a)`$, and the maximum ascending order with respect to $`S`$ is $`(\mathrm{Max}(S_r)\mathrm{Max}(S_l)a)`$.

## 6. The map $`B(n,2)S([0,n+1],3)`$

This section is chiefly dedicated to the proof of the following proposition:

###### Proposition 6.1

$`f:B(n,2)S([0,n+1],3)`$ is surjective.

###### Demonstration Proof

Let $`SS([0,n+1],3)`$. Fix an ascending order (as defined in the previous section) on its simplices: $`A_1,\mathrm{},A_s`$.

We will now define a chain of $`T_i`$ in $`S([0,n+1],2)`$, having the property that their simplices occur as facets of the simplices of $`S`$. Let $`T_0`$ be the minimum element of $`S([0,n+1],2)`$. Define $`T_i`$ inductively by replacing the simplices of $`T_{i1}`$ which are bottom facets of $`A_i`$ by the top facets of $`A_i`$.

###### Lemma 6.1

For $`i<j`$, $`\mathrm{Min}(T_i)<\mathrm{Min}(T_j)`$ in $`B(n,1)`$.

###### Demonstration Proof

Clearly, it suffices to consider the case where $`j=i+1`$. Suppose the vertices of $`A_{i+1}`$ are $`a<b<c<d`$. Then $`T_i`$ and $`T_{i+1}`$ look like:

Outside the quadrilateral with vertices $`a`$, $`b`$, $`c`$, and $`d`$, $`T_i`$ and $`T_{i+1}`$ coincide.

Let $`U`$, $`V`$, and $`W`$ denote their common restrictions to the regions below the lines $`\{a,b\}`$, $`\{b,c\}`$, and $`\{c,d\}`$ respectively. Then $`\mathrm{Min}(T_i)`$ and $`\mathrm{Min}(T_{i+1})`$ coincide except for a consecutive sequence describing the triangles below the line $`\{a,d\}`$, which runs $`\mathrm{Min}(U)\mathrm{Min}(V)b\mathrm{Min}(W)c`$ in $`T_i`$ and $`\mathrm{Min}(U)\mathrm{Min}(V)\mathrm{Min}(W)cb`$ in $`T_{i+1}`$. From this it follows that $`\mathrm{Min}(T_{i+1})>\mathrm{Min}(T_i)`$ in $`B(n,1)`$.

From the lemma, the proposition is almost immediate. Pick a maximal chain $`\pi _0<\pi _1<\mathrm{}<\pi _{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}`$ in $`B(n,1)`$ which refines the chain $`\mathrm{Min}(T_0)<\mathrm{Min}(T_1)<\mathrm{}<\mathrm{Min}(T_s)`$. So $`I(\pi _{i+1})`$ consists of one more element than $`I(\pi _i)`$. Let $`Y_i=I(\pi _{i+1})I(\pi _i)`$. Now $`Y_1,Y_2,\mathrm{},Y_{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}`$ is an admissible order on $`\left(\genfrac{}{}{0pt}{}{[n]}{2}\right)`$, and thus defines an element of $`\alpha B(n,2)`$. It is clear from Definition 1 that $`f(\alpha )=S`$.

Having shown surjectivity of $`f:B(n,2)S([0,n+1],3)`$, we might hope to prove an analogue of Proposition 5.3. However, the fibres of the map from $`B(n,2)`$ to $`S([0,n+1],3)`$ are more complicated than the fibres of the map from $`B(n,1)`$ to $`S([0,n+1],2)`$, as the following example shows. Let $`I=\{123,124,456,356\}\left(\genfrac{}{}{0pt}{}{[6]}{2}\right)`$. Let $`\alpha B(6,2)`$ be defined by $`I(\alpha )=I`$. Then $`S=f(\alpha )`$ is the triangulation consisting of the following simplices:

$$S=\{0125,0156,0167,0234,0245,1256,1267,2345,2357,2567,3457\}.$$

Using Definition 2, one checks that $`\beta f^1(S)`$ iff $`II(\beta )I\{134,346\}`$. Now $`I\{134\}`$ and $`I\{346\}`$ are consistent, but $`I\{134,346\}`$ is not. Thus, the fibre of $`f`$ over $`S`$ has no maximum element. (This example was based on an example given in \[Zi\] to show that $`B(6,2)`$ is not a lattice.) Thus, there is no simple analogue of Proposition 5.3. In turn, this makes it harder to understand the map $`B(n,3)S([0,n+1],4)`$.

## 7. Interpretation of $`\mathrm{lk}_0f`$ and $`\mathrm{lk}_{\{0,n+1\}}f`$

Let $`SS([0,n+1],d+1)`$. Then $`\mathrm{lk}_0(S)=\{A\{0\}0AS\}`$, the link of $`S`$ at 0. As was remarked in \[ER\] and proved in \[Ra1\], thinking of this link as describing faces of the vertex figure of $`\mathrm{\Delta }_{n+1}`$ at 0, we see that $`\mathrm{lk}_0(S)S(n+1,d)`$. Similarly, we can define $`\mathrm{lk}_{n+1}(S)S([0,n],d)`$. The map $`\mathrm{lk}_0`$ is order-preserving; $`\mathrm{lk}_{n+1}`$ is order-reversing. (One might wonder about taking links at other vertices. For $`d`$ even, these other links are not naturally elements of $`S(n+1,d)`$; for $`d`$ odd one can define a link in a suitably labelled $`S(n+1,d)`$ but this link map does not respect the poset structures.)

In this section, we give geometric interpretations of $`\mathrm{lk}_0f`$ and $`\mathrm{lk}_{\{0,n+1\}}f`$.

###### Proposition 7.1

Let $`\pi B(n,d)`$. Then a simplex $`A\mathrm{lk}_{\{0,n+1\}}f`$ iff $`F_A^\pi `$ contains $`(1,\mathrm{},1)`$. In other words, $`\mathrm{lk}_{\{0,n+1\}}(f(\pi ))`$ is the vertex figure of $`K(\pi )`$ at $`(1,\mathrm{},1)`$.

###### Demonstration Proof

The first statement follows immediately from Definition 2 of $`f`$. The second statement follows immediately from the first.

Let us write $`[1,1]_{}^n`$ for the weakly increasing $`n`$-tuples from $`[1,1]`$. This set forms a simplex with $`n+1`$ vertices, whose coordinates consisting of a string of $`1`$s followed by a string of $`1`$s. We identify this simplex with the standard $`n`$-simplex by labelling the vertex whose first $`a1`$ coefficients are $`1`$ as vertex $`a`$.

Let us define a map:

$`W:[1,1]^n[1,1]_{}^n`$
$`W(a_1,\mathrm{},a_n)=(a_1,\mathrm{max}(a_1,a_2),\mathrm{},\mathrm{max}(a_1,a_2,\mathrm{},a_n))`$
###### Proposition 7.2

Let $`\pi B(n,d)`$. Then a simplex $`A\mathrm{lk}_0(f(\pi ))`$ iff $`dim(W(F_A^\pi ))=dim(F_A^\pi )`$. Consequently, $`\mathrm{lk}_0(f(\pi ))=W(K(\pi ))`$.

###### Demonstration Proof

The first statement follows as before from Definition 2 of $`f`$.

From the first statement, it follows that $`\mathrm{lk}_0(f(\pi ))`$ consists of the images under $`W`$ of the faces of $`K(\pi )`$ which don’t drop dimension under $`W`$. Next, we check that if $`F_A^\pi `$ drops dimension, then $`W(F_A^\pi )`$ coincides with the images under $`W`$ of the union of the upper faces of $`F_A^\pi `$, and also with the union of the lower faces of $`F_A^\pi `$, which is straightforward. Now let $`A_1,\mathrm{},A_{\left(\genfrac{}{}{0pt}{}{n}{d}\right)}`$ be an admissible order in the equivalence class $`\pi `$. Now let $`J\left[\left(\genfrac{}{}{0pt}{}{n}{d}\right)\right]`$ denote the indices $`j`$ such that $`F_{A_j}^\pi `$ does not drop dimension. Then a simple induction argument shows that for any $`i`$,

$$W\left(\underset{1ji}{}F_{A_j}^\pi \right)=\underset{\genfrac{}{}{0pt}{}{1ji}{jJ}}{}W(F_{A_j}^\pi )$$

For $`i=\left(\genfrac{}{}{0pt}{}{n}{d}\right)`$, this is exactly what we want.

## 8. Combinatorics of $`S(n,d)`$

For the remainder of the paper, we shall need a combinatorial description of $`S(n,d)`$ introduced in \[Th\]. We begin with some preliminary definitions.

For $`\{a_1,\mathrm{},a_{d+1}\}_<`$ a subset of $`[n]`$, let $`r(a_1,\mathrm{},a_{d+1})`$ denote the subset of $`\left(\genfrac{}{}{0pt}{}{[n1]}{d}\right)`$ which consists of those $`d`$-sets consisting of exactly one element from $`[a_i,a_{i+1}1]`$ for $`1id`$. Subsets of $`\left(\genfrac{}{}{0pt}{}{[n1]}{d}\right)`$ of this form are called snug rectangles. We say that a set of snug rectangles forms a snug partition if each $`d`$-set in $`\left(\genfrac{}{}{0pt}{}{[n1]}{d}\right)`$ occurs in exactly one of the snug rectangles.

To $`SS(n,d)`$, we associate the collection of snug rectangles $`r(S)`$ which consists of the rectanges $`r(a_1,\mathrm{},a_{d+1})`$ for each simplex $`\{a_1,\mathrm{},a_{d+1}\}_<`$ in $`S`$. Then we have the following theorem:

###### Theorem 8.1 \[Th\]

The map $`r`$ defines a bijection from $`S(n,d)`$ to snug partitions of $`\left(\genfrac{}{}{0pt}{}{[n1]}{d}\right)`$.

The description of the covering relations of $`S(n,d)`$ in terms of snug partitions is straightforward. As we know, $`ST`$ in $`S(n,d)`$ is equivalent to the existence of some $`d+1`$-simplex $`\{a_1,\mathrm{},a_{d+2}\}_<`$ such that $`S`$ and $`T`$ coincide except within this simplex, where $`S`$ consists of its top facets and $`T`$ consists of its bottom facets. By Lemma 3.1, this is equivalent to the existence of $`\{a_1,\mathrm{},a_{d+2}\}_<`$ such that $`r(S)`$ and $`r(T)`$ coincide except that $`r(S)`$ contains the snug rectangles $`r(a_1,\mathrm{},\widehat{a}_i,\mathrm{},a_{d+2})`$ for $`i`$ odd, and $`r(T)`$ contains the snug rectangles $`r(a_1,\mathrm{},\widehat{a}_i,\mathrm{},a_{d+2})`$ for $`i`$ even.

It is sometimes convenient to adopt a different point of view on snug partitions, where we partition $`\left(\genfrac{}{}{0pt}{}{[n1]}{nd1}\right)`$ instead of $`\left(\genfrac{}{}{0pt}{}{[n1]}{d}\right)`$. For $`\{a_1,\mathrm{},a_{d+1}\}_<[n]`$, let $`r^c(a_1,\mathrm{},a_{d+1})`$ denote the elements of $`\left(\genfrac{}{}{0pt}{}{[n1]}{nd1}\right)`$ which are complements in $`[n1]`$ of an element of $`r(a_1,\mathrm{},a_{d+1})`$. We refer to $`r^c(a_1,\mathrm{},a_{d+1})`$ as a complementary snug rectangle.

This complementary snug rectangle can be described explicitly as follows. Let $`\{a_1^c,\mathrm{},a_{nd1}^c\}_<=[n]\{a_1,\mathrm{},a_{d+1}\}`$. Then

$$r^c(a_1,\mathrm{},a_{d+1})=(\{a_1^c1,a_1^c\}\times \mathrm{}\times \{a_{nd1}^c1,a_{nd1}^c\})\left(\genfrac{}{}{0pt}{}{[n1]}{nd1}\right).$$

A complementary snug partition is a partition of $`\left(\genfrac{}{}{0pt}{}{[n1]}{nd1}\right)`$ into complementary snug rectangles. A complementary snug partition records the same information as a snug partition, but sometimes it is handier to deal with.

We now describe an important feature of the combinatorics of $`S(n,d)`$, namely, the collapse maps, poset maps from $`S(n,d)`$ to $`S(p,d)`$ with $`p<n`$.

Let $`I`$ be a subset of $`[n1]`$. Let $`m_I:[n]I\{n\}`$ be the map defined by $`m_I(a)=\mathrm{min}\{iI\{n\},ia\}`$.

Consider the map from $`^n`$ to $`^{I\{n\}}`$ which takes $`e_i`$ to $`e_{m_I(i)}`$. This defines a map from $`\mathrm{\Delta }_{n1}`$ to $`\mathrm{\Delta }_{|I|}^{I\{n\}}`$. We define a map $`c_I`$ on faces of $`\mathrm{\Delta }_{n1}`$, which takes a face to its image in $`\mathrm{\Delta }_{|I|}`$, or to $`\mathrm{}`$ if its image is lower dimensional. Explicitly, if $`A=\{a_1,\mathrm{},a_{d+1}\}_<`$, then

$$c_I(A)=\{m_I(a_1),\mathrm{},m_I(a_{d+1})\}$$

provided the $`m_I(a_i)`$ are all distinct, and $`c_I(A)=\mathrm{}`$ otherwise.

Now, for $`SS(n,d)`$, define $`c_I(S)`$ to be the collection of non-empty $`c_I(A)`$ for $`AS`$. We have the following lemma:

###### Lemma 8.1

For $`IJ[n1]`$, $`SS(n,d)`$, $`A=\{a_1,\mathrm{},a_{d+1}\}_<`$:

i) $`c_I(S)S(I\{n\},d)`$

ii) $`c_I(S)=c_I(c_J(S))`$

iii) $`r(c_I(A))=r(A)\left(\genfrac{}{}{0pt}{}{I}{d}\right)`$

iv) $`r(c_I(S))=\{X\left(\genfrac{}{}{0pt}{}{I}{d}\right)Xr(S),X\left(\genfrac{}{}{0pt}{}{I}{d}\right)\mathrm{}\}`$.

###### Demonstration Proof

The first part is perhaps easiest to see if we think of $`S(n,d)`$ as triangulations of $`C(n,d)`$. If $`I=\{i_1,\mathrm{},i_{r1}\}`$, we can pick a geometric realization of $`C(n,d)`$ and gradually deform it, bringing the vertices $`1,\mathrm{},i_1`$ closer and closer together, and similarly for $`i_1+1,\mathrm{},i_2`$ and so on, while preserving the property of being a cyclic polytope. The limit of this process is a cyclic polytope with vertices labelled by $`I\{n\}`$. If we begin with a triangulation $`S`$ and deform it in this manner, discarding simplices which degenerate, we obtain $`c_I(S)`$.

The other parts are straightforward.

We now draw some consequences of the fact that collapse maps take triangulations to triangulations.

###### Lemma 8.2

Let $`X=\{x_1,\mathrm{},x_{d+1}\}_<\left(\genfrac{}{}{0pt}{}{[n1]}{d+1}\right)`$, and let $`P`$ be the $`d`$-packet of its $`d`$-subsets. Then:

(i) Let $`R`$ be a snug rectangle in $`\left(\genfrac{}{}{0pt}{}{[n1]}{d}\right)`$. The possible intersection of $`R`$ with $`P`$ are: $`\{X\{x_1\}\}`$, $`\{X\{x_{d+1}\}\}`$, or $`\{X\{x_i\},X\{x_{i+1}\}\}`$ for $`1id`$.

(ii) Let $`SS(n,d)`$. Let $`W`$ be the corresponding snug partition of $`\left(\genfrac{}{}{0pt}{}{[n1]}{d}\right)`$. Then the non-empty intersections of $`P`$ with rectangles of $`W`$ are either

$`\{X\{x_{d+1}\},X\{x_d\}\},\{X\{x_{d1}\},X\{x_{d2}\}\},\mathrm{}\text{ or}`$
$`\{X\{x_{d+1}\}\},\{X\{x_d\},X\{x_{d1}\}\},\mathrm{}`$
In the former case $`XI(S)`$; in the latter case $`XI(S)`$.

###### Demonstration Proof

The intersection of a snug rectangle with $`P`$ must be a snug rectangle in $`\left(\genfrac{}{}{0pt}{}{X}{d}\right)`$ by Lemma 8.1 (iii). The snug rectangles in $`\left(\genfrac{}{}{0pt}{}{X}{d}\right)`$ are exactly the possible intersections listed in the statement of the lemma, which proves (i).

The restriction of $`W`$ to $`\left(\genfrac{}{}{0pt}{}{X}{d}\right)`$ must be a snug partition of $`\left(\genfrac{}{}{0pt}{}{X}{d}\right)`$, by Lemma 8.1 (iv). These correspond to triangulations of $`C(X,d)C(d+2,d)`$; there are two of these. The snug partition corresponding to $`\widehat{1}_d`$ is the first list of rectangles, while the snug partition corresponding to $`\widehat{0}_d`$ is the second list. This proves (ii).

## 9. The map $`g:S(n,d)B(n1,d)`$

In this section we define a map $`g:S(n,d)B(n1,d)`$, which is analogous to $`f`$ in ways which will be made clear later.

Observe that $`S(d+2,d)`$ consists of 2 elements, which, as usual, we denote $`\widehat{0}_d`$ and $`\widehat{1}_d`$. For $`SS(n,d)`$, let $`I(S)=\{X\left(\genfrac{}{}{0pt}{}{[n1]}{d+1}\right)c_X(S)=\widehat{1}\}`$. We wish to define $`g(S)`$ by setting $`I(g(S))=I(S)`$. In order for this to make sense, we must prove the following proposition:

###### Proposition 9.1

For $`SS(n,d)`$, $`I(S)\left(\genfrac{}{}{0pt}{}{[n1]}{d+1}\right)`$ is a consistent set

###### Demonstration Proof

To check that a set of $`d+1`$-subsets of $`[n1]`$ is consistent, we must check that its intersection with any $`d+1`$-packet is either an initial or final segment. So let $`J=\{a_1,\mathrm{},a_{d+2}\}_<[n1]`$. By part (ii) of Lemma 8.1, $`I(S)\left(\genfrac{}{}{0pt}{}{J}{d+1}\right)=\{X\left(\genfrac{}{}{0pt}{}{J}{d+1}\right)|c_X(c_J(S))=\widehat{1}\}=I(c_J(S))`$. Since $`c_J(S)S(J\{n\},d)S(d+3,d)`$, it suffices to consider the proposition in $`S(d+3,d)`$.

The triangulations of $`C(d+3,d)`$ are well-understood. There are $`d+3`$ of them, and the Hasse diagram $`S(d+3,d)`$ is shown below. (The labels will be explained shortly.)

We shall use complementary snug partitions to give a simple pictorial representation of these triangulations. Put $`\left(\genfrac{}{}{0pt}{}{[d+2]}{2}\right)`$ in correspondence with a diagram of boxes with $`d+1`$ columns numbered 1 to $`d+1`$ and $`d+1`$ rows numbered from 2 to $`d+2`$, with boxes in positions $`(i,j)`$ with $`i<j`$. A complementary snug rectangle is the intersection of a $`2\times 2`$ square with this diagram, where all partial intersections are allowed, except the intersections consisting of a single box $`(p,p+1)`$ with $`1<p<d+1`$. A complementary snug partition consists of a tiling of this diagram by $`2\times 2`$ squares, with the stated restrictions on partial intersections. It is easy to see by playing with the pictures that there are two tilings which have no $`2\times 2`$ square with its bottom right corner on the diagonal (the left and right pictures below). The tiling $`\widehat{0}`$ is the one which has the box $`(d+1,d+2)`$ in a square by itself; the other is $`\widehat{1}`$. The other tilings have exactly one $`2\times 2`$ square with its lower right corner on a box on the diagonal and for each box on the diagonal, there is exactly one such tiling. These triangulations are denoted $`S_i`$ for $`1id+1`$. $`S_i`$ denotes the triangulation which contains the square $`\left([i1,i]\times [i+1,i+2]\right)\left(\genfrac{}{}{0pt}{}{d+2}{2}\right)`$, whose lower right corner is $`(i,i+1)`$.

From this analysis, we can see that the Hasse diagram is as above. Further, we see that $`I(\widehat{0})=\mathrm{}`$; $`I(\widehat{1})=\left(\genfrac{}{}{0pt}{}{[d+2]}{d+1}\right)`$; for $`di`$ even $`I(S_i)=\{[d+2]\{1\},\mathrm{},[d+2]\{i\}\}`$; for $`di`$ odd $`I(S_i)=\{[d+2]\{i+1\},\mathrm{},[d+2]\{d+2\}\}`$. By inspection, all these sets are consistent, which proves the proposition.

In fact, we have proved more than we needed. Let us say that $`I\left(\genfrac{}{}{0pt}{}{[n1]}{d+1}\right)`$ is superconsistent if its intersection with any $`d+1`$-packet is either an initial segment of odd length or a final segment of the same parity as $`d`$ (or empty or full). Then for $`SS(n,d)`$, $`I(S)`$ is superconsistent. And more is true:

###### Theorem 9.1

If $`I\left(\genfrac{}{}{0pt}{}{[n1]}{d+1}\right)`$ is superconsistent, then it is the inversion set of some $`SS(n,d)`$. Equivalently, the image of $`g:S(n,d)B(n1,d)`$ consists of those elements with superconsistent inversion sets.

###### Demonstration Proof

Let $`I`$ be a superconsistent subset of $`\left(\genfrac{}{}{0pt}{}{[n1]}{d+1}\right)`$. We wish to determine a corresponding snug partition of $`\left(\genfrac{}{}{0pt}{}{[n1]}{d}\right)`$.

For each $`X=\{x_1,\mathrm{},x_d\}_<\left(\genfrac{}{}{0pt}{}{[n1]}{d}\right)`$, we wish to determine a snug rectangle containing $`X`$. Write $`\{x_1^c,\mathrm{},x_{nd1}^c\}_<`$ for $`[n1]X`$.

If $`X\{x_i^c\}I`$, then let

$$s_i^c=\{\begin{array}{cc}x_i^c& \text{ if }d+ix_i^c\text{ is even}\\ x_i^c+1& \text{ if }d+ix_i^c\text{ is odd }\end{array}$$

If $`X\{x_i^c\}I`$, then let

$$s_i^c=\{\begin{array}{cc}x_i^c& \text{ if }d+ix_i^c\text{ is odd }\\ x_i^c+1& \text{ if }d+ix_i^c\text{ is even}\end{array}$$

I claim the $`s_i^c`$ are all different. Suppose $`s_i^c=s_{i+1}^c`$. Then clearly $`x_i^c=x_{i+1}^c1`$, and either $`X\{x_i^c\}I`$, $`X\{x_{i+1}^c\}I`$, and $`d+ix_i^c`$ is odd, or $`X\{x_i^c\}I`$, $`X\{x_{i+1}^c\}I`$, and $`d+ix_i^c`$ is even. We assume that we are in the first case. The number of elements of $`X`$ greater than $`x_i^c`$ is $`d+ix_i^c`$, so it is odd. Since $`I`$ is consistent, if $`xX`$, $`x<x_i^c`$, then $`X\{x_i^c,x_{i+1}^c\}\{x\}I`$, while if $`xX`$, $`x>x_{i+1}^c`$, then $`X\{x_i^c,x_{i+1}^c\}\{x\}I`$. But this means that the intersection of $`I`$ with the $`d+1`$-packet $`\left(\genfrac{}{}{0pt}{}{X\{x_i^c,x_{i+1}^c\}}{d+1}\right)`$ is an initial segment of even length, which contradicts the fact that $`I`$ is superconsistent. The other case, when $`X\{x_i^c\}I`$, is very much the same.

Now, set $`S_X=[n]\{s_1^c,\mathrm{},s_{nd1}^c\}`$. Now $`r^c(S_X)=(\{s_1^c1,s_1^c\}\times \mathrm{}\times \{s_{nd1}^c1,s_{nd1}^c\})\left(\genfrac{}{}{0pt}{}{[n1]}{nd1}\right)`$, and it is clear that $`(x_1^c,\mathrm{},x_{nd1}^c)r^c(S_X)`$, so $`Xr(S_X)`$.

Now, I claim that if $`X,Y\left(\genfrac{}{}{0pt}{}{[n1]}{d}\right)`$, and $`Yr(S_X)`$, then $`S_Y=S_X`$. Let $`X=\{x_1,\mathrm{},x_d\}_<`$, and let $`\{x_1^c,\mathrm{},x_{nd1}^c\}_<=[n1]X`$. Since we can move from $`X^c`$ to $`Y^c`$ by succcessive changes of a single coordinate by plus or minus one, while remaining in $`r^c(X)`$, it suffices to assume that $`Y^c=(x_1^c,\mathrm{},x_i^c\pm 1,\mathrm{},x_{nd1}^c)r^c(X)`$. In fact, we assume $`Y^c=(x_1^c,\mathrm{},x_i^c+1,\mathrm{},x_{nd1}^c)r^c(X)`$.

Thus either $`X\{x_i^c\}I`$ and $`d+ix_i^c`$ is odd, or $`X\{x_i^c\}I`$ and $`d+ix_i^c`$ is even. Let us assume the former; the proof is similar in the latter case.

We need to verify that $`X\{x_j^c\}I`$ iff $`Y\{x_j^c\}I`$ for all $`ji`$. Suppose otherwise for some $`j`$, and, for the moment, suppose $`j<i`$. There are an odd number of $`x_k`$ greater than $`x_i^c`$, so, by the superconsistency of $`I`$, it must be that $`X\{x_j^c\}I`$ while $`Y\{x_j^c\}I`$. By the consistency of $`I`$, this implies that $`X\{x_i^c\}I`$, contradicting the assumption. The case where $`j<i`$ is similar. This completes the proof that $`S_X=S_Y`$, and thus that the $`r(S_X)`$ form a snug partition.

Let $`T`$ be the corresponding element of $`S(n,d)`$. I claim that $`I(T)=I`$. Let $`Z=\{z_1,\mathrm{},z_{d+1}\}_<[n1]`$. Let $`X=Z\{z_{d+1}\}`$, $`Y=Z\{z_d\}`$. As usual, let $`[n1]X=\{x_1^c,\mathrm{},x_{nd1}^c\}_<`$, and similarly for $`Y`$. Let $`z_{d+1}=x_i^c`$. Note that $`d+ix_i^c=0`$. Thus, if $`ZI`$, $`s_i^c=x_i^c+1`$. But $`y_i^c=z_{d+1}1`$. Thus $`y^cr^c(S_X)`$, so $`X`$ and $`Y`$ are in different snug rectangles in the snug partition corresponding to $`T`$. By Lemma 8.2, this implies that $`ZI(T)`$.

Now, suppose that $`ZI`$. Observe that for $`kz_{d+1}(z_d+1)`$, $`z_{d+1}k=x_{ik}^c`$. As before, $`d+ix_i^c=0`$, so $`x_i^c=s_i^c`$. Now, by induction on $`k`$, using the fact that the $`s_j^c`$ are all distinct, it follows that for $`kz_{d+1}(z_d+1)`$, $`s_{ik}^c=x_{ik}^c`$. This implies that $`y^cr^c(S_X)`$, so, similarly, $`ZI(T)`$, as desired. This proves the theorem.

Depending on one’s taste, one may prefer to justify the construction of $`S_X`$ above by arguing that everything that one has to check to verify that the $`S_X`$ form a snug partition may be checked after a suitable contraction which reduces the question to the case where $`n=d+3`$, where we have already established the result.

## 10. The map $`g:S(n,d)B(n1,d)`$ is order-preserving

###### Lemma 10.1

Let $`STS(n,d)`$, and let $`S`$ and $`T`$ coincide outside the simplex $`\{a_1,\mathrm{},a_{d+2}\}_<`$. Then

$$I(S)=I(T)r(a_1,\mathrm{},a_{d+2})$$

where $``$ is disjoint union.

###### Demonstration Proof

For $`Ir(a_1,\mathrm{},a_{d+2})`$, one checks that $`c_I(S)=c_I(T)`$.

We now investigate $`I(S)r(a_1,\mathrm{},a_{d+2})`$ and $`I(T)r(a_1,\mathrm{},a_{d+2})`$. This is a straightforward check using the definition of $`g`$, together with the fact that $`S`$ contains the snug rectangles $`r(a_1,\mathrm{},\widehat{a}_i,\mathrm{},a_{d+2})`$ for $`i`$ with the opposite parity to $`d`$, while $`T`$ contains those for $`i`$ having the same parity as $`d`$.

From this lemma we obtain a corollary which amounts to giving a definition of $`g`$ analogous to Definition 3 of $`f`$, relying as it does to define $`I(S)`$ on the choice of a maximal chain from $`\widehat{0}_d`$ to $`S`$.

###### Corollary

Let $`SS(n,d)`$. Choose an unrefinable chain $`\widehat{0}_d=T_0T_1\mathrm{}T_r=S`$. Let $`R_i`$ be the snug rectangle in $`\left(\genfrac{}{}{0pt}{}{[n1]}{d+1}\right)`$ corresponding to the simplex where $`T_{i1}`$ and $`T_i`$ differ. Then

$$I(S)=\underset{i=1}{\overset{r}{}}R_i.$$

We will have occasion to consider a special type of linear order on the elements of a snug rectangle in $`\left(\genfrac{}{}{0pt}{}{[n1]}{d+1}\right)`$. We say that such an order is rectangular if

$`(x_1,\mathrm{},x_i,\mathrm{},x_{d+1})>(x_1,\mathrm{},x_i+1,\mathrm{},x_{d+1})\text{ if }(d+1)i\text{ is even}`$ $`1`$
$`(x_1,\mathrm{},x_i,\mathrm{},x_{d+1})<(x_1,\mathrm{},x_i+1,\mathrm{},x_{d+1})\text{ if }(d+1)i\text{ is odd}`$
###### Lemma 10.2

There is a unique rectangular order on $`r(a_1,\mathrm{},a_{d+2})`$ up to transposition of adjacent pairs of $`d+1`$-tuples not both in any $`d+1`$-packet.

###### Demonstration Proof

It is clear that there are rectangular orders. Suppose that $`(x_1,\mathrm{},x_{d+1})`$ and $`(y_1,\mathrm{},y_{d+1})`$ are both in $`r(a_1,\mathrm{},a_{d+2})`$ and lie in some common $`d+1`$-packet. Then, by Lemma 8.2, there is some $`i`$ such that $`x_j=y_j`$ for $`ji`$. Thus, it’s clear that the order relation between $`(x_1,\mathrm{},x_{d+1})`$ and $`(y_1,\mathrm{},y_{d+1})`$ is determined by (1) together with transitivity. Thus any two rectangular orders differ only by transpositions of adjacent pairs of elements not both occurring in a common $`d+1`$-packet.

We now prove the main result of this section:

###### Theorem 10.1

The map $`g:S(n,d)B(n1,d)`$ is order-preserving.

###### Demonstration Proof

The statement is clear for $`d=0`$ and $`d=1`$, so we may assume that $`d>1`$. Let $`ST`$ in $`S(n,d)`$. It suffices to show that $`g(S)>g(T)`$ in $`B(n1,d)`$.

Since $`ST`$, there is some simplex $`A=\{a_1,\mathrm{},a_{d+2}\}_<`$ such that $`S`$ and $`T`$ differ in that $`S`$ contains the top facets of $`A`$ and $`T`$ contains the bottom facets. Lemma 10.1 tells us that

$$I(S)=I(T)r(a_1,\mathrm{},a_{d+2}).$$

The fact that $`I(S)`$ and $`I(T)`$ are consistent implies that there are admissible orders on $`\left(\genfrac{}{}{0pt}{}{[n1]}{d+1}\right)`$ which have each of $`I(T)`$ and $`I(S)`$ as initial segments. We must show that there is a single admissible order which has both as initial segments.

In fact, we prove something more:

###### Lemma 10.3

Let $`d>1`$. Let $`STS(n,d)`$. Let $`\alpha `$ be an order of $`I(T)`$ such that any initial subsequence is consistent. Let $`\gamma `$ be an order of $`\left(\genfrac{}{}{0pt}{}{[n1]}{d+1}\right)I(S)`$ such that any final subsequence is consistent. Then $`\alpha \beta \gamma `$ is an admissible order on $`\left(\genfrac{}{}{0pt}{}{[n1]}{d+1}\right)`$ iff $`\beta `$ is rectangular.

###### Demonstration Proof

We begin by remarking that there are necessarily orders $`\alpha `$ and $`\gamma `$ as in the statement of the theorem (since $`\widehat{0}_d`$ is the unique minimal element and $`\widehat{1}_d`$ the unique maximal element of $`B(n1,d)`$, as shown in \[MS\]).

Let $`\beta `$ be a rectangular order on $`r(a_1,\mathrm{},a_{d+2})`$. Let us consider the $`d+1`$-packet $`P`$ of $`d+1`$-subsets of $`X=\{x_1,\mathrm{},x_{d+2}\}_<`$. We wish to check that it occurs in $`\alpha \beta \gamma `$ in either lexicographic order or its opposite. This is certainly true if the $`d+1`$-packet intersects $`r(a_1,\mathrm{},a_{d+2})`$ in at most one $`d+1`$-set. So suppose it intersects it in more than one place. Then by Lemma 8.2, there is some $`i`$ such that $`Xx_i`$ and $`Xx_{i+1}`$ both lie in $`r(a_1,\mathrm{},a_{d+2})`$, and this is the entire intersection of $`P`$ with the rectangle.

By the consistency of $`I(T)`$ and $`I(S)`$, the intersection of $`I(T)`$ and $`\left(\genfrac{}{}{0pt}{}{[n1]}{d+1}\right)I(S)`$ with $`P`$ must be $`\{X\{x_j\}j<i\}`$ and $`\{X\{x_j\}j>i+1\}`$, but not necessarily respectively. One now checks that superconsistency of $`I(T)`$ implies that if $`di`$ is odd then $`I(T)`$ contains the former, and if $`di`$ is even then $`I(T)`$ contains the latter, which imply that the the elements of $`P`$ not in $`r(a_1,\mathrm{},a_{d+2})`$ occur in reverse order if $`di`$ is odd, and lex order if $`di`$ is even. The rectangularity of $`\beta `$ ensures that the elements of $`r(a_1,\mathrm{},a_{d+2})P`$ also occur in the same order.

On the other hand, if $`\beta `$ fails to satisfy any of the conditions (1), it is clear that there is a $`d+1`$-packet which intersects $`r(a_1,\mathrm{},a_{d+2})`$ in two places, and these two elements do not occur in the order which would agree with the order on the rest of the $`d+1`$-packet. Thus, if $`\beta `$ is not rectangular, $`\alpha \beta \gamma `$ is not admissible.

Theorem 10.1 now follows from Lemma 10.3.

## 11. The map $`g:S(n,d)B(n1,d)`$ is a poset embedding

In this section, we investigate the map $`fg`$ and show that it coincides with the “extension” map defined in \[Ra1\]. We then show that $`g`$ is a poset embedding.

We now recall Rambau’s definition of extension (with a trivial modification to suit our conventions). Let $`SS(n,d)`$. Then by definition $`\widehat{S}`$, the extension of $`S`$, is

$`\widehat{S}=\{A\{0\}`$ $`AS\}`$
$`\{(x,x+1,a_2,\mathrm{},a_{d+1})\{a_1,\mathrm{},a_{d+1}\}_<A,a_1xa_22\}`$
It is a nice application of the theory of snug partitions to check that $`\widehat{S}S([0,n],d+1)`$.

There is a simple geometrical idea motivating this definition. Let $`SS(n,d)`$, thought of as triangulations of $`C(n,d)`$. $`S`$ defines a hypersurface $`\mathrm{\Gamma }_S`$ in $`C(n,d+1)`$. Add a new point on the moment curve which precedes all the vertices of $`C(n,d)`$, and label it 0. All the faces of $`\mathrm{\Gamma }_S`$ are visible from 0. $`\widehat{S}`$ consists of all the simplices formed by joining $`0`$ to simplics of $`S`$, together with a canonical way to fill in the remainder of $`C([0,n],d+1)`$.

It is clear either from this description, or directly from the definition, that, as is shown in \[Ra1\], $`\mathrm{lk}_0(\widehat{S})=S`$.

###### Proposition 11.1

For $`SS(n,d)`$, $`f(g(S))=\widehat{S}`$.

###### Demonstration Proof

One checks, using Definition 2 of $`f`$, that each of the simplices of $`\widehat{S}`$ appears in $`f(g(S))`$.

Since both $`f`$ and $`g`$ are order-preserving, we recover the result from \[Ra1\] that the map $`S\widehat{S}`$ is order-preserving.

###### Theorem 11.1

The map $`g:S(n,d)B(n1,d)`$ is a poset embedding

###### Demonstration Proof

Suppose that $`S,TS(n,d)`$, and $`g(S)>g(T)`$ in $`B(n1,d)`$. Then, since $`f`$ is order preserving, $`f(g(S))>f(g(T))`$. So $`\widehat{S}>\widehat{T}`$, so $`S=\mathrm{lk}_0\widehat{S}>\mathrm{lk}_0\widehat{T}=T`$.

Thus $`g`$ is a poset embedding.

## 12. Alternative definitions of $`g`$

In this section we show that $`g`$ satisfies two alterative definitions, including an analogue of Definition 1 of $`f`$. First, we give another combinatorial construction, for which we need a lemma.

###### Lemma 12.1

The unique ascending order on the simplices of the triangulation $`\widehat{0}`$ of $`C(d+2,d)`$ is $`[d+2]\{d+2\},[d+2]\{d\},\mathrm{}`$. The unique ascending order on the simplices of the triangulation $`\widehat{1}`$ is $`\mathrm{},[d+2]\{d1\},[d+2]\{d+1\}`$.

###### Demonstration Proof

This can be seen directly, by examining the intersections of pairs of simplices in the two triangulations, or by observing that an ascending order on simplices of a triangulation of $`C(d+2,d)`$ corresponds to an ascending chain in $`C(d+2,d1)`$, which we have studied in the proof of Proposition 9.1.

###### Proposition 12.1

Let $`SS(n,d)`$. Fix an ascending order on the simplices of $`S`$, say, $`A_1,\mathrm{},A_r`$. Consider the order on $`\left(\genfrac{}{}{0pt}{}{[n1]}{d}\right)`$ which consists of the element of $`r(A_1)`$ followed by the elements of $`r(A_2)`$, etc., where the elements within any $`r(A_i)`$ are written in a rectangular order. This order is admissible, and the element of $`B(n,d)`$ which it defines is $`g(S)`$.

###### Demonstration Proof

Let $`\pi `$ denote an order on $`\left(\genfrac{}{}{0pt}{}{[n1]}{d}\right)`$ as in the statement of the proposition. Let $`X=\{x_1,\mathrm{},x_{d+1}\}_<\left(\genfrac{}{}{0pt}{}{[n1]}{d+1}\right)`$. Let $`P`$ denote the $`d`$-packet of $`d`$-subsets of $`X`$. Lemma 8.2 describes the two possible sets of non-empty intersections of snug rectangles in $`r(S)`$ with $`P`$, depending on whether or not $`XI(S)`$. An ascending order on simplices of $`S`$ restricts to an ascending order on the simplices of $`S`$ which survive in $`c_X(S)`$. Lemma 12.1 describes the unique ascending order on the simplices of $`c_X(S)`$. Thus, the order on $`P`$ is determined by Lemma 12.1 and rectangularity, and one checks that this implies that the elements of $`P`$ occur in lexicographic order if $`XI(S)`$ and in the reverse of lexicographic order if $`XI(S)`$.

We now prove the equivalence of a definition of $`g`$ analogous to the Definition 1 of $`f`$.

###### Proposition 12.2

Let $`d2`$, and $`SS(n,d)`$. Fix an ascending order on the simplices of $`S`$. Let $`\widehat{0}=T_0T_1\mathrm{}T_r=\widehat{1}`$ be the corresponding chain in $`S(n,d1)`$. Refine the chain $`g(\widehat{0})<g(T_1)<\mathrm{}<g(\widehat{1})`$ to a maximal chain in $`B(n1,d1)`$. Then $`g(S)`$ is the element of $`B(n1,d)`$ corresponding to that chain.

###### Demonstration Proof

Refining the chain as in the statement of the proposition amounts to finding an admissible ordering on $`\left(\genfrac{}{}{0pt}{}{[n1]}{d}\right)`$ such that $`I(T_i)`$ is an initial subsequence for all $`i`$. By Lemma 10.3, there is a unique element of $`B(n1,d)`$ which corresponds to any such order. This is the element associated to the admissible order on $`\left(\genfrac{}{}{0pt}{}{[n1]}{d}\right)`$ defined in Proposition 12.1, and therefore by that proposition, it coincides with $`g(S)`$.

Interestingly, this definition fails for $`d=0,1`$. Here, different refinements of the chain of $`g(T_i)`$ yield different elements of $`B(n1,d)`$ (though it is of course easy to specify which refinement to use).

## 13. Further Directions

We would like to understand the fibres of $`f`$ better. Perhaps, as a first step, one might study the fibres of $`\mathrm{lk}_0f`$, since the fibre of $`\mathrm{lk}_0f`$ over $`S`$ has a distinguished element, namely $`g(S)`$. (Contrary to what one might hope, $`g(S)`$ is neither always minimal nor always maximal in the fibre.)

We would also like to see the question of the surjectivity of $`f`$ settled.

The map $`gf:B(n,d)B([0,n],d+1)`$ is a map which does not seem to have been studied before, and may prove of interest.

The motivation for \[KV\] was from the still-developing theory of $`n`$-categories. We hope that our results may have some application in this area. In particular, according to some definitions (see \[KV\], \[St2\]), there is an $`n`$-category $`\mathrm{\Delta }_n`$ associated to the $`n`$-simplex, and an $`n`$-category $`I_n`$ associated to the $`n`$-cube. It appears that the map $`g`$ defines a map of $`n`$-categories from $`\mathrm{\Delta }_n`$ to $`I_n`$ (as the map $`f`$ was shown in \[KV\] to define a map from $`I_n`$ to $`\mathrm{\Delta }_{n+1}`$).

The order complex of $`B(n,d)`$ is homotopic to a sphere of dimension $`nd2`$ \[Ra2\]. The order complex of $`S(n,d)`$ is homotopic to a sphere of dimension $`nd3`$ \[ERR\]. Thus, the maps $`g`$ and $`fg`$ induce maps between order complexes which are homotopy equivalent. It seems likely that these maps are homotopy equivalences. (The map $`f`$ does not induce a map on order complexes because it takes non-minimal elements to $`\widehat{0}`$.)

We would also like to understand the homotopy type of intervals in these posets, or, more restrictedly, the Möbius functions of these posets. There is an interesting conjectural description for both, see \[Re\]. Perhaps the existence of the new map $`g`$ will help, at the very least, to connect the questions for the higher Stasheff-Tamari posets and the higher Bruhat orders more closely together.

## Acknowledgements

I would like to thank Vic Reiner for comments on an earlier draft of this paper, and Alex Postnikov for suggesting that I investigate the vertex figure of an element of $`B(n,d)`$ at $`(1,\mathrm{},1)[1,1]^n`$.