Monotone Paths on Cross-Polytopes

The vertex generic linear functionals on the cross-polytope are precisely those with distinct nonzero values of coefficients $a_{i}$ for each $e_{i}$. Furthermore, they each map $e_{i}$ to $a_{i}$, where up to a change in indices, $|a_{1}|<|a_{2}|<\dots<|a_{n}|$. Then, by applying the reflection map taking $e_{i}\mapsto-e_{i}$, we may assume that each $a_{i}$ is positive. The cross-polytope $\diamond^{n}$ has vertices $\pm e_{i}$, so under this map, the vertices are ordered such that $-e_{i}<e_{i}$ for all $i\in[n]$ and $e_{j}<e_{k}$ for all $j<k$ in $[n]$. Hence, up to a permutation and reflection, we always obtain the same vertex ordering. Since these symmetries are linear, by Lemma $2.3$ from [5], the affine isomorphism from the cross-polytope to itself induces an affine isomorphism of the monotone path polytopes. ∎

For both directions, by Lemma 3.1, we may assume without loss of generality that the linear functional $\ell:\mathbb{R}^{n}\to\mathbb{R}$ given by $\ell(e_{i})=a_{i}$ satisfies $0<a_{i}<a_{j}$ for all $i,j\in[n]$ with $i<j$.

Suppose that a coherent cellular string contains $-e_{i}$ and $e_{i}$ as vertices in possibly distinct cells. Then, by the definition of coherence, there exists a projection $\pi:\diamond^{n}\to\mathbb{R}^{2}$ that takes $-e_{i}$ and $e_{i}$ to possibly distinct lower edges of some polygon, where $\pi=\ell\times\varphi$ for some linear functional $\varphi:\mathbb{R}^{n}\to\mathbb{R}$. Since $\pi(-e_{i})$ and $\pi(e_{i})$ lie on the lower edges, and $-e_{n}$ and $e_{n}$ are minimal and maximal respectively for $\varphi$, $\pi(e_{i})$ and $\pi(-e_{i})$ must lie below the line segment from $\pi(-e_{n})$ to $\pi(e_{n})$. It follows that the slope from $\pi(-e_{n})$ to $\pi(-e_{i})$ must be less than the slope from $\pi(-e_{n})$ to $\pi(e_{n})$. Similarly, the slope from $\pi(e_{i})$ to $\pi(e_{n})$ must be greater than the slope from $\pi(-e_{n})$ to $\pi(e_{n})$. Thus, we must have

a contradiction.

Suppose instead we have a cellular string such that the set of vertices contained in some cell has only one pair of antipodes. The vertices contained in the cellular string may be partitioned into the subsets of positive and negative basis vectors: $S_{+}\subseteq\{e_{1},e_{2},\dots,e_{n}\}$ and $S_{-}\subseteq\{-e_{1},-e_{2},\dots,-e_{n}\}$. Let $S_{0}=\{e_{i}:-e_{i},e_{i}\notin S_{+}\cup S_{-}\}$, the set of $e_{i}$ such that $\pm e_{i}$ does not appear in the path. Then, by our assumption that the path only contains a single pair of antipodes $-e_{n}$ and $e_{n}$, we must have

It follows that $(S_{+}\cup-S_{-}\cup S_{0})\setminus\{-e_{n}\}=\{e_{1},e_{2},\dots,e_{n}\}$ and is, in particular, linearly independent. Let $F_{1}<F_{2}<\dots<F_{k}$ denote the sequence of faces in the cellular string. Let $e_{-i}=-e_{i}$ and $a_{-i}=-a_{i}$ for $i\in\pm[n]$. To prove coherence, we must choose $\varphi:\mathbb{R}^{n}\to\mathbb{R}$ such that $\pi=\ell\times\varphi$ takes endpoints of the cellular string to lower vertices of $\pi(\diamond^{n})$ and vertices of cells to the interior of the edge between the endpoints. We will construct such a choice of $\varphi$ inductively first on the endpoints of the string and then interpolate to find the value on the interior points.

By linear independence, we may define $\varphi$ however we choose for each vertex that appears in the cellular string. Let $e_{b_{j}}$ and $e_{c_{j}}$ denote the minimal and maximal vertices of $F_{j}$. Define $\varphi(e_{n})=0$. Define $\varphi(e_{c_{1}})$ to be $-(a_{c_{1}}+a_{n})$. Then the slope from $(-a_{n},\varphi(-e_{n}))$ to $(a_{c_{1}},\varphi(a_{c_{1}}))$ will be precisely $-1$. Define $\varphi$ inductively so that the slope from $(a_{b_{j}},\varphi(e_{b_{j}}))$ to $(a_{c_{j}},\varphi(e_{c_{j}}))$ is $\frac{-1}{j}$ for all $1\leq j<k$. For each remaining vertex $v$ in each $F_{j}$, define $\varphi$ so that $\pi(v)$ lies on the line segment from $\pi(e_{b_{j}})$ to $\pi(e_{c_{j}})$. Such a choice is always possible by linear independence. Finally, define $\varphi$ to be $0$ for all vertices in $S_{0}$.

It remains to show that $\pi$ then satisfies the properties from Definition 2.2. Observe that, since $\varphi(-e_{n})=-\varphi(e_{n})=0$ and the slope between consecutive endpoints of the string is negative, $\varphi$ is negative for each endpoint of the cellular string other than $-e_{n}$ and $e_{n}$. Thus, by interpolating, $\varphi$ must be negative for each vertex on the interior of a cell. For vertices $e_{i}$ not in the string, there are two cases. If $-e_{i}$ is in the string, then $\varphi(e_{i})=-\varphi(-e_{i})\geq 0$. Otherwise, $e_{i}\in S_{0}$, so $\varphi(e_{i})=0\geq 0$. Hence, all vertices $v$ not contained in some cell of the string must satisfy $\varphi(v)\geq 0$. Since $\varphi(-e_{n})=\varphi(e_{n})=0$, it follows that all vertices not in the string lie on or above the line segment from $\pi(-e_{n})$ to $\pi(e_{n})$.

Thus, the lower vertices of the polygon must be some subset of the vertices contained in the string. By construction, we defined the $F_{i}$ to each be mapped to an edge and so that the slope of each edge increases as $i$ increases. These edges yield a path from $\pi(-e_{n})$ to $\pi(e_{n})$. Since the slope is increasing, this path is the graph of a piece-wise linear convex function that lies below the line segment from $\pi(-e_{n})$ to $\pi(e_{n})$. It follows then that the convex hull of the path has vertices $\{\pi(e_{i}):e_{i}\text{ is an endpoint of the string}\}$. Furthermore, by construction once again, any vertex in a cell of the cellular string is mapped to the interior of the edge between the endpoints of that string. Hence, the projections of each $F_{i}$ are precisely the lower edges of the polygon meaning that the cellular string must be coherent by definition. ∎

In [5], they show that the fiber polytope is given by the minkowski sum of fibers of barycenters of the subdivision induced by the projection. In this case, the subdivision induced by the projection is trivial, so the monotone path polytope is given by $\ell^{-1}(0)$. In that case, we are taking a slice of the Cayley sum of $\Delta_{d-1}$ and $-\Delta_{d-1}$, so from either explicit computation or the Cayley trick as in [15], we find that the resulting MPP is $\Delta_{d-1}-\Delta_{d-1}$. ∎

Recall that any two non-antipodal points of the cross-polytope are connected by an edge. It follows then that the coherent monotone paths consists of choices $e_{i},-e_{i}$ or neither to include in our sequence of points. That gives $3^{n-1}$ possible choices. Since we have to include at least $1$ element between $-e_{n}$ and $e_{n}$, we obtain that $\diamond^{n}$ has precisely $3^{n-1}-1$ coherent monotone paths. Since the vertices of $MPP_{\varphi}(\diamond^{n})$ correspond to coherent monotone paths, $MPP_{\varphi}(\diamond^{n})$ has precisely $3^{n-1}-1$ vertices. ∎

Use the characterization of coherent monotone paths in Theorem 3.2 in combination with Theorem $5.3$ from [5], and the result is immediate. ∎

Apply Lemma $2.3$ from [5] as stated in Section 2 to the result of Theorem 1.1(a). ∎

To find the facet defining relations for the MPP, we follow the method outlined by Ziegler in Section $9.1$ of [23]. Namely, the facet defining inequalities are obtained from the linear functional that yields the polygon whose lower vertices correspond to maximal coherent subdivisions. That is, for such a linear functional $\varphi$, the inequality is given by $\varphi(x)\geq\varphi(v)$, where $v$ is the vertex that is minimized by $\varphi$ on the polygon corresponding to the maximal coherent cellular string. From the combinatorial characterization in Theorem 1.1(b), the facets correspond precisely to the maximal intervals in the sign poset. Maximal intervals are obtained from starting with a choice of a separating vertex $e_{i}$ and choosing a maximal length monotone path through $e_{i}$. In the notation from the proof of Theorem 3.2, these are precisely the subdivisions corresponding $F_{1}<F_{2}$ such that $\pm F_{1}\cup\pm F_{2}=\{k:k\in\pm[n-1]\}$, where we remove $e_{n}$ from $F_{2}$ and $-e_{n}$ from $F_{1}$ and identify each $e_{i}$ with $i$. To obtain a lifting functional, by following the proof of Theorem 3.2, we define

Then for the remaining vertices in $F_{1}$ we linearly interpolate between $0$ and $-a_{i}-a_{n}$. For the vertices in $F_{2}$, we provide a similar interpolation. In particular, $\varphi(e_{k})=-a_{k}-a_{n}$ if $k\in F_{1}$ and $\varphi(e_{k})=\frac{a_{i}+a_{n}}{a_{n}-a_{i}}(a_{k}-a_{n})$ if $k\in F_{2}$

We denote any functional of this form as $\varphi_{i,\varepsilon}$, where $i\in\pm[n-1]$ is the choice of the splitting vertex, and $\varepsilon:[n-1]\to\pm 1$ denotes the sign sequence of the vertices. Then $F_{1}=\{k:\varepsilon(k)k\leq i\}$ and $F_{2}=\{k:\varepsilon(k)k\geq i\}$, which yields the result. ∎

By Theorem $2.1$ of [5], the face lattice of the monotone path polytope corresponds to the poset of coherent cellular strings under refinement. Note that a coherent cellular string is uniquely determined by two pieces of data: its endpoints and the vertices included in the cells between each endpoint. These two pieces of data may be interpreted as two monotone paths, the one with vertices given by the set of endpoints, $E$, of the cellular string and the on given by $V$, the set of vertices that appear anywhere in the cellular string. Clearly $E\subseteq V$, which translates via the bijection to $V$ and $E$ being comparable. Furthermore, the vertices contained in the cellular string correspond exactly to all monotone paths with a set of vertices $S$ such that $E\subseteq S\subseteq V$. Hence, the partial order of inclusion of faces via this bijection is equivalent to the partial order given by inclusion of intervals.

Note that each interval $I=[a,b]$ in $\{0,-1,1\}^{n-1}\setminus\{\mathbf{0}\}$ is Boolean. Furthermore, $\text{conv}([a,b])$ is isomorphic to $\text{conv}([a,b]-a)=\text{conv}([\mathbf{0},b-a])$, where $\mathbf{0}$ is adjoined in the natural way to the partial order. Let $k$ be the length of the interval. Then $b-a$ will have precisely $k$ nonzero entries of either $0$’s or $1^{\prime}$s. Let $A$ be the linear map defined by $A(e_{i})=\sigma(i)e_{i}$, where $\sigma(i)$ denotes the sign of $e_{i}$ in $b-a$. Let $S=\{i\in[n-1]:\sigma(i)\neq 0\}$. Then $A([0,b-a])=\left[0,\sum_{s\in S}e_{s}\right]$. By construction, $A$ is then an isometry taking $\text{conv}(I)$ to the unit cube.

Hence, each interval corresponds to a unit cube of dimension $\leq n-2$ with vertices contained in $\{\pm 1,0\}^{n-1}\setminus\{\mathbf{0}\}$. The converse is similar, since each unit cube has vertices corresponding to an interval in the poset $\{+,-,0\}^{n-1}\setminus\{\mathbf{0}\}$ ∎

Note that the vertices of $C_{n}+\diamond^{n}$ are obtained precisely by adding the unique maximal vertices on each for a linear functional. Let $\ell$ be a linear functional. Then the max on $\diamond^{n}$ is the vertex corresponding to the coordinate of maximum absolute value together with the corresponding sign, and the max on $C_{n}$ returns the subset with $1$’s for positive elements and $-1$’s for negative elements. The element of maximum absolute value could either be positive or negative.

The resulting polytope has vertices $\{B_{d}\left(2e_{1}+\sum_{i=2}^{d}e_{i}\right)\}$, where $B_{d}$ is the set of signed permutation matrices. Let $S\in\{+,-,0\}^{n}\setminus\{\mathbf{0}\}$. Then $S$ induces a partitions of $[n]$ into $S_{+}\cup S_{-}\cup S_{0}$, and there is a naturally associated linear functional $\varphi_{S}$ given by $\sum_{i\in S_{+}}e_{i}^{T}-\sum_{j\in S_{-}}e_{j}^{T}.$ The vertices maximized by $\varphi_{S}$ are precisely

These vectors span the affine hyperplane given by

Thus, each sign vector $\varphi_{S}$ corresponds to a facet of the resulting polytope. Let $\varphi$ be a linear functional. Then any vertex maximized by that linear functional would also be maximized by the linear functional with the same sign pattern. Hence, the sign vectors induce all of the facets of $C_{n}+\diamond^{n}$, which gives us a polyhedral formulation of this polytope.

Namely, for any partition $S_{+}\cup S_{-}\cup S_{0}$ of $n$, we must have

These are precisely the relations given by maximizing the sign functionals. Observe that if a sign vector contains $0$’s, then any choice of $\pm e_{i}$ for $i\in S_{0}$ is allowable for a vertex in that facet. Furthermore, if two facets have distinct positive sets or negative sets, then they cannot intersect, since that imposes the sign of $e_{i}$ for any vertex in the set. It follows that two facets intersect if and only if their corresponding sign vectors are comparable. In particular, $m$-dimensional faces correspond exactly to intervals of sign vectors in the poset of length $n-m$. It follows then that the face lattice of this polytope is isomorphic to the lattice of intervals of the sign poset under reverse inclusion. Hence, we have $(C_{n-1}+\diamond^{n-1})^{\Delta}$ and $\text{MPP}_{\varphi}(\diamond^{n})$ are combinatorially equivalent. ∎

From Theorem 1.1(b), faces correspond exactly to elements of the poset of intervals in the sign poset. Namely, they are identified precisely by pairs of elements of comparable elements of the poset. An $m$-face corresponds to pairs of elements of distance $m$ from each other. That is one has $k$ nonzero entries, and the other has $k+m$ nonzero entries including the $k$ nonzero entries of the starting point. Thus, the faces correspond to flags of length two of subsets of $n-1$ of subsets of size $k$ and $k+m$ counted by $\binom{n-1}{k,m,n-k-m-1}$ together with $2^{k+m}$ choices of signs for each vertex contained in the flag. Then we have that

∎

Recall that $\diamond^{n}$ is simplicial. It follows that a polygonal flip either deletes a vertex from a path or adds a single, new vertex. Deleting or adding a vertex corresponds to changing a $1$ or $-1$ to a $0$ or a $0$ to a $1$ or $-1$ in the sequence bijection from Corollary 3.5. The connectivity of $\diamond^{n}$ allows us to perform this operation for any element of the sequence. Two sequences of $1$’s, $0$’s, and $-1$’s are at distance $1$ in the Taxi-cab metric if and only if they agree on all but one entry in which one is a $0$ and the other is a $-1$ or $1$, which yields the result. ∎

By the triangle inequality,

Since each step along an edge can change the distance by at most one, we have the diameter is at least $2(n-1)$. To see that it is at most $2(n-1)$ may be seen by taking two vectors and changing the coordinates by $\pm 1$ until one vector equals the other. Each coordinate change represents a single step, and the path requires at most $2(n-1)$ coordinate changes. The only detail is avoiding the origin, and that is also easy. ∎

A monotone path corresponds to a subsequence $s_{1},s_{2},\dots,s_{m}$ of

such that $s_{k}+s_{k+1}\neq 0$, since all vertices are connected to all vertices other than their antipodes. There are $2^{2(n-1)}-1$ non-empty subsets of $\{e_{i}:i\in\{\pm 1,\pm 2,\dots,\pm n-1\}$. Then $2^{2(n-2)}$ of those subsets include $-e_{1},e_{1}$, $2^{2(n-3)}$ include $-e_{2},e_{2}$ but neither of $-e_{1},e_{1}$, and in general $2^{2(n-1-k)}$ include $-e_{k},e_{k}$ but none of $e_{j}$, where $|j|<|k|$. Hence, one may easily verify via standard results for geometric series, the resulting number of possible sequences is

For the diameter of the flip graph, since $\diamond^{n}$ is simplicial, two monotone paths are adjacent if and only if they differ by the addition or removal of a single vertex. A vertex may only be added or removed if it does not introduce consecutive antipodal points. Note that, given these restrictions, the distance between the path given by $e_{1}$ and the path $(-e_{n-1},-e_{n-2},\dots,-e_{1},e_{2},e_{3},\dots,e_{n})$ is at least $2(n-1)$. By starting with removing all negative vertices starting with $-e_{n-1}$ and ending with $-e_{1}$ and then adding $e_{1}$ and removing $e_{2}$ through $e_{n}$ we achieve a sequence of flips going between these paths of length precisely $2(n-1)$. Hence, the distance between those points is precisely $2(n-1)$.

Let $e_{s_{i}}$ and $e_{t_{j}}$ be two different paths. Let $s_{-}$ and $s_{+}$ denote the maximal negative element and minimal positive element of $s$ respectively. define $t_{-}$ and $t_{+}$ similarly. If $s_{-}=t_{-}$ and $s_{+}=t_{+}$, we may go from $s$ to $t$ by adding elements from $t$ that are not in $s$ to $s$ and taking away elements from $s$ that are not in $t$. Such a path will have length at most $2(n-2)$.

If $s_{-}<t_{-}$ and $s_{+}=t_{+}$, then we may add $t_{-}$ to $s$ and follow the same strategy. This will result in a sequence of moves of length at most $2(n-2)+1$. A similar idea works for any of the possible cases in which $s_{-}=t_{-}$ or $s_{+}=t_{+}$.

Suppose that $s_{-}<t_{-}$ and $s_{+}<t_{+}$. If $t_{-}\neq-s_{+}$, we may add $t_{-}$ to the list $s_{-}$. Then we may follow the same strategy for the remaining list keeping $s_{+}$ and $t_{-}$. Then, at the end, we remove $s_{+}$. The result must take fewer that $2(n-2)+2\leq 2(n-1)$ moves. Suppose instead that $s_{-}<t_{-}=-s_{+}<s_{+}<t_{+}$. First modify all elements of $s$ greater that $s_{+}$ to agree with $t$. If $t_{+}=-s_{-}$, remove $t_{+}$. Otherwise, leave it. In both cases, add $t_{-}$, add $t_{+}$ back and modify all elements $<t_{-}$ to agree with $t$. The result takes $\leq 2(n-2)-1+3=2(n-1)$ moves, since $e_{1}<t_{+}$.

The only remaining case is that $s_{-}<t_{-}$ and $s_{+}>t_{+}$. In that case, add $t_{-}$ and $t_{+}$ to $s$ and make the required changes. The result takes fewer than $2(n-2)+2$ moves. Hence, the diameter of the flip graph is $2(n-1)$.

The longest distance to the nearest coherent path for a monotone path may be computed similarly. Start with a path $s$ with $s_{-}$ and $s_{+}$ defined as before. If $s_{+}<-s_{-}$, remove all parts of antipodal pairs after $s_{+}$. Otherwise, remove all parts of antipodal pairs before $s_{-}$. Since there are at most $n-2$ elements before $s_{-}$ and $s_{+}$, the distance to the nearest coherent path is at most $n-2$. This bound is attained for the path $(-e_{n-1},-e_{n-2},\dots,-e_{1},e_{2},e_{3},\dots,e_{n-1})$. ∎