# Triangulations, Order Polytopes, and Generalized Snake Posets

Matias von Bell  Department of Mathematics
University of Kentucky
http://www.ms.uky.edu/~mkvo222/<EMAIL_ADDRESS>,  Benjamin Braun
Department of Mathematics
University of Kentucky
https://sites.google.com/view/braunmath/<EMAIL_ADDRESS>,  Derek
Hanely  Department of Mathematics
University of Kentucky
https://math.as.uky.edu/users/dwha232<EMAIL_ADDRESS>,  Khrystyna
Serhiyenko  Department of Mathematics
University of Kentucky
https://math.as.uky.edu/users/kse246<EMAIL_ADDRESS>,  Julianne
Vega  Department of Mathematics
Kennesaw State University
https://sites.google.com/view/julievega/<EMAIL_ADDRESS>,  Andrés R.
Vindas-Meléndez  Department of Mathematics
University of Kentucky
https://ms.uky.edu/ãrvi222<EMAIL_ADDRESS>and  Martha Yip  Department
of Mathematics
University of Kentucky
http://www.ms.uky.edu/~myip/<EMAIL_ADDRESS>
###### Abstract.

This work regards the order polytopes arising from the class of generalized
snake posets and their posets of meet-irreducible elements. Among generalized
snake posets of the same rank, we characterize those whose order polytopes
have minimal and maximal volume. We give a combinatorial characterization of
the circuits in these order polytopes and then conclude that every
triangulation is unimodular. For a generalized snake word, we count the number
of flips for the canonical triangulation of these order polytopes. We
determine that the flip graph of the order polytope of the poset whose lattice
of filters comes from a ladder is the Cayley graph of a symmetric group.
Lastly, we introduce an operation on triangulations called twists and prove
that twists preserve regular triangulations.

The authors thank Raman Sanyal for helpful discussions about triangulations of
order polytopes, and Paco Santos for helpful comments on a preliminary version
of this article. MB was partially supported by a University of Kentucky
Mathematics Steckler Fellowship. BB was partially supported by National
Science Foundation award DMS-1953785. DH was partially supported by National
Science Foundation award DUE-1356253. KS was partially supported by funding
from the University of Kentucky College of Arts and Sciences. ARVM was
partially supported by National Science Foundation Graduate Research
Fellowship DGE-1247392 and National Science Foundation KY-WV LSAMP Bridge to
Doctorate Fellowship HRD-2004710. MY was partially supported by Simons
Collaboration Grant 429920.

##  1\. Introduction

In 1986, Richard Stanley [20] introduced two geometric objects associated to a
finite partially ordered set, or _poset_ , known as the order polytope and the
chain polytope. Since then, the study of order polytopes has been an active
area of research, e.g., geometric and algebraic properties [6, 10, 11, 12,
13], connections between flow polytopes and order polytopes [15, 16], and
lattice-point enumeration [4, 14].

One of Stanley’s fundamental observations is that the arrangement given by all
hyperplanes of the form $x_{i}=x_{j}$ for $i\neq j$ induces a regular
unimodular triangulation of the order polytope for any poset. This
triangulation is known as the _canonical triangulation_ of an order polytope,
see Subsection 2.2. It is well-known that the set of all regular
triangulations of a polytope correspond to the vertices of its secondary
polytope, and that these triangulations are connected via flips; definitions
are given in Subsection 2.1 and further information can be found in [5].
Various triangulations of order polytopes have been constructed or considered,
often for special classes of posets. See, for example, Santos, Stump, and
Welker for products of chains [19], Féray and Reiner for non-unimodular
triangulations related to graph-associahedra [7], Reiner and Welker for graded
posets [18], Bränden and Solus for $\mathbf{s}$-lecture hall order polytopes
[2], disjoint unions of chains [5, Section 6.2], and others. However, the
general space of regular triangulations of an order polytope, i.e., the
$1$-skeleton of the secondary polytope of an order polytope, does not appear
to have been studied in detail and motivates our work.

Our contributions in this paper add to the literature on order polytopes and
further the study of the general space of regular triangulations of order
polytopes. Specifically, we investigate circuits, flips, and regular
triangulations of order polytopes arising from a certain class of posets,
called generalized snake posets. These posets are constructed recursively by
adding a square face at the bottom and gluing it to an edge of the previous
square. First, we prove results regarding the volumes of their corresponding
order polytopes. In particular, for generalized snake posets of the same rank,
Theorem 3.10 characterizes those with minimal and maximal normalized volumes.

Next, we turn our attention to the poset $Q$, whose lattice of filters is a
generalized snake poset $P$, and study the combinatorial properties of the
corresponding order polytope $\mathcal{O}(Q)$. Thus, the vertices of
$\mathcal{O}(Q)$ are given by the elements of $P$. In Theorem 4.5, we prove
that there exists a bijection between the set of nonempty connected induced
subgraphs associated to the faces of $P$ and the set of circuits of
$\mathcal{O}(Q)$. As a consequence, we obtain Theorem 4.12, which states that
every vertex of the secondary polytope of $\mathcal{O}(Q)$ corresponds to a
unimodular triangulation. The combinatorial characterization of the circuits
also implies that the canonical triangulation of $\mathcal{O}(Q)$ admits the
same number of flips as there are faces in $P$, see Theorem 5.1. Then, in
Theorem 5.2 we determine that the flip graph of the order polytope
$\mathcal{O}(Q)$, when $P$ is a ladder, is in fact the Cayley graph of a
symmetric group.

Finally, we introduce an action on the vertices of $P$ given by the so-called
twists. It extends to an action on regular triangulations, and in Theorem 5.8
we prove that twists of a canonical triangulation of $\mathcal{O}(Q)$ are
again regular triangulations. Moreover, twists preserve circuits of
$\mathcal{O}(Q)$, and hence they commute with applying flips, see Theorem 5.6.
In particular, this implies that twists give an action on the component of the
flip graph of $\mathcal{O}(Q)$ containing all regular triangulations.

The article is organized as follows. In Section 2, we review some background
and establish notation for triangulations and order polytopes. In Section 3,
we introduce the family of generalized snake posets $P$ and study volumes of
their corresponding order polytopes. The characterization of circuits of the
order polytope $\mathcal{O}(Q)$ of the poset of filters of $P$ is given in
Section 4. Section 5 is devoted to introducing twists, and then proving four
theorems regarding twists, flips, and triangulations of $\mathcal{O}(Q)$.
Lastly, in Section 6 we conclude the paper with conjectures for future work.

##  2\. Background and Notation

###  2.1. Triangulations

Our primary focus in this paper is the study of triangulations for a
particular family of order polytopes. We begin by providing the necessary
background for triangulations following the presentation in De Loera, Rambau,
and Santos [5, Section 2.4].

######  Definition 2.1.

Given a point configuration $\mathbf{A}\subseteq\mathbb{R}^{d}$, let
$\mathrm{conv}(\mathbf{A})$ denote the convex hull of $\mathbf{A}$. A
_triangulation_ of $\mathbf{A}$ is a collection $\mathcal{T}$ of $d$-simplices
all of whose vertices are points in $\mathbf{A}$ that satisfies the following
two properties:

  1. (1)

The union of all of these simplices equals $\operatorname{conv}(\mathbf{A})$.
(_Union Property_)

  2. (2)

Any pair of these simplices intersects in a (possibly empty) common face.
(_Intersection property_)

A triangulation is _unimodular_ if every simplex has normalized volume one. A
triangulation of a point configuration $\mathbf{A}\subseteq\mathbb{R}^{d}$ is
_regular_ if it can be obtained by projecting the lower envelope of a lifting
of $\mathbf{A}$ from $\mathbb{R}^{d+1}.$

######  Example 2.2.

Consider the polytope generated by the convex hull of the points $(0,0,0,0),$
$(1,0,0,0),$ $(1,1,0,0),(1,0,1,0),(1,1,1,0),$ and $(1,1,1,1)$. A triangulation
of this point configuration consists of the simplices:

$\displaystyle\sigma_{4231}$
$\displaystyle=\mathrm{conv}\\{(0,0,0,0),(1,0,0,0),(1,0,1,0),(1,1,1,0),(1,1,1,1)\\}$
$\displaystyle\sigma_{4321}$
$\displaystyle=\mathrm{conv}\\{(0,0,0,0),(1,0,0,0),(1,1,0,0),(1,1,1,0),(1,1,1,1)\\}.$

######  Definition 2.3.

A point configuration $\mathbf{A}$ with index set $J$ has _corank one_ if and
only if it has an affine dependence relation $\sum_{j\in
J}\lambda_{j}\mathbf{v}_{j}=0$ with $\sum_{j\in J}\lambda_{j}=0$ that is
unique up to multiplication by a constant. This affine dependence partitions
$J$ into three subsets:

$J_{+}:=\\{j\in J:\lambda_{j}>0\\},J_{0}:=\\{j\in J:\lambda_{j}=0\\},\text{
and }J_{-}:=\\{j\in J:\lambda_{j}<0\\}.$

In the case when $A$ has corank one, $J_{+}$ and $J_{-}$ are the only disjoint
subsets of $J$ with the property that their relative interiors intersect at
the point

$\sum\limits_{j\in J_{+}}\lambda_{j}\mathbf{v}_{j}=\sum\limits_{j\in
J_{-}}|\lambda_{j}|\mathbf{v}_{j},$

where the $\lambda_{j}$ are assumed to be normalized so that $\sum_{j\in
J_{+}}\lambda_{j}=\sum_{j\in J_{-}}|\lambda_{j}|=1$. The set $J_{+}\bigcup
J_{-}$ is called a _circuit_ in $J$ and the pair $(J_{+},J_{-})$ is called the
oriented circuit, or Radon partition , of $\mathbf{A}$.

######  Definition 2.4.

Let $\mathbf{A}$ be a point configuration with index set $J$. In general, a
subset $Z$ of $J$ is a _circuit_ if it is a minimal dependent set (that is, it
is dependent but every proper subset is independent). Let $(Z_{+},Z_{-})$ be a
partition of $Z$, such that $\mathrm{conv}(Z_{+})\cap\mathrm{conv}(Z_{-})$ is
nonempty. The partition $(Z_{+},Z_{-})$ is called an _oriented circuit_. We
say the circuit is of _type_ $(|Z_{+}|,|Z_{-}|)$.

From the circuits we can generate triangulations by using flips to locally
transform one triangulation into another.

######  Lemma 2.5.

[5, Lemma 2.4.2] Let $\mathbf{A}$ be a point configuration of corank one and
$J=J_{+}\cup J_{0}\cup J_{-}$ be its label set, partitioned by the unique
oriented circuit of $\mathbf{A}$. Then the following are the only two
triangulations of $\mathbf{A}:$

$\mathcal{T}_{+}=\\{J\smallsetminus\\{j\\}:j\in J_{+}\\},\text{ and
}\mathcal{T}_{-}=\\{J\smallsetminus\\{j\\}:j\in J_{-}\\}.$

######  Example 2.6.

We return to Example 2.2, where we considered the convex hull of the corank
one point configuration

$\mathbf{v}_{0}=(0,0,0,0),\mathbf{v}_{1}=(1,0,0,0),\mathbf{v}_{2}=(1,1,0,0),\mathbf{v}_{3}=(1,0,1,0),\mathbf{v}_{4}=(1,1,1,0),\mathbf{v}_{5}=(1,1,1,1).$

Since
$\mathbf{v}_{1}-\mathbf{v}_{2}-\mathbf{v}_{3}+\mathbf{v}_{4}=\mathbf{0}$, then
an oriented circuit is $J_{+}=\\{1,4\\}$ and $J_{-}=\\{2,3\\}$. The circuit
type is $(2,2)$ and the two triangulations are:

$\displaystyle\mathcal{T}_{+}$ $\displaystyle=\\{J\setminus\\{j\\}:j\in
J_{+}\\}=\\{\\{0,2,3,4,5\\},\\{0,1,2,3,5\\}\\}$ $\displaystyle\mathcal{T}_{-}$
$\displaystyle=\\{J\setminus\\{j\\}:j\in
J_{-}\\}=\\{\\{0,1,3,4,5\\},\\{0,1,2,4,5\\}\\}.$

Triangulation of $\mathbf{A}$ is a simplicial complex on $\mathbf{A}$. Recall
that an _(abstract) simplicial complex_ $\Delta$ on a set $X$ is a collection
of subsets of $X$ such that if $\sigma\in\Delta$ and $\tau\subseteq\sigma$,
then $\tau\in\Delta.$ The elements of a simplicial complex are called _faces_
and a subcomplex $\Delta^{\prime}$ of $\Delta$ is a subcollection of $\Delta$
which is also a simplicial complex. The _link_ of a face $\sigma\in\Delta$ is
the simplicial complex

$\mathrm{lk}_{\Delta}(\sigma)=\\{\tau\in\Delta:\sigma\cup\tau\in\Delta\text{
and }\sigma\cap\tau=\varnothing\\}.$

If $\Delta$ and $\Delta^{\prime}$ are simplicial complexes, then their join is
$\Delta\ast\Delta^{\prime}=\\{\sigma\cup\sigma^{\prime}:\sigma\in\Delta\text{
and }\sigma^{\prime}\in\Delta^{\prime}\\}$.

######  Theorem 2.7.

[5, Theorem 4.4.1] Let $\mathcal{T}_{1}$ and $\mathcal{T}_{2}$ be two
triangulations of a point configuration $\mathbf{A}$. Then $\mathcal{T}_{1}$
and $\mathcal{T}_{2}$ differ by a flip if and only if there is a circuit $Z$
of $\mathbf{A}$ such that

  1. (i)

They contain, respectively, the two triangulations $\mathcal{T}_{Z}^{+}$ and
$\mathcal{T}_{Z}^{-}$ of $Z$.

  2. (ii)

All the maximal simplices of $\mathcal{T}_{Z}^{+}$ and $\mathcal{T}_{Z}^{-}$
have the same link $\mathrm{L}$ in $\mathcal{T}_{1}.$

  3. (iii)

Removing the subcomplex $\mathcal{T}_{Z}^{+}\ast\mathrm{L}$ from
$\mathcal{T}_{1}$ and replacing it by $\mathcal{T}_{Z}^{-}\ast\mathrm{L}$
gives $\mathcal{T}_{2}.$

Two triangulations of $\mathbf{A}$ are _adjacent_ if they differ by a flip.
The set of all triangulations of $\mathbf{A}$, under adjacency by flips, forms
the _graph of triangulations_ , or _flip graph_ , of $\mathbf{A}$.

######  Example 2.8.

Continuing from Example 2.6 we demonstrate a flip from $\mathcal{T}_{+}$ to
$\mathcal{T}_{-}$. We have

$\mathcal{T}_{+}=\\{\\{0,2,3,4,5\\},\\{0,1,2,3,5\\}\\}\in\mathcal{T}.$

The circuit $Z=\\{1,2,3,4\\}$ has triangulations
$\mathcal{T}_{Z}^{+}=\\{\\{2,3,4\\},\\{1,2,3\\}\\}$ and
$\mathcal{T}_{Z}^{-}=\\{\\{1,3,4\\},\\{1,2,4\\}\\}$. The link of the simplices
is $\mathrm{L}=\\{\\{\mathbf{v}_{0},\mathbf{v}_{5}\\}\\}$, so flipping at the
circuit supported at $Z$ gives the triangulation

$\mathcal{T}_{Z}^{-}\ast\mathrm{L}=\\{\\{0,1,3,4,5\\},\\{0,1,2,4,5\\}\\}=\mathcal{T}_{-}.$

In Sections 4 and 5, we will take a look at the _secondary polytope_ whose
vertices are in bijection with regular triangulations of a point
configuration. Recall that we can define for each triangulation of a point
configuration $\mathbf{A}$ a GKZ-vector. As stated in the following
definition, the convex hull of the GKZ-vectors for $\mathbf{A}$ is the
secondary polytope. See De Loera, Rambau, and Santos [5, Section 5.1] for a
further discussion of secondary polytopes and GKZ-vectors.

######  Definition 2.9 (Secondary Polytope.).

For a point configuration $\mathbf{A}$ the secondary polytope of $\mathbf{A}$
is conv{$\varphi_{\mathbf{A}}(\mathcal{T})\mid\mathcal{T}\text{ triangulation
of }\mathcal{A}$}, where $\varphi_{\mathbf{A}}(\mathcal{T})$ represents the
GKZ-vector of $\mathcal{T}$ in $\mathbf{A}$.

The flip graph, which is the graph of all triangulations connected by flips,
is in general not connected, but the flip graph of regular triangulations is
connected and contains the 1-skeleton of the secondary polytope as a spanning
subgraph.

###  2.2. Order polytopes

Let $P$ be a partially ordered set on the set of elements
$[d]:=\\{1,\ldots,d\\}$. We abuse notation and write $P$ to denote the
elements of $P$. The _order polytope_ of $P$, introduced by Stanley [20], is
defined as

$\mathcal{O}(P)=\left\\{\mathbf{x}=(x_{1},\ldots,x_{d})\in[0,1]^{d}:x_{i}\leq
x_{j}\text{ for }i<_{P}j\right\\}.$

See Example 2.10. An _upper order ideal of $P$_, also called a _filter_ , is a
set $A\subseteq P$ such that if $i\in A$ and $i<_{P}j$, then $j\in A$. Let
$J(P)$ denote the poset of upper order ideals of $P$, ordered by reverse
inclusion. We use $\langle p_{1},...,p_{k}\rangle$ to denote the ideal
generated by elements $p_{1},...,p_{k}\in P$. Let
$\mathbf{e}_{1},\ldots,\mathbf{e}_{d}$ denote the standard basis vectors of
$\mathbb{R}^{d}$. For an upper order ideal $A\in J(P)$, define the
_characteristic vector_ $\mathbf{v}_{A}:=\sum_{i\in A}\mathbf{e}_{i}$. The
vertices of $\mathcal{O}(P)$ are given by

$V(\mathcal{O}(P))=\left\\{\mathbf{v}_{A}:A\in J(P)\right\\}.$

Define a hyperplane
$\mathcal{H}_{i,j}=\\{\mathbf{x}\in\mathbb{R}^{d}:x_{i}=x_{j}\\}$ for $1\leq
i<j\leq d$. The set of all such hyperplanes, called the $d$-dimensional braid
arrangement of type A, induces a triangulation $\mathcal{T}$ of
$\mathcal{O}(P)$ known as the _canonical triangulation_ , which has the
following three fundamental properties:

  1. (1)

$\mathcal{T}$ is unimodular,

  2. (2)

the simplices are in bijection with the linear extensions of $P$, so the
normalized volume of the order polytope is

$\operatorname{vol}(\mathcal{O}(P))=\\#\text{ of linear extensions of
}P,\text{ and}$

  3. (3)

the simplex corresponding to a linear extension $(a_{1},\ldots,a_{d})$ of $P$
is

$\sigma_{a_{1},...,a_{d}}=\left\\{\mathbf{x}\in[0,1]^{d}:x_{a_{1}}\leq
x_{a_{2}}\leq\cdots\leq x_{a_{d}}\right\\},$

with vertex set
$\\{\mathbf{0},\mathbf{e}_{a_{d}},\mathbf{e}_{a_{d-1}}+\mathbf{e}_{a_{d}},\ldots,\mathbf{e}_{a_{1}}+\cdots+\mathbf{e}_{a_{d}}=\mathbf{1}\\}.$

######  Example 2.10 (Order polytope and triangulations).

Let $P$ be the diamond poset

$4$$2$$3$$1$

Then $\mathcal{O}(P)=\\{(x_{1},x_{2},x_{3},x_{4})\in[0,1]^{4}:x_{4}\leq
x_{2}\leq x_{1}\text{ and }x_{4}\leq x_{3}\leq x_{1}\\}$. The six upper order
ideals of $P$ are

$\varnothing$$1$$2$$1$$3$$1$$1$$2$$3$$4$$2$$3$$1$

so $\mathcal{O}(P)$ is the convex hull of the points
$(0,0,0,0),(1,0,0,0),(1,1,0,0),(1,0,1,0)$, $(1,1,1,0)$ and $(1,1,1,1)$. The
poset $P$ has two linear extensions, namely $4,2,3,1$ and $4,3,2,1$. The
canonical triangulation of $\mathcal{O}(P)$ then consists of the following
simplices:

$\displaystyle\sigma_{4231}$
$\displaystyle=\mathrm{conv}\\{(0,0,0,0),(1,0,0,0),(1,0,1,0),(1,1,1,0),(1,1,1,1)\\}$
$\displaystyle\sigma_{4321}$
$\displaystyle=\mathrm{conv}\\{(0,0,0,0),(1,0,0,0),(1,1,0,0),(1,1,1,0),(1,1,1,1)\\}.$

##  3\. Generalized snake posets

We introduce the family of generalized snake posets $P(\mathbf{w})$, which are
distributive lattices with width two, and give a recursive formula for the
normalized volume of the order polytope of $P(\mathbf{w})$. For generalized
snake posets of the same rank, we characterize those with minimal and maximal
normalized volumes.

######  Definition 3.1.

For $n\in\mathbb{Z}_{\geq 0}$, a _generalized snake word_ is a word of the
form $\mathbf{w}=w_{0}w_{1}\cdots w_{n}$ where $w_{0}=\varepsilon$ is the
empty letter and $w_{i}$ is in the alphabet $\\{L,R\\}$ for $i=1,\ldots,n$.
The _length_ of the word is $n$, which is the number of letters in
$\\{L,R\\}$.

######  Definition 3.2.

Given a generalized snake word $\mathbf{w}=w_{0}w_{1}\cdots w_{n}$, we define
the _generalized snake poset_ $P(\mathbf{w})$ recursively in the following
way:

  * •

$P(w_{0})=P(\varepsilon)$ is the poset on elements $\\{0,1,2,3\\}$ with cover
relations $1\prec 0$, $2\prec 0$, $3\prec 1$ and $3\prec 2$.

  * •

$P(w_{0}w_{1}\cdots w_{n})$ is the poset $P(w_{0}w_{1}\cdots
w_{n-1})\cup\\{2n+2,2n+3\\}$ with the added cover relations $2n+3\prec 2n+1$,
$2n+3\prec 2n+2$, and

$\begin{cases}2n+2\prec 2n-1,&\text{ if }n=1\text{ and }w_{n}=L,\text{ or
}n\geq 2\text{ and }w_{n-1}w_{n}\in\\{RL,LR\\},\\\ 2n+2\prec 2n,&\text{ if
}n=1\text{ and }w_{n}=R,\text{ or }n\geq 2\text{ and
}w_{n-1}w_{n}\in\\{LL,RR\\}.\end{cases}$

In this definition, the minimal element of the poset $P(\mathbf{w})$ is
$\widehat{0}=2n+3$, and the maximal element of the poset is $\widehat{1}=0$.

If $\mathbf{w}=w_{0}w_{1}\cdots w_{n}$ is a generalized snake word of length
$n$, then $P(\mathbf{w})$ is a distributive lattice of width two and rank
$n+2$. We point out two special cases of generalized snake posets. For the
length $n$ word $\varepsilon LRLR\cdots$, $S_{n}:=P(\varepsilon LRLR\cdots)$
is the _snake poset_ , and for the length $n$ word $\varepsilon LLLL\cdots$,
$\mathcal{L}_{n}:=P(\varepsilon LLLL\cdots)$ is the _ladder poset_. For an
example, refer to Figure 1.

$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$$\varepsilon$$L$$R$$L$$R$$L$$0$$1$$4$$6$$8$$10$$12$$2$$3$$5$$7$$9$$11$$13$$\varepsilon$$L$$L$$L$$L$$L$
Figure 1. The snake poset $S_{5}=P(\varepsilon LRLRL)$ and the ladder poset
$\mathcal{L}_{5}=P(\varepsilon LLLLL)$.

In this article, we consider the generalized snake posets in two contexts. In
the next subsection, we consider the order polytope of the generalized snake
posets, $\mathcal{O}(P(\mathbf{w}))$. More precisely, we give a recursive
formula for the volume and obtain tight lower and upper bounds for the volumes
of $\mathcal{O}(P(\mathbf{w}))$ when $\mathbf{w}$ is of fixed length. In the
remaining sections, we study the order polytope of a related poset
$Q_{\mathbf{w}}$, which is the poset of join-irreducibles of the generalized
snake poset.

###  3.1. Volume of the order polytope of generalized snake posets

Recall that the volume of an order polytope $\mathcal{O}(P)$ is determined by
the number of linear extensions of the poset $P$. Thus, to study the volume of
$\mathcal{O}(P(\mathbf{w}))$ we consider the recursive structure of the poset
of upper order ideals of $P(\mathbf{w})$. Because of the definition of the
generalized snake poset $P(\mathbf{w})$, the minimal element of
$J(P(\mathbf{w}))$ is $\widehat{0}=\langle 2n+3\rangle=P(\mathbf{w})$ and the
maximal element is $\widehat{1}=\varnothing$.

######  Lemma 3.3.

Let $\mathbf{w}=w_{0}w_{1}\cdots w_{n}$ be a generalized snake word. If $k\geq
0$ is the largest index such that $w_{k}\neq w_{n}$, then $J(P(\mathbf{w}))=$

$J(P(w_{0}w_{1}\cdots w_{n-1}))\cup\left\\{\langle 2n+3\rangle,\langle
2n+2\rangle,\langle 2n+2,2k+2\rangle\right\\}\cup\left\\{\langle
2n+2,2k+2i+1\rangle\right\\}_{i=1}^{n-k}.$

###### Proof.

First note that $P(\mathbf{w})=P(w_{0}w_{1}\cdots
w_{n-1})\cup\\{2n+2,2n+3\\}$, where $2n+3\prec 2n+1$, $2n+3\prec 2n+2$, and
$2n+2\prec 2n$ or $2n+2\prec 2n-1$. One can see that $J(P(w_{0}w_{1}\cdots
w_{n-1}))$ is contained in $J(P(\mathbf{w}))$. The added elements $2n+3$ and
$2n+2$ generate the upper order ideals $\langle 2n+3\rangle$ and $\langle
2n+2\rangle$, respectively. Since $2n+3$ is comparable with every other
element of $P(\mathbf{w})$, it is not in the minimal generating set of any
other upper order ideal. The only elements of $P(w_{0}w_{1}\cdots w_{n-1})$
which are not comparable with $2n+2$ are $2k+2$ and
$\\{2k+2i+1\\}_{i=1}^{n-k}$. Hence, each pair $\\{2n+2,2k+2\\}$ and
$\\{2n+2,2k+2i+1\\}_{i=1}^{n-k}$ generates an upper order ideal of
$P(\mathbf{w})$. Since $2n+1\prec\cdots\prec 2k+5\prec 2k+3\prec 2k+2$, no
additional minimal generating sets of upper order ideals are possible. ∎

######  Remark 3.4.

Thus, we see that $J(P(\mathbf{w}))$ can be constructed by adding a chain of
$n-k+3$ elements to the bottom of $J(P(w_{0}w_{1}\cdots w_{n-1}))$. In the
Hasse diagram for $J(P(\mathbf{w}))$, this corresponds to drawing a strip of
$n-k+1$ squares. See Figure 2 for an illustration.

Notice that in the strip of the $n-k+1$ newly added squares in
$J(P(\mathbf{w}))$, the lowest square (consisting of the four elements
$\langle 2n+2,2n+1\rangle,\langle 2n+1\rangle,\langle 2n+2,2n-1\rangle,\langle
2n,2n-1\rangle$) lies directly below the topmost square of $J(P(\mathbf{w}))$
(consisting of the four elements $\langle 0\rangle,\langle 1\rangle,\langle
2\rangle,\langle 1,2\rangle$). Hence from Lemma 3.3, we see that the Hasse
diagram of $J(P(\mathbf{w}))$ contains exactly $n$ squares which are lined up
directly below the topmost square of $J(P(\mathbf{w}))$. We will refer to
these squares as the _central squares_ of $J(P(\mathbf{w}))$. Swapping every
letter from $R$ to $L$ and vice versa in $\mathbf{w}$ corresponds to
reflecting $J(P(\mathbf{w}))$ about this central line of squares.

$2k$$2k+2$$2k+1$$2k+3$$2k+4$$2k+5$$2n$$2n+1$$2n+2$$2n+3$$w_{k-1}$$w_{k}$$w_{k+1}$

$\ddots$

$\ddots$

$w_{n}$$\langle 2k,2k-1\rangle$$\langle 2k+1\rangle$$\langle
2k+1,2k+2\rangle$$\langle 2n\rangle$$\langle 2n+2\rangle$$\langle
2n+2,2k+2\rangle$$\langle 2n+2,2n-3\rangle$$\langle 2n+2,2n-1\rangle$$\langle
2n,2n-1\rangle$$\langle 2n+2,2n+1\rangle$$\langle 2n+1\rangle$$\langle
2n+3\rangle$

$\ddots$

$\ddots$

$\ddots$

$\ddots$

$\vdots$$\vdots$ Figure 2. An illustration of Lemma 3.3. On the left is a
portion of a generalized snake poset $P(\mathbf{w})$ and on the right is the
corresponding poset of upper order ideals $J(P(\mathbf{w}))$. To construct
$J(P(\mathbf{w}))$ from $J(P(w_{0}\cdots w_{n-1})$ is to add $n-k+3$ elements,
with cover relations shown in red in the Hasse diagram on the right.

The normalized volume of the order polytope $\mathcal{O}(P(\mathbf{w}))$ can
be computed by a recursive formula involving Catalan numbers.

######  Definition 3.5.

For $m\geq 0$, the _$m$ -th Catalan number_ is
$\mathrm{Cat}(m)=\frac{1}{m+1}\binom{2m}{m}$.

The Catalan number $\mathrm{Cat}(m)$ enumerates _Dyck paths_ , which are
lattice paths from $(0,0)$ to $(m,m)$ that do not fall below the line $y=x$.

######  Theorem 3.6.

For $n\geq 0$, let $\mathbf{w}=w_{0}w_{1}\cdots w_{n}$ be a generalized snake
word. If $k\geq 0$ is the largest index such that $w_{k}\neq w_{n}$, then the
normalized volume $v_{n}$ of $\mathcal{O}(P(\mathbf{w}))$ is given recursively
by

$v_{n}=\mathrm{Cat}(n-k+1)v_{k}+\left(\mathrm{Cat}(n-k+2)-2\cdot\mathrm{Cat}(n-k+1)\right)v_{k-1}$

with $v_{-1}=1$ and $v_{0}=2$.

###### Proof.

The normalized volume of $\mathcal{O}(P(\mathbf{w}))$ is the number of linear
extensions of $P(\mathbf{w})$, and the set of linear extensions of
$P(\mathbf{w})$ is in bijection with the set of maximal chains in
$J(P(\mathbf{w}))$, so we enumerate the latter.

Let $c(p_{1},..,p_{j})$ denote the number of maximal chains in
$J(P(\mathbf{w}))$ which contain the elements $p_{1},...,p_{j}$. Each maximal
chain in $J(P(\mathbf{w}))$ contains at least one of $\langle 2k,2k-1\rangle$
or $\langle 2k+1,2k+2\rangle$, as can be seen in Figure 2, so the total number
of maximal chains in $J(P(\mathbf{w}))$ is then $c(\varnothing)$ and is given
by

$c(\varnothing)=c(\langle 2k+1,2k+2\rangle)+c(\langle
2k,2k-1\rangle)-c(\langle 2k+1,2k+2\rangle,\langle 2k,2k-1\rangle).$

Note that $c(\langle 2k+1,2k+2\rangle)$ is the product of the number of
maximal chains in the interval $[\langle 2n+3\rangle,\langle
2k+1,2k+2\rangle]$ and the number of maximal chains in the interval $[\langle
2k+1,2k+2\rangle,\varnothing]$. There are $v_{k}$ many maximal chains in
$[\langle 2k+1,2k+2\rangle,\varnothing]$, and the maximal chains in $[\langle
2n+3\rangle,\langle 2k+1,2k+2\rangle]$ are counted by $\mathrm{Cat}(n-k+1)$,
as they can be viewed as Dyck paths. Therefore, $c(\langle
2k+1,2k+2\rangle)=\mathrm{Cat}(n-k+1)v_{k}$. Similarly, one sees that
$c(\langle 2k,2k-1\rangle)=\mathrm{Cat}(n-k+2)v_{k-1}$.

Finally, $c(\langle 2k+1,2k+2\rangle,\langle 2k,2k-1\rangle)$ is given by
$2\mathrm{Cat}(n-k+1)v_{k-1}$, as there are two ways to form a maximal chain
in $J(P(\mathbf{w}))$ from a maximal chain in $[\langle
2k,2k-1\rangle,\varnothing]$ and a maximal chain in $[\langle
2n+3\rangle,\langle 2k+1,2k+2\rangle]$. Therefore,

$c(\varnothing)=\mathrm{Cat}(n-k+1)v_{k}+\mathrm{Cat}(n-k+2)v_{k-1}-2\mathrm{Cat}(n-k+1)v_{k-1}.$

∎

Focusing our attention on the snake poset $S_{n}=P(\varepsilon LRLR\cdots)$,
the letters alternate so we have $n-k=1$ at every step, which leads to the
following corollary.

######  Corollary 3.7.

The normalized volume of $\mathcal{O}(S_{n})$ with $n\geq 0$ is given
recursively by

$v_{n}=2v_{n-1}+v_{n-2},$

with $v_{-1}=1$ and $v_{0}=2$. These are the Pell numbers. ∎

In the case of the ladder poset $\mathcal{L}_{n}=P(\varepsilon LLLL\cdots)$,
we have $k=0$ at every step, and hence we have the following well-known result
as a corollary.

######  Corollary 3.8.

The normalized volume of $\mathcal{O}(\mathcal{L}_{n})$ with $n\geq 0$ is
given by

$v_{n}=\mathrm{Cat}(n+2).$

∎

We end this section by showing that the normalized volume of an order polytope
$\mathcal{O}(P(\mathbf{w}))$ of a generalized snake poset is bounded above and
below by the volume of the order polytope of the ladder poset and the snake
poset, respectively.

Let $W_{n}$ denote the set of generalized snake words of length $n$. For
$i=1,\ldots,n$, define a _swap operation_ $f_{i}:W_{n}\rightarrow W_{n}$ by
letting $f_{i}(\mathbf{w})$ be the word obtained from $\mathbf{w}$ by swapping
all letters with indices greater than or equal to $i$ to the opposite letter.

######  Lemma 3.9.

Let $\mathbf{w}$ be a generalized snake word. Then

$\operatorname{vol}(\mathcal{O}(P(f_{i}(\mathbf{w}))))\leq\operatorname{vol}(\mathcal{O}(P(\mathbf{w})))$

whenever $w_{i-1}=w_{i}$ or $i=1$. Furthermore, equality occurs only when
$i=1$.

###### Proof.

Consider the maximal chains in $J(P(\mathbf{w}))$ and for the moment assume
$i\neq 1$. Without loss of generality assume that $w_{i}=w_{i-1}=L$ (the case
$w_{i}=w_{i-1}=R$ is symmetric).

Let $A=\langle 2i,2i-1\rangle$ and $B=\langle 2i-2,2i-3\rangle$. In light of
Remark 3.4 we see that $J(P(f_{i}(\mathbf{w})))$ consists of a union of the
upper order ideal generated by $A$ in $J(P(\mathbf{w}))$ and a reflected lower
order ideal generated by $B$. Figure 3 provides an illustration.

In $J(P(f_{i}(\mathbf{w})))$, all maximal chains contain at least one of $A$
or $B$. Maximal chains containing $A$ in $J(P(\mathbf{w}))$ corresponds
bijectively to chains containing $A$ in $J(P(f_{i}(\mathbf{w})))$ by
reflecting the portion of the chain after $A$. Similarly, the chains
containing $B$ are in bijection in both posets. Since $J(P(\mathbf{w}))$
contains maximal chains that pass through neither $A$ nor $B$, there are
strictly more maximal chains in $J(P(\mathbf{w}))$. Hence,
$\operatorname{vol}(\mathcal{O}(P(f_{i}(\mathbf{w}))))\leq\operatorname{vol}(\mathcal{O}(P(\mathbf{w})))$.

Finally, in the case $i=1$, $P(\mathbf{w})$ and $P(f_{1}(\mathbf{w}))$ are
isomorphic via a reflection, and so their posets of upper order ideals are
isomorphic. ∎

######  Theorem 3.10.

For any generalized snake word $\mathbf{w}=w_{0}w_{1}\cdots w_{n}$ of length
$n$,

$\operatorname{vol}\mathcal{O}(S_{n})\leq\operatorname{vol}\mathcal{O}(P(\mathbf{w}))\leq\operatorname{vol}\mathcal{O}(\mathcal{L}_{n}).$

###### Proof.

First, we show that
$\operatorname{vol}\mathcal{O}(S_{n})\leq\operatorname{vol}\mathcal{O}(P(\mathbf{w}))$.
Let $2\leq i_{1}<i_{2}<\dots<i_{k}\leq n$ be the set of indices such that
$w_{i_{j}}=w_{i_{j}-1}$. Applying a swap operation at any index strictly
smaller then $i_{j}$ yields a word whose letters indexed by $i_{j}$ and
$i_{j}-1$ are still the same. Then for any $j\in[k]$, the letters indexed by
$i_{j}$ and $i_{j}-1$ are also the same in the word
$f_{i_{j-1}}f_{i_{j-2}}\dots f_{i_{1}}(\mathbf{w})$. By Lemma 3.9, we can
conclude that

$\operatorname{vol}\mathcal{O}(P(f_{i_{k}}f_{i_{k-1}}\dots
f_{i_{1}}(\mathbf{w})))\leq\operatorname{vol}\mathcal{O}(P(\mathbf{w})).$

Moreover, by the construction of $i_{j}$’s and the definition of the swap
operation, no two adjacent letters with indices up to $i_{j}$ are the same in
$f_{i_{j}}f_{i_{j-1}}\dots f_{i_{1}}(\mathbf{w})$. This shows that
$P(f_{i_{k}}f_{i_{k-1}}\dots f_{i_{1}}(\mathbf{w}))$ equals $P(\varepsilon
LRLR\dots)=S_{n}$ or $P(\varepsilon RLRL\dots)=f_{1}(S_{n})$. By Lemma 3.9,
applying $f_{1}$ does not change the volume of the order polytope, so we
conclude that
$\operatorname{vol}\mathcal{O}(S_{n})\leq\operatorname{vol}\mathcal{O}(P(\mathbf{w}))$.

Now, we show the second part of the inequality that
$\operatorname{vol}\mathcal{O}(P(\mathbf{w}))\leq\operatorname{vol}\mathcal{O}(\mathcal{L}_{n})$.
Let $2\leq i_{1}<i_{2}<\dots<i_{k}\leq n$ be the set of indices such that
$w_{i_{j}}\not=w_{i_{j}-1}$. Then for any $j\in[k]$ the letters in
$f_{i_{j-1}}\dots f_{i_{1}}(\mathbf{w})$ with indices strictly smaller then
$i_{j}$ are the same, but the the letters with indices $i_{j}$ and $i_{j}-1$
are different. Then the letters in $f_{i_{j}}f_{i_{j-1}}\dots
f_{i_{1}}(\mathbf{w})$ with indices $i_{j}$ and $i_{j}-1$ are the same and
Lemma 3.9 implies that

$\operatorname{vol}\mathcal{O}(P(\mathbf{w}))\leq\operatorname{vol}\mathcal{O}(P(f_{i_{k}}f_{i_{k-1}}\dots
f_{i_{1}}(\mathbf{w}))).$

Furthermore, by construction all letters in $f_{i_{k}}f_{i_{k-1}}\dots
f_{i_{1}}(\mathbf{w})$ are the same so its generalized snake poset equals
$P(\varepsilon LLL\dots)=\mathcal{L}_{n}$ or $P(\varepsilon
RRR\dots)=f_{1}(L_{n})$. By the same reasoning as above we conclude that
$\operatorname{vol}\mathcal{O}(P(\mathbf{w}))\leq\operatorname{vol}\mathcal{O}(\mathcal{L}_{n})$.
∎

$A$$B$$\vdots$$L$$L$$L$$L$$L$$L$$R$$R$$A$$B$$\vdots$$L$$L$$L$$R$$R$$R$$L$$L$
Figure 3. On the left is a snippet of a poset $J(P(\mathbf{w}))$ where
$\mathbf{w}$ contains the sequence $\cdots
RLLL{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}L}LLRRL\cdots$.
On the right is the corresponding snippet of $J(P(f_{i}(\mathbf{w})))$, where
$i$ is the index of the red $L$ in $\mathbf{w}$. The corresponding portion in
$f_{i}(\mathbf{w})$ is $\cdots
RLLL{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}R}RRLLR\cdots$.
The blue paths demonstrate the bijective correspondence between maximal chains
in $J(P(\mathbf{w}))$ through $A$ or $B$ with maximal chains in
$J(P(f_{i}(\mathbf{w})))$.

##  4\. A combinatorial interpretation of circuits

In the remainder of this article, we study the properties of the order
polytope of a poset $Q_{\mathbf{w}}$ whose lattice of filters is a generalized
snake poset.

Define $\widehat{P}(\mathbf{w})$ to be the generalized snake poset
$P(\mathbf{w})$ with $\widehat{0}$ and $\widehat{1}$ adjoined, and when
$\mathbf{w}$ is clear from context we write $\widehat{P}$. Given
$\mathbf{w}=w_{0}w_{1}\cdots w_{n}$, $\widehat{P}=\widehat{P}(\mathbf{w})$ is
a distributive lattice with order $2n+6$ because $\widehat{P}$ does not
contain a copy of the smallest non-modular lattice with five elements and does
not contain a sublattice isomorphic to a three-element antichain with a
$\widehat{0}$ and $\widehat{1}$ added. Let
$Q_{\mathbf{w}}=\mathrm{Irr}_{\wedge}(\widehat{P})$ denote the poset of meet-
irreducibles of $\widehat{P}$. Heuristically,
$\mathrm{Irr}_{\wedge}(\widehat{P})$ is obtained from $\widehat{P}$ by
removing $\widehat{1}$, and every vertex which is at the bottom of a bounded
face in the Hasse diagram. See Figure 4. By the fundamental theorem of finite
distributive lattices, $\widehat{P}\cong J(Q_{\mathbf{w}})$, where
$J(Q_{\mathbf{w}})$ is the lattice of filters of $Q_{\mathbf{w}}$, ordered by
reverse inclusion.

We construct a graph $G=G(\mathbf{w})$ associated to
$\widehat{P}=\widehat{P}(\mathbf{w})$ as follows. If
$\mathbf{w}=w_{0}w_{1}\cdots w_{n}$, the vertex set of $G$ is
$V(G)=\\{w_{0},w_{1},\ldots,w_{n}\\}$. The edge set of $G$ is given by

$E(G)=\\{(w_{i},w_{i+1})\mid i=0,\ldots,n-1\\}\cup\\{(w_{i},w_{i+2})\mid\hbox{
if $w_{i}w_{i+1}w_{i+2}=LLR$ or $RRL$}\\}.$

In other words, $G$ consists of the path of length $n$ on the vertices
$w_{0},\ldots,w_{n}$, with a $3$-cycle for each turn $LLR$ or $RRL$ in
$\mathbf{w}$. See Figure 4. We denote the set of nonempty connected induced
subgraphs of $G(\mathbf{w})$ by $\mathcal{G}(\mathbf{w})$.

The Hasse diagram of $\widehat{P}(\mathbf{w})$ can be embedded on the plane so
that its edges are non-crossing where each bounded face of the embedded Hasse
diagram has degree $4$ given by the length of the cycle bounding the face. We
call these bounded faces the squares of $\widehat{P}(\mathbf{w})$.

There is a one-to-one correspondence between the squares of
$\widehat{P}(\mathbf{w})$ and the letters of $\mathbf{w}$ by realizing
$G=G(\mathbf{w})$ as follows. Consider each square in the Hasse diagram
$\mathrm{Hasse}(\widehat{P})$ as a vertex, then form an edge between squares
when they intersect in the plane, as shown in Figure 4. To each vertex $w_{i}$
of $G$, we denote by $\mathrm{Sq}(w_{i})$ the four elements of $\widehat{P}$
contained in the $4$-cycle which bounds the face of
$\mathrm{Hasse}(\widehat{P})$ corresponding to $w_{i}$.

${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}w_{0}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}w_{1}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}w_{2}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}w_{3}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}w_{4}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}w_{5}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}w_{6}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}w_{7}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}w_{8}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}w_{9}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}w_{10}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}w_{11}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}w_{12}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}w_{13}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}w_{14}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}w_{15}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}w_{16}}$$\varnothing$$\langle
0\rangle$$\langle 1\rangle$$\langle 2\rangle$$\langle 3\rangle$$\langle
4\rangle$$\langle 5\rangle$$\langle 6\rangle$$\langle 7\rangle$$\langle
8\rangle$$\langle 9\rangle$$\langle 10\rangle$$\langle 11\rangle$$\langle
12\rangle$$\langle 13\rangle$$\langle 14\rangle$$\langle 15\rangle$$\langle
16\rangle$$\langle 17\rangle$$\langle 18\rangle$$\langle
19\rangle$$\varepsilon$$L$$L$$L$$R$$R$$L$$L$$L$$L$$R$$R$$R$$R$$R$$L$$L$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$$14$$15$$17$$16$$18$$19$
Figure 4. In the center is the lattice $\widehat{P}(\mathbf{w})$ for
$\mathbf{w}=\varepsilon L^{3}R^{2}L^{4}R^{5}L^{2}$. Its poset of meet-
irreducibles $Q_{\mathbf{w}}=\mathrm{Irr}_{\wedge}(\widehat{P})$ is shown to
the right, and the associated graph $G(\mathbf{w})$ is shown to the left.

######  Remark 4.1.

The volume of $\mathcal{O}(Q_{\mathbf{w}})$ equals the number of maximal
chains in $\widehat{P}(\mathbf{w})$ or, equivalently, in $P(\mathbf{w})$. By
[17, Section 4], maximal chains in $P(\mathbf{w})$ are in bijection with
perfect matchings of the Hasse diagram of $P(\mathbf{w}^{*})$, where
$\mathbf{w}^{*}$ denotes the dual of $\mathbf{w}$. Informally,
$P(\mathbf{w}^{*})$ is obtained from $P(\mathbf{w})$ by replacing three
consecutive squares that form a ladder by three squares that form a bend and
vice versa. Perfect matchings of $P(\mathbf{w}^{*})$ have been extensively
studied because they play an important role in the theory of cluster algebras
and their total number can be computed via explicit formulas involving
continued fractions [3, Theorem 3.4] or certain admissible sequences [1,
Theorem 4.6].

Alternatively, we may view the Hasse diagram of $P(\mathbf{w})$ as a skew
partition $\lambda/\mu$, and maximal chains in $P(\mathbf{w})$ correspond to
partitions contained in $\lambda/\mu$. For example in Figure 4,
$\lambda=(10,7,7,3,3,3,3,3)$ and $\mu=(6,6,2,2,2,2,2)$. Given a partition
$\lambda=(\lambda_{1},\ldots,\lambda_{k})$, the number of partitions contained
inside $\lambda$ is given by
$D(\lambda)=\det(\binom{\lambda_{j}+1}{j-i+1})_{1\leq i,j\leq k}$, thus the
number of maximal chains in $P(\mathbf{w})$ can be computed by
$D(\lambda)-D(\mu)$.

Next, we study the circuits of the order polytope
$\mathcal{O}(Q_{\mathbf{w}})$. Understanding this for arbitrary words
$\mathbf{w}$ is a challenge, therefore we instead restrict our attention in
this section to the following set of words.

######  Definition 4.2.

Let $\mathcal{V}$ denote the subset of words which do not contain the
substring $LRL$ or $RLR$.

Theorem 4.5 shows that for $\mathbf{w}\in\mathcal{V}$, circuits in the
vertices of $\mathcal{O}(Q_{\mathbf{w}})$ have a combinatorial interpretation
as the nonempty connected induced subgraphs of the graph $G(\mathbf{w})$.

######  Lemma 4.3.

Let $\mathbf{w}\in\mathcal{V}$ be a generalized snake word of length $n$. The
poset $Q_{\mathbf{w}}$ has order $n+4$.

###### Proof.

A non-$\widehat{1}$ element of $\widehat{P}$ is meet-irreducible if and only
if it is not the minimum element in a square of $\widehat{P}(\mathbf{w})$.
There are $n+1$ squares, thus
$|\mathrm{Irr}_{\wedge}(\widehat{P})|=2n+6-1-(n+1)=n+4.$ ∎

######  Lemma 4.4.

Let $\mathbf{w}\in\mathcal{V}$ be a generalized snake word of length $n$. A
circuit of the vertex set of $\mathcal{O}(Q_{\mathbf{w}})$ cannot contain the
zero vector $\mathbf{v}_{\varnothing}$ or
$\mathbf{v}_{Q_{\mathbf{w}}}=(1,1,\ldots,1)$.

###### Proof.

Observe that $\mathbf{v}_{\varnothing}$ is the zero vector in
$\mathbb{R}^{|Q_{\mathbf{w}}|}$, so it cannot be in a minimal dependent set.
Also, $\mathbf{v}_{Q_{\mathbf{w}}}$ is the vector of all ones in
$\mathbb{R}^{|Q_{\mathbf{w}}|}$, and in particular is the only vertex whose
$|Q_{\mathbf{w}}|$-th coordinate is nonzero, so it also cannot be in a minimal
dependent set. ∎

######  Theorem 4.5.

Let $\mathbf{w}\in\mathcal{V}$ be a generalized snake word of length $n$.
There exists a bijection
$\Gamma:\mathcal{G}(\mathbf{w})\rightarrow\mathcal{C}(Q_{\mathbf{w}})$ between
the set $\mathcal{G}(\mathbf{w})$ of nonempty connected induced subgraphs of
$G(\mathbf{w})$ and the set $\mathcal{C}(Q_{\mathbf{w}})$ of circuits of the
vertex set of the order polytope $\mathcal{O}(Q_{\mathbf{w}})$.

###### Proof.

Let ${\mathbf{w}}=w_{0}w_{1}\dots w_{n}$ and let
$H\in\mathcal{G}(\mathbf{w})$. For a filter $A$ of $Q_{\mathbf{w}}$, we
consider $A$ to be a point in $J(Q_{\mathbf{w}})\cong\widehat{P}$. We say $A$
is _compatible_ with $H$ if $A$ is an element of an odd number of squares in
$\\{\mathrm{Sq}(w_{i}):w_{i}\in H\\}$. Define $\Gamma(H)$ to be the set of all
$\mathbf{v}_{A}$ such that $A$ is compatible with $H$. See Figure 5 for an
illustration.

${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}+}$${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}-}$${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}-}$${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}+}$${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}-}$${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}+}$${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}+}$${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}-}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}w_{1}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}w_{2}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}w_{3}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}w_{4}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}w_{6}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}w_{7}}$${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}w_{8}}$
Figure 5. The connected induced subgraph $H$ of $G(\mathbf{w})$, depicted in
blue, is embedded in $\mathrm{Hasse}(\widehat{P})$. The elements in the
circuit $\Gamma(H)$ are depicted in red.

We shall show by induction on $|H|$ that $\Gamma(H)$ is a minimal dependent
set of vertices of $\mathcal{O}(Q_{\mathbf{w}})$. First, suppose
$H=\\{w_{k}\\}$ is a single vertex of $G$ for some $k=0,\ldots,n$. Then for
some filter $A$ of $Q_{\mathbf{w}}$ and distinct incomparable elements $x,y\in
Q_{\mathbf{w}}$, we have

$\Gamma(H)=\\{\mathbf{v}_{B}:B\in\mathrm{Sq}(w_{k})\\}=\\{\mathbf{v}_{A},\mathbf{v}_{A\cup\\{x\\}},\mathbf{v}_{A\cup\\{y\\}},\mathbf{v}_{A\cup\\{x,y\\}}\\}\,.$

As

$\displaystyle\mathbf{v}_{A\cup\\{x\\}}$
$\displaystyle=\mathbf{v}_{A}+\mathbf{e}_{x},$
$\displaystyle\mathbf{v}_{A\cup\\{y\\}}$
$\displaystyle=\mathbf{v}_{A}+\mathbf{e}_{y},$
$\displaystyle\mathbf{v}_{A\cup\\{x,y\\}}$
$\displaystyle=\mathbf{v}_{A}+\mathbf{e}_{x}+\mathbf{e}_{y},$

then
$\mathbf{v}_{A}-\mathbf{v}_{A\cup\\{x\\}}-\mathbf{v}_{A\cup\\{y\\}}+\mathbf{v}_{A\cup\\{x,y\\}}=\mathbf{0},$
and $\Gamma(H)$ is a circuit.

Next, suppose $H=\\{w_{i_{1}},\ldots,w_{i_{k}}\\}$ is a connected induced
subgraph of $G$, with the assumption that $i_{1}<\cdots<i_{k}$ and $k\geq 2$.
Observe that $H$ contains the path $w_{i_{1}},\ldots,w_{i_{k}}$. We will
inductively assign signs to the squares of $\widehat{P}$ that contain vertices
of $H$. Start by defining $\mathrm{sgn}(\mathrm{Sq}(w_{i_{1}}))=1$. For
$j=2,\ldots,k$,

$\mathrm{sgn}(\mathrm{Sq}(w_{i_{j}}))=\begin{cases}\
\,\,\,\mathrm{sgn}(\mathrm{Sq}(w_{i_{j-1}}))\,,&\hbox{if
$i_{j}-i_{j-1}=1$},\\\ -\mathrm{sgn}(\mathrm{Sq}(w_{i_{j-1}})),&\hbox{if
$i_{j}-i_{j-1}=2$}\,.\end{cases}$

We note that since $H$ is a connected subgraph, then
$\mathrm{Sq}(w_{i_{j}})\cap\mathrm{Sq}(w_{i_{j+1}})\neq\varnothing$. If

$\mathrm{Sq}(w_{i_{j}})=\left\\{A_{i_{j}},A_{i_{j}}\cup\\{x_{i_{j}}\\},A_{i_{j}}\cup\\{y_{i_{j}}\\},A_{i_{j}}\cup\\{x_{i_{j}},y_{i_{j}}\\}\right\\},$

then

$\sigma_{i_{j}}:=\mathbf{v}_{A_{i_{j}}}-\mathbf{v}_{A_{i_{j}}\cup\\{x_{i_{j}}\\}}-\mathbf{v}_{A_{i_{j}}\cup\\{y_{i_{j}}\\}}+\mathbf{v}_{A_{i_{j}}\cup\\{x_{i_{j}},y_{i_{j}}\\}}=\mathbf{0}$

is an affine dependence relation on the vertices of $\mathrm{Sq}(w_{i_{j}})$.
Thus,

(1)
$\sum_{j=1}^{k}\mathrm{sgn}(\mathrm{Sq}(w_{i_{j}}))\cdot\sigma_{i_{j}}=\mathbf{0}.\,$

Because of the definition of the $\mathrm{sgn}$ function, the terms which
occur in the left hand side of this expression with nonzero coefficient are
indexed precisely by the elements of $\widehat{P}$ which are compatible with
$H$, i.e., $\Gamma(H)$. Thus, $\Gamma(H)$ is a dependent set with an affine
dependence relation (1).

Having shown $\Gamma(H)$ is dependent, it remains to show that $\Gamma(H)$ is
also minimal, i.e., a circuit. We will use induction on $|H|=k$. If $k=1$,
then it is straightforward to verify that $\mathrm{Sq}(w_{i_{1}})$ is a
circuit. Assume that $k>1$. We consider three cases. For the first case,
suppose that $i_{k-1}+1=i_{k}$ and $(w_{i_{k-2}},w_{i_{k}})$ is not an edge in
$H$. Thus, it follows that for some filter $A$ and elements $a,b,c$, we have

$\mathrm{Sq}(w_{i_{k-1}})=\\{A,A\cup\\{b\\},A\cup\\{a\\},A\cup\\{a,b\\}\\}$

and

$\mathrm{Sq}(w_{i_{k}})=\\{A\cup\\{b\\},A\cup\\{a,b\\},A\cup\\{b,c\\},A\cup\\{a,b,c\\}\\}\,.$

$A$$A\cup\\{a\\}$$A\cup\\{b\\}$$A\cup\\{a,b\\}$$A\cup\\{b,c\\}$$A\cup\\{a,b,c\\}$$w_{i_{k-1}}$$w_{i_{k}}$
Figure 6. The first case, with $i_{k-1}+1=i_{k}$ and $(w_{i_{k-2}},w_{i_{k}})$
is not an edge in $H$.

In $\Gamma(H)$, the only vectors supported on the $c$-coordinate are
$\mathbf{v}_{A\cup\\{b,c\\}}$ and $\mathbf{v}_{A\cup\\{a,b,c\\}}$. If we
restrict the vectors in $\\{\mathbf{v}_{C}:C\in\Gamma(H)\\}$ to the
coordinates in $A\cup\\{a,b\\}$, then we obtain the vectors
$\\{\mathbf{v}_{C}:C\in\Gamma(H\setminus w_{i_{k}})\\}$. By induction, these
vectors form a circuit with a unique minimal dependence where the coefficients
of $\mathbf{v}_{A\cup\\{b\\}}$ and $\mathbf{v}_{A\cup\\{a,b\\}}$ are equal and
opposite in sign. Thus, this is the only potential dependence (up to scaling)
for $\\{\mathbf{v}_{C}:C\in\Gamma(H)\\}$, where the coefficients of
$\mathbf{v}_{A\cup\\{b\\}}$ and $\mathbf{v}_{A\cup\\{a,b\\}}$ become the
coefficients of $\mathbf{v}_{A\cup\\{b,c\\}}$ and
$\mathbf{v}_{A\cup\\{a,b,c\\}}$ respectively. It is immediate that this choice
of coefficients is a dependence with all non-zero coefficients, and thus
$\Gamma(H)$ is a circuit.

For the second case, suppose that $i_{k-1}+2=i_{k}$, i.e., the last edge in
$H$ is the vertical edge of a triangle in $G$. Thus, it follows that for some
filter $A$ and elements $a,b,c,d$, we have

$\mathrm{Sq}(w_{i_{k-1}})=\\{A,A\cup\\{b\\},A\cup\\{a\\},A\cup\\{a,b\\}\\}$

and

$\mathrm{Sq}(w_{i_{k}})=\\{A\cup\\{a,b\\},A\cup\\{a,b,c\\},A\cup\\{a,b,d\\},A\cup\\{a,b,c,d\\}\\}\,.$

$A$$A\cup\\{a\\}$$A\cup\\{b\\}$$A\cup\\{a,b\\}$$A\cup\\{a,b,d\\}$$A\cup\\{a,b,c\\}$$A\cup\\{a,b,c,d\\}$$w_{i_{k-1}}$$w_{i_{k}}$
Figure 7. Case two, with $i_{k-1}+2=i_{k}$.

In $\Gamma(H)$, the only vectors supported on the $d$-coordinate are
$\mathbf{v}_{A\cup\\{a,b,c,d\\}}$ and $\mathbf{v}_{A\cup\\{a,b,d\\}}$. Thus,
in any dependence for $\Gamma(H)$, these two vectors have coefficients that
are equal in magnitude and opposite in sign. The only vectors supported on the
$c$-coordinate are $\mathbf{v}_{A\cup\\{a,b,c\\}}$ and
$\mathbf{v}_{A\cup\\{a,b,c,d\\}}$. Thus, these vectors have coefficients that
are equal in magnitude and opposite in sign in any dependence for $\Gamma(H)$.
Summing these three vectors with these equal and opposite coefficients yields
the vector $\mathbf{v}_{A\cup\\{a,b\\}}$ (scaled by the same coefficient).
Thus, any dependence on $\Gamma(H)$ arises from a dependence on
$\Gamma(H\setminus w_{i_{k}})$. By induction, this set is a circuit with a
unique minimal dependence. This unique minimal dependence induces a unique
minimal dependence on $\Gamma(H)$, for which every coefficient is non-zero.

For the third case, suppose that $i_{k-1}+1=i_{k}$ and
$(w_{i_{k-2}},w_{i_{k}})$ is an edge in $H$, i.e., that $w_{i_{k-2}}$,
$w_{i_{k-1}}$, and $w_{i_{k}}$ form a triangle in $H$. Thus, it follows that
for some filter $A$ and elements $a,b,c,d$, we have

$\mathrm{Sq}(w_{i_{k-2}})=\\{A,A\cup\\{b\\},A\cup\\{a\\},A\cup\\{a,b\\}\\}$

and

$\mathrm{Sq}(w_{i_{k-1}})=\\{A\cup\\{b\\},A\cup\\{a,b\\},A\cup\\{b,c\\},A\cup\\{a,b,c\\}\\}$

and

$\mathrm{Sq}(w_{i_{k}})=\\{A\cup\\{a,b\\},A\cup\\{a,b,c\\},A\cup\\{a,b,d\\},A\cup\\{a,b,c,d\\}\\}\,.$

$A$$A\cup\\{a\\}$$A\cup\\{b\\}$$A\cup\\{a,b\\}$$A\cup\\{b,c\\}$$A\cup\\{a,b,d\\}$$A\cup\\{a,b,c\\}$$A\cup\\{a,b,c,d\\}$$w_{i_{k-2}}$$w_{i_{k-1}}$$w_{i_{k}}$
Figure 8. Case three, with $i_{k-1}+1=i_{k}$ and $(w_{i_{k-2}},w_{i_{k}})$ is
an edge in $H$.

In $\Gamma(H)$, the only vectors supported on the $d$-coordinate are
$\mathbf{v}_{A\cup\\{a,b,c,d\\}}$ and $\mathbf{v}_{A\cup\\{a,b,d\\}}$. Thus,
in any dependence for $\Gamma(H)$, these two vectors have coefficients that
are equal in magnitude and opposite in sign. Because $A\cup\\{a,b,c\\}$ is not
compatible with $H$, the only non-zero vectors supported on the $c$-coordinate
are $\mathbf{v}_{A\cup\\{b,c\\}}$and $\mathbf{v}_{A\cup\\{a,b,c,d\\}}$. Thus,
these vectors have coefficients that are equal in magnitude and opposite in
sign in any dependence for $\Gamma(H)$. Summing these three vectors with these
equal and opposite coefficients yields the vector $\mathbf{v}_{A\cup\\{b\\}}$
(scaled by the same coefficient). Thus, any dependence on $\Gamma(H)$ arises
from a dependence on $\Gamma(H\setminus\\{w_{i_{k-1}},w_{i_{k}}\\})$. By
induction, this set is a circuit with a unique minimal dependence. This unique
minimal dependence induces a unique minimal dependence on $\Gamma(H)$, for
which every coefficient is non-zero.

Having established that $\Gamma$ is well-defined, we next show that $\Gamma$
is injective. Suppose $\Gamma(H)=\Gamma(K)$ but $H\neq K$. Since $H$ and $K$
are induced subgraphs, then this means $V(H)\neq V(K)$. Without loss of
generality, suppose $w_{m}\in H$ but $w_{m}\notin K$. Since $H$ and $K$ are
each connected, then $w_{m}$ must occur either at one of the ends of the main
path ($w_{i_{1}},\ldots,w_{i_{k}}$) of $H$, or is a corner of a triangle in
$H$, where $w_{i}$ is a corner if $w_{i-1}$ and $w_{i+1}\in H$. In either
case, this implies $\Gamma(H)\backslash\Gamma(K)\neq\varnothing$, a
contradiction.

To see that $\Gamma$ surjective, we induct on the length of $\mathbf{w}$. If
$\mathbf{w}=w_{0}w_{1}\cdots w_{n}$, we define $\ell(\mathbf{w})=n$. Consider
$\ell(\mathbf{w})=0$ so that $\mathbf{w}=\varepsilon$. See Figure 9.

$\varnothing$$\langle 0\rangle$$\langle 1\rangle$$\langle 2\rangle$$\langle
3\rangle$$\langle
1,2\rangle$$\varepsilon$$\widehat{P}=\widehat{P}(\varepsilon):$$0$$1$$2$$3$$Q_{\varepsilon}=\mathrm{Irr}_{\wedge}(J):$
Figure 9. The base case with $\mathbf{w}=\varepsilon$.

The only circuit arises from $\mathrm{Sq}(\varepsilon)$:

$\mathbf{v}_{\langle 0\rangle}-\mathbf{v}_{\langle
1\rangle}-\mathbf{v}_{\langle 2\rangle}+\mathbf{v}_{\langle
1,2\rangle}=(1,0,0,0)-(1,1,0,0)-(1,0,1,0)+(1,1,1,0)=(0,0,0,0).$

Suppose the map
$\Gamma:\mathcal{G}(\mathbf{w})\rightarrow\mathcal{C}(Q_{\mathbf{w}})$ is
surjective for all $\mathbf{w}$ where $\ell(\mathbf{w})\leq n-1$.

Now, let $\mathbf{u}=w_{0}\cdots w_{n-1}\in\mathcal{V}$ and
$\mathbf{w}=\mathbf{u}w_{n}\in\mathcal{V}$. Suppose
$\mathrm{Sq}(w_{n})=\\{A,B,C,D\\}$ so that $A\prec B$, $A\prec C$, $B\prec D$,
$C\prec D$, and $C$ and $B$ are incomparable. Without loss of generality,
there are two cases to consider; $w_{n-1}=w_{n}=R$, or $w_{n-1}=L$ and
$w_{n}=R$. These cases are shown in Figure 10.

$D=\langle d\rangle$$C=\langle e,d\rangle$$B=\langle b\rangle$$A=\langle
e,b\rangle$$Q$$w_{n}$$w_{n-1}$$w_{n-2}$$\widehat{P}=\widehat{P}(\mathbf{w}):$$F=\langle
f\rangle$$E=\langle e\rangle$$D=\langle f,g\rangle$$C=\langle
e,g\rangle$$B=\langle b\rangle$$A=\langle
e,b\rangle$$Q$$w_{n}$$w_{n-1}$$w_{n-2}$or Figure 10. The two cases in the
induction step.

In both cases, $A$ and $C$ are not meet-irreducible, while $B$ is meet-
irreducible. In the case $w_{n}=w_{n-1}$, $D$ is meet-irreducible, so we have
$B=\langle b\rangle$, $D=\langle d\rangle$, $A=\langle e,b\rangle$ and
$C=\langle e,d\rangle$ for some $b,d,e\in Q$. In the case $w_{n}\neq w_{n-1}$,
$D$ is not meet-irreducible. If $\mathrm{Sq}(w_{n-1})=\\{C,D,E,F\\}$ with
$E\prec F$, then we have $B=\langle b\rangle$, $E=\langle e\rangle$,
$F=\langle f\rangle$, $A=\langle e,b\rangle$, $C=\langle e,d\rangle$ and
$D=\langle f,d\rangle$ for some $b,d,e,f\in Q$. See the picture on the left in
Figure 10.

Let $T=\mathrm{Irr}_{\wedge}(\widehat{P}(\mathbf{u}))$. If
$\gamma\in\mathcal{C}(Q_{\mathbf{w}})$ is a circuit that does not contain
$\mathbf{v}_{A}$ or $\mathbf{v}_{B}$, then $\gamma$ is a circuit of the vertex
set of $\mathcal{O}(T)$. By the induction hypothesis, there exists a connected
induced subgraph $H\in\mathcal{G}(\mathbf{u})\subset\mathcal{G}(\mathbf{w})$
such that $\Gamma(H)=\gamma$.

We shall show that for any circuit $\gamma$ that contains $\mathbf{v}_{A}$ or
$\mathbf{v}_{B}$, there exists a connected induced subgraph $H\subseteq G$
such that $\Gamma(H)=\gamma$. First, observe that $\mathbf{v}_{A}$ or
$\mathbf{v}_{B}$ are the only vertices in $\mathcal{O}(Q_{\mathbf{w}})$ whose
$b$-th coordinate is nonzero, aside from $\mathbf{v}_{Q_{\mathbf{w}}}$ (which
by Lemma 4.4 we know cannot be contained in any circuit). Thus, if one of
these vectors is in $\gamma$, then they must both be in $\gamma$. This also
implies that any dependency relation involving $\mathbf{v}_{A}$ and
$\mathbf{v}_{B}$ must be of the form
$\alpha(\mathbf{v}_{A}-\mathbf{v}_{B})+R=\mathbf{0}$ for some nonzero
$\alpha\in\mathbb{R}$ and where $R$ is a linear combination of the elements of
$\gamma\smallsetminus\\{\mathbf{v}_{A},\mathbf{v}_{B}\\}$. Second, since
$\mathbf{v}_{A}\in\gamma$ and $A=\langle e,b\rangle$, then $\gamma$ must
contain a vertex of the form $\mathbf{v}_{\langle e\rangle}$ or
$\mathbf{v}_{\langle e,x\rangle}$ for some $x\in Q_{\mathbf{w}}$.

Consider the case $w_{n}=w_{n-1}=R$, so that $C=\langle e,d\rangle$ and
$D=\langle d\rangle$. If $\mathbf{v}_{C}\in\gamma$, then
$\mathbf{v}_{D}\in\gamma$ as well, since these are the only vertices in
$\mathcal{O}(T)$ whose $d$-th coordinate is nonzero. Then by minimality
$\gamma$ must be the circuit $\\{A,B,C,D\\}$ as

$\mathbf{v}_{A}-\mathbf{v}_{B}-\mathbf{v}_{C}+\mathbf{v}_{D}=\mathbf{0}.$

In this case $H=\\{w_{n}\\}$ and $\Gamma(H)=\gamma$.

Otherwise, $\gamma$ does not contain $\mathbf{v}_{C}$ nor $\mathbf{v}_{D}$, so
suppose $\gamma$ gives rise to a minimal dependence relation of the form

$\alpha\mathbf{v}_{A}-\alpha\mathbf{v}_{B}+R=\mathbf{0}$

for some nonzero $\alpha\in\mathbb{R}$, and $R$ is a nonzero linear
combination of vertices of $\mathcal{O}(T)$ that does not involve
$\mathbf{v}_{A}$ or $\mathbf{v}_{B}$. As
$\mathbf{v}_{A}-\mathbf{v}_{B}=\mathbf{v}_{C}-\mathbf{v}_{D},$ then

$\alpha\mathbf{v}_{C}-\alpha\mathbf{v}_{D}+R=\mathbf{0}$

is another dependence relation which is minimal, because the initial
dependence relation was minimal. This new dependence relation consists of a
set of vertices $\gamma^{\prime}\subseteq\mathcal{O}(T)$, so by the induction
hypothesis, there is a connected induced subgraph
$H^{\prime}\in\mathcal{G}(\mathbf{u})$ such that
$\Gamma(H^{\prime})=\gamma^{\prime}$. From this, it follows that the connected
induced subgraph $H=H^{\prime}\cup\\{w_{n}\\}\in\mathcal{G}(\mathbf{w})$
satisfies $\Gamma(H)=\gamma$.

Next, we consider the case $w_{n-1}=L$ and $w_{n}=R$. We have $C=\langle
e,g\rangle$, $D=\langle f,g\rangle$, $E=\langle e\rangle$ and $F=\langle
f\rangle$. See the picture on the right in Figure 10. We consider four cases;
in each we will find an $H$ with $\Gamma(H)=\gamma$, concluding the proof.

  1. (i)

Case $\mathbf{v}_{C},\mathbf{v}_{D}\in\gamma$: This implies $\gamma$ contains
$\\{A,B,C,D\\}$, which is a circuit. Thus, it must be that
$\gamma=\\{A,B,C,D\\}$ and hence $\Gamma(\\{w_{n}\\})=\gamma$.

  2. (ii)

Case $\mathbf{v}_{C}\in\gamma$, $\mathbf{v}_{D}\notin\gamma$: Since
$\mathbf{v}_{A}=\mathbf{v}_{F}+\mathbf{e}_{g}+\mathbf{e}_{e}+\mathbf{e}_{b}$,
$\mathbf{v}_{B}=\mathbf{v}_{F}+\mathbf{e}_{g}+\mathbf{e}_{b}$, and
$\mathbf{v}_{C}=\mathbf{v}_{F}+\mathbf{e}_{g}+\mathbf{e}_{e}$, then $\gamma$
must contain $\mathbf{v}_{F}$ since $\mathbf{v}_{F}$ is the only other vertex
in $\mathcal{O}(T)$ whose $f$-th entry is nonzero. In this case, $\gamma$
gives rise to a minimal dependence relation of the form

$\alpha(\mathbf{v}_{A}-\mathbf{v}_{B}-\mathbf{v}_{C}+\mathbf{v}_{F})+R=\mathbf{0}$

for some nonzero $\alpha\in\mathbb{R}$, and $R$ is a nonzero linear
combination of vertices of $\mathcal{O}(T)$ that does not involve
$\mathbf{v}_{A},\mathbf{v}_{B},\mathbf{v}_{C},\mathbf{v}_{D},\mathbf{v}_{E}$,
or $\mathbf{v}_{F}$. As
$\mathbf{v}_{A}-\mathbf{v}_{B}-\mathbf{v}_{C}=-\mathbf{v}_{D}$, then

$\alpha(\mathbf{v}_{F}-\mathbf{v}_{D})+R=\mathbf{0}$

is another minimal dependence relation consisting of vertices
$\gamma^{\prime}\subseteq\mathcal{O}(T)$ so there exists
$H^{\prime}\in\mathcal{G}(\mathbf{u})$ such that
$\Gamma(H^{\prime})=\gamma^{\prime}$, and it follows that
$\Gamma(H^{\prime}\cup\\{w_{n}\\})=\gamma$.

  3. (iii)

Case $\mathbf{v}_{C}\notin\gamma$, $\mathbf{v}_{F}\in\gamma$: By a similar
analysis as above, it must be that $\gamma$ is the circuit $\\{A,B,E,F\\}$,
since

$\mathbf{v}_{A}-\mathbf{v}_{B}-\mathbf{v}_{E}+\mathbf{v}_{F}=\mathbf{0},$

and $H$ is the subgraph induced on $\\{w_{n-1},w_{n}\\}$, where
$\Gamma(H)=\gamma$.

  4. (iv)

Case $\mathbf{v}_{C},\mathbf{v}_{F}\notin\gamma$: Since
$\mathbf{v}_{C}\notin\gamma$, we must have $\mathbf{v}_{E}\in\gamma$ as
$\mathbf{v}_{A}=\mathbf{v}_{B}+\mathbf{e}_{e}$ and $\mathbf{v}_{E}$ is the
only other vertex in $\mathcal{O}(T)$ whose $e$-th coordinate is nonzero.
Since $A,B,E<F$, then the $f$-th entry of each of
$\mathbf{v}_{A},\mathbf{v}_{B},\mathbf{v}_{E}$ are nonzero. This implies that
$\mathbf{v}_{D}$ is in $\gamma$ since the only other vertex in
$\mathcal{O}(T)$ whose $f$-th entry is nonzero is $\mathbf{v}_{F}$.

Thus, $\gamma$ gives rise to a minimal dependence relation of the form

$\alpha(\mathbf{v}_{A}-\mathbf{v}_{B}+\mathbf{v}_{D}-\mathbf{v}_{E})+R=\mathbf{0}$

for some nonzero $\alpha\in\mathbb{R}$, and $R$ is a nonzero linear
combination of vertices of $\mathcal{O}(T)$ that does not involve
$\mathbf{v}_{A},\mathbf{v}_{B},\mathbf{v}_{C},\mathbf{v}_{D},\mathbf{v}_{E}$,
or $\mathbf{v}_{F}$. As
$\mathbf{v}_{A}-\mathbf{v}_{B}+\mathbf{v}_{D}=\mathbf{v}_{C}$, then

$\alpha(\mathbf{v}_{C}-\mathbf{v}_{E})+R=\mathbf{0}$

is another minimal dependence relation consisting of vertices
$\gamma^{\prime}\subseteq\mathcal{O}(T)$ so there exists
$H^{\prime}\in\mathcal{G}(\mathbf{u})$ such that
$\Gamma(H^{\prime})=\gamma^{\prime}$, and
$\Gamma(H^{\prime}\cup\\{w_{n}\\})=\gamma$.

∎

######  Remark 4.6.

Theorem 4.5 does not hold for a generalized snake word $\mathbf{w}$ outside of
$\mathcal{V}$. Computational evidence suggests that the size of
$\mathcal{G}(\mathbf{w})$ is an upper bound for the number of circuits of
$\mathcal{O}(Q_{\mathbf{w}})$.

Next, we obtain a number of corollaries about the structure of the circuits in
the vertex set of $\mathcal{O}(Q_{\mathbf{w}})$.

######  Corollary 4.7.

Let $\mathbf{w}\in\mathcal{V}$. A circuit $Z$ with partition $(Z_{+},Z_{-})$
in the vertex set of $\mathcal{O}(Q_{\mathbf{w}})$ has an affine dependence
relation of the form

$\sum\limits_{j\in Z_{+}}\mathbf{v}_{j}=\sum\limits_{j\in
Z_{-}}\mathbf{v}_{j}.$

In particular, $|{Z_{-}}|=|{Z_{+}}|$.

###### Proof.

By proof of Theorem 4.5, a circuit $Z=\Gamma(H)$ for some nonempty connected
induced subgraph $H$ of $G(\mathbf{w})$. Moreover, an affine dependence
relation for $Z$ is given in (1), where by construction every vertex of $Z$
appears with coefficient $\pm 1$. This shows that there is an affine
dependence relation for $Z$ as in the statement of the corollary. Furthermore,
we conclude that $|{Z_{-}}|=|{Z_{+}}|$, because the dependence is affine. ∎

######  Corollary 4.8.

Let $H=\\{w_{i_{1}},\ldots,w_{i_{k}}\\}$ be a connected induced subgraph of
$G$ induced by the subword $w_{i_{1}}\cdots w_{i_{k}}$ of
$\mathbf{w}=w_{0}\cdots w_{n}\in\mathcal{V}$ such that $i_{1}<\cdots<i_{k}$.
Suppose $H^{\prime}=H\cup\\{w_{i_{j}}\\}$ is a connected induced subgraph of
$G$ such that $i_{k}<i_{j}$. Then

  1. (a)

If $w_{i_{j}}=w_{i_{k}}$, then $|\Gamma(H^{\prime})|=|\Gamma(H)|$.

  2. (b)

If $w_{i_{j}}\neq w_{i_{k}}$, then $|\Gamma(H^{\prime})|=|\Gamma(H)|+2$.

In the case where $H=\\{\varepsilon\\}$, $|\Gamma(H^{\prime})|=|\Gamma(H)|$.
Thus, the smallest circuits in the vertex set of $\mathcal{O}(Q_{\mathbf{w}})$
have four vertices. The largest circuits have $4+2t$ vertices where $t$ is the
number of turns (an occurrence of $LLR$ or $RRL$) in $\mathbf{w}$.

Using the bijection of Theorem 4.5, we can recursively compute the number of
circuits in the vertex set of $\mathcal{O}(Q_{\mathbf{w}})$.

######  Corollary 4.9.

Let $\mathbf{u}=w_{0}\cdots w_{n-1}\in\mathcal{V}$ and
$\mathbf{w}=\mathbf{u}w_{n}\in\mathcal{V}$. Let $N_{k}$ be the number of
connected induced subgraphs of $G(\mathbf{u})$ that contain $w_{k}$ but not
$w_{k+1}$. Then $|\mathcal{G}(\varepsilon)|=1$, $|\mathcal{G}(\varepsilon
w_{1})|=3$, and

  1. (a)

If $w_{n}=w_{n-1}$, then
$|\mathcal{G}(\mathbf{w})|=|\mathcal{G}(\mathbf{u})|+N_{n-1}+1$.

  2. (b)

If $w_{n}\neq w_{n-1}$, then
$|\mathcal{G}(\mathbf{w})|=|\mathcal{G}(\mathbf{u})|+N_{n-1}+N_{n-2}+1$.

###### Proof.

  1. (a)

If $w_{n}=w_{n-1}$, then $\deg_{G(\mathbf{w})}w_{n}=1$. Thus for any connected
induced subgraph $H$ of $G(\mathbf{w})$ that contains $w_{n}$, the connected
induced subgraph $H^{\prime}=H\backslash\\{w_{n}\\}$ contains $w_{n-1}$. From
the proof of Theorem 4.5, every circuit supported on the squares corresponding
to $H$ has a corresponding circuit supported on the squares corresponding to
$H^{\prime}$. The claim follows as $N_{n-1}$ counts the subgraphs of
$G(\mathbf{u})$ which contain $w_{n-1}$ and $1$ counts the subgraph
$\\{w_{n}\\}$.

  2. (b)

If $w_{n}=w_{n-1}$, then $\deg_{G(\mathbf{w})}w_{n}=2$. Thus for any connected
induced subgraph $H$ of $G(\mathbf{w})$ that contains $w_{n}$, the connected
induced subgraph $H^{\prime}=H\backslash\\{w_{n}\\}$ contains at least one of
$w_{n-2}$ and $w_{n-1}$. From the proof of Theorem 4.5, every circuit
supported on the squares corresponding to $H$ has a corresponding circuit
supported on the squares corresponding to $H^{\prime}$. The claim follows as
$N_{n-2}$ is the number of connected induced subgraphs of $G(\mathbf{u})$
which contain $w_{n-2}$ but not $w_{n-1}$, $N_{n-1}$ is the number of
connected induced subgraphs of $G(\mathbf{u})$ which contain $w_{n-1}$, and
$1$ counts the subgraph $\\{w_{n}\\}$.

∎

######  Remark 4.10.

When $\mathbf{w}=\varepsilon RRLLRRLL\ldots$, the poset
$Q_{\mathbf{w}}=P(\varepsilon RLRLRL\ldots)=S_{k}$ is the snake poset. The
number of circuits of the order polytope of the snake poset is equal to the
number of nonempty connected induced subgraphs of the graph $TS_{2k+1}$,
defined as follows. For odd $n$, let $TS_{n}$ denote the graph on $n$ vertices
formed by taking the the path graph on $n$ vertices $P_{n}$ and adding edges
$(2i-1,2i+1)$ for $i=1,\dots,(n-1)/2$. The graph $TS_{n}$ is called a
_triangular snake graph_ ; see [8] and the references therein for additional
information about triangular snakes.

The properties of circuits imply the following results regarding
triangulations of $\mathcal{O}(Q_{\mathbf{w}})$.

######  Lemma 4.11.

Let $\mathbf{w}\in\mathcal{V}$. If two triangulations of the polytope
$\mathcal{O}(Q_{\mathbf{w}})$ are connected by a flip, then they have the same
number of simplices.

###### Proof.

Let $\mathcal{T}_{1},\mathcal{T}_{2}$ be a pair of triangulations of
$\mathcal{O}(Q_{\mathbf{w}})$ that differ by a flip at circuit $Z$. Then
$\mathcal{T}_{1},\mathcal{T}_{2}$ are related as in Theorem 2.7. By Corollary
4.7, we have $|{Z_{-}}|=|{Z_{+}}|$, which implies that the two triangulations
$\mathcal{T}_{Z}^{-},\mathcal{T}_{Z}^{+}$ of $Z$ have the same number of
simplices. Therefore, because by definition the link $\mathrm{L}$ is disjoint
from both $\mathcal{T}_{Z}^{-},\mathcal{T}_{Z}^{+}$, we see that
$\mathcal{T}_{1}=\mathcal{T}_{Z}^{+}\ast\mathrm{L}$ and
$\mathcal{T}_{2}=\mathcal{T}_{Z}^{-}\ast\mathrm{L}$ also have the same number
of simplices. This shows that the number of simplices in a triangulation does
not change when performing a flip. ∎

######  Theorem 4.12.

For $\mathbf{w}\in\mathcal{V}$, every vertex of the secondary polytope of
$\mathcal{O}(Q_{\mathbf{w}})$ is a unimodular triangulation. Thus, every
triangulation of $\mathcal{O}(Q_{\mathbf{w}})$ is unimodular.

###### Proof.

The vertices of a secondary polytope of $\mathcal{O}(Q_{\mathbf{w}})$
correspond to regular triangulations of $\mathcal{O}(Q_{\mathbf{w}})$, see [5,
Theorem 5.1.9]. Moreover, all regular triangulations are connected by flips
[5, Theorem 5.3.1]. In particular, because the canonical triangulation of
$\mathcal{O}(Q_{\mathbf{w}})$ is regular and unimodular, then Lemma 4.11
implies that all regular triangulations of $\mathcal{O}(Q_{\mathbf{w}})$ are
also unimodular. Finally, it is a straightforward exercise to show that for a
lattice polytope $P$, the following conditions are equivalent: all full-
dimensional simplices are unimodular; all triangulations are unimodular; all
regular triangulations are unimodular; all placing triangulations are
unimodular. Hence, all triangulations are unimodular. ∎

##  5\. Flips and a twist action on triangulations

In this section we will take a deeper look at the 1-skeleton of the secondary
polytope. Starting from the canonical triangulation of
$\mathcal{O}(Q_{\mathbf{w}})$ we will see that for a length $k$ word there are
exactly $k+1$ flips, where a single flip corresponds to a local move along an
edge in the flip graph. As a consequence, we fully determine the flip graph of
regular triangulations in the special case of the ladder. We will also
introduce the notion of twists which act globally by inducing automorphisms on
the flip graph.

###  5.1. Theorems regarding twists, flips, and triangulations

Using the notation from Section 4, let $\mathbf{w}$ be a generalized snake
word in $\mathcal{V}$ and consider the associated poset $Q_{\mathbf{w}}$. In
this section, our goal is to prove four theorems about flips of regular
triangulations for $\mathcal{O}(Q_{\mathbf{w}})$. We state the four theorems
below; all undefined terms and proofs will be given in later subsections.
First, we classify the flips that can be made from the canonical triangulation
of $\mathcal{O}(Q_{\mathbf{w}})$.

######  Theorem 5.1.

Let $\mathbf{w}\in\mathcal{V}$ have length $k$. The canonical triangulation of
$\mathcal{O}(Q_{\mathbf{w}})$ admits exactly $k+1$ flips.

As an application, we determine the flip graph of regular triangulations for
the special case of a ladder. When $\mathbf{w}=\varepsilon L^{n-1}$,
$\widehat{P}\backslash\\{\hat{0},\hat{1}\\}$ is the product of a $(n+1)$-chain
and a $2$-chain. Thus the next result is a rephrasing of the well-known result
that the secondary polytope of the Cartesian product of an $n$-simplex and
$1$-simplex is an $n$-dimensional permutahedron [9, Section 16.7.1].

######  Theorem 5.2.

Let $\mathbf{w}=\varepsilon L^{n-1}$, and
$Q_{\mathbf{w}}=\mathrm{Irr}_{\wedge}(\widehat{P}(\mathbf{w}))$. The flip
graph of triangulations of $\mathcal{O}(Q_{\mathbf{w}})$ is the Cayley graph
of the symmetric group $\mathfrak{S}_{n+1}$ with the simple transpositions as
the generating set.

Third, we introduce the following group. Let
$\widehat{P}=\widehat{P}(\mathbf{w})$ be defined as in the previous section.
We can then think of $\widehat{P}$ as being made up of $\widehat{0}$,
$\widehat{1}$, and ladders $\mathcal{L}^{1},\dots,\mathcal{L}^{t}$ for $t\geq
1$ defined as follows. Given the vertices $w_{0},\ldots,w_{k}$ of
$G(\mathbf{w})$, let $w_{i_{1}}$ be the first index such that there is an edge
from $w_{i_{1}}$ to $w_{i_{1}+2}$. Then $\mathcal{L}^{1}$ is the ladder in
$\widehat{P}$ induced by the elements of
$\cup_{j=0}^{i_{1}+1}\mathrm{Sq}(w_{j})$. Let $w_{i_{2}}$ be the next vertex
where there is an edge from $w_{i_{2}}$ to $w_{i_{2}+2}$. Then
$\mathcal{L}^{2}$ is the ladder in $\widehat{P}$ induced by the elements of
$\cup_{j=i_{1}+1}^{i_{2}+1}\mathrm{Sq}(w_{j})$. Inductively define
$\mathcal{L}^{i}$ in a similar fashion. Note that by definition these ladders
are disjoint except that $\mathcal{L}^{i}\cap\mathcal{L}^{i+1}$ is a single
square corresponding to a corner box in $\widehat{P}$. That is,
$\mathcal{L}^{i}\cap\mathcal{L}^{i+1}$ comes from the underlined letter $\dots
R\underline{R}L\dots$ or $\dots L\underline{L}R\dots$ in the expression for
$\mathbf{w}$. Moreover, we index the ladders so that $y$, the top element of
$\mathcal{L}^{1}$, is covered by $\widehat{1}$ in $\widehat{P}$. That is,
$y\prec\widehat{1}.$ Since $\mathbf{w}$ avoids subwords $LRL$ and $RLR$, each
$\mathcal{L}^{i}$, for $1<i<t$, consists of at least three squares and
$\mathcal{L}^{1},\mathcal{L}^{t}$ consist of at least two squares, except for
the case where $\mathbf{w}=\varepsilon$, in which case we have one square and
one ladder. For example, in Figure 5 the poset $\widehat{P}$ consists of five
ladders $\mathcal{L}^{1},\dots,\mathcal{L}^{5}$ made up of $4,3,5,6,$ and $3$
boxes respectively.

Let $V_{0}$ denote the set of vertices of $\widehat{P}$. Next, we define a
collection of certain permutations on elements of $V_{0}$. Consider the ladder
$\mathcal{L}^{i}$ for $i\in[t]$ in the poset $\widehat{P}$. Then
$\mathcal{L}^{i}$ has the following structure up to a reflection of
$\widehat{P}$ in a vertical axis. Label the vertices of $\mathcal{L}^{i}$ as
$x_{1},\dots,x_{s}$ for some even integer $s$ as in Figure 11. In the case
where $\mathbf{w}=\varepsilon$, we resolve the ambiguity of the labeling by
choosing the convention that the left and right elements in the antichain of
the square have labels $x_{2}$ and $x_{3}$ respectively.

$x_{1}$$x_{3}$$x_{2}$$x_{4}$$x_{5}$$x_{6}$

$\ddots$

$\ddots$

$\ddots$

$w_{p-1}$$w_{p}$$w_{p+1}$$w_{q-1}$$w_{q}$$w_{q+1}$$x_{s-5}$$x_{s-3}$$x_{s-1}$$x_{s-4}$$x_{s-2}$$x_{s}$$x_{1}$$x_{3}$$x_{2}$$x_{4}$$x_{5}$$x_{6}$

$\ddots$

$\ddots$

$\ddots$

$w_{p-1}$$w_{p}$$w_{p+1}$$w_{q-1}$$w_{q}$$w_{q+1}$$x_{s-5}$$x_{s-3}$$x_{s-1}$$x_{s-4}$$x_{s-2}$$x_{s}$
Figure 11. Ladder $\mathcal{L}^{i}$ in $\widehat{P}$ containing boxes with
labels $w_{p},\dots,w_{q}$, where $w_{p}<w_{p+1}<\cdots<w_{q}$. The left
(right) represents the case where $w_{q}=L$ ($w_{q}=R$).

######  Definition 5.3.

Given a ladder $\mathcal{L}^{i}$, define $\tau_{i}\in\mathfrak{S}_{|V_{0}|}$
to be the permutation of $V_{0}$ such that for $v\in V_{0}$,

$\tau_{i}(v)=\begin{cases}x_{j-1},&\text{if }v=x_{j}\text{ and }j\in[s]\text{
is even,}\\\ x_{j+1},&\text{if }v=x_{j}\text{ and }j\in[s]\text{ is odd,}\\\
v,&\text{otherwise.}\end{cases}$

Hence, $\tau_{i}$ acts on $V_{0}$ by reflecting the vertices of
$\mathcal{L}^{i}$ across a diagonal and fixing the remaining vertices. The
next lemma says that the set of $\tau_{i}$ for $i\in[t]$ generate a
commutative subgroup of $\mathfrak{S}_{|V_{0}|}$.

######  Lemma 5.4.

For all $\tau_{i},\tau_{r}\in\mathfrak{S}_{|V_{0}|}$, the following properties
hold.

  * (a)

$\tau_{i}^{2}=1$

  * (b)

$\tau_{i}\tau_{r}=\tau_{r}\tau_{i}$

###### Proof.

Part (a) follows directly from the definition of $\tau_{i}$. Part (b) is
straightforward when $|r-i|\geq 2$ because the ladders
$\mathcal{L}^{r},\mathcal{L}^{i}$ have no vertices in common. The case $r=i$
follows from part (a), so it suffices to consider the case $r=i+1$. Moreover,
it is enough to check the action of the $\tau$’s on the vertices of the square
in $\mathcal{L}^{i}\cap\mathcal{L}^{i+1}$. Label the vertices of this square
as $x_{a},x_{b},x_{c},x_{d}$ and consider the computations
$\tau_{i}\tau_{i+1}$ and $\tau_{i+1}\tau_{i}$, as shown in Figure 12. This
shows that $\tau_{i}\tau_{i+1}=\tau_{i+1}\tau_{i}$ as desired. ∎

$x_{a}$$x_{c}$$x_{b}$$x_{d}$

$\ddots$

$\ddots$

$\Bigg{\\{}$$\mathcal{L}^{i}$$\Bigg{\\{}$$\mathcal{L}^{i+1}$$x_{a}$$x_{c}$$x_{b}$$x_{d}$$\tau_{i}$$\tau_{i+1}$$\tau_{i+1}$$\tau_{i}$$x_{c}$$x_{a}$$x_{d}$$x_{b}$$x_{b}$$x_{d}$$x_{a}$$x_{c}$$x_{d}$$x_{b}$$x_{c}$$x_{a}$
Figure 12. The action of $\tau_{i}$ and $\tau_{i+1}$ commute.

######  Definition 5.5.

Let $\mathfrak{T}(\mathbf{w})$ denote the subgroup of $\mathfrak{S}_{|V_{0}|}$
generated by the set of the $\tau_{i}$’s. We call $\mathfrak{T}(\mathbf{w})$
the twist group of $Q_{\mathbf{w}}$. Elements of $\mathfrak{T}(\mathbf{w})$
are called _twists_ and the elements $\tau_{i}$ are called _elementary
twists_.

Note that by Lemma 5.4, $\mathfrak{T}(\mathbf{w})=\langle\tau_{i}\mid
i\in[t]\rangle$ is isomorphic to $\mathbb{Z}_{2}^{t}$. The fact that
elementary twists commute will be an important factor in several proofs in
this section. As the next theorem demonstrates, the twist group acts on the
component of the flip graph of triangulations of $\mathcal{O}(Q_{\mathbf{w}})$
containing the canonical triangulation, and flips are preserved by twists. A
priori, a simplex $\sigma$ in the triangulation $T$ after twisting becomes a
collection of vertices $\tau(\sigma)$ of $\mathcal{O}(Q_{\mathbf{w}})$ that
may or may not also form a simplex. Hence, a twist $\tau(\mathcal{T})$ of a
triangulation $\mathcal{T}$ is a collection of subsets of vertices obtained by
applying the twist $\tau$ to every simplex in $\mathcal{T}$, so
$\tau(\mathcal{T})$ is not necessarily a triangulation. However, in the case
when twisting results in a triangulation, the following theorem says that
twists and flips behave well with each other.

Recall that if $Z$ is a circuit in $\mathcal{O}(Q_{\mathbf{w}})$ and
$\mathcal{T}$ is a triangulation of $\mathcal{O}(Q_{\mathbf{w}})$ that admits
a flip using $Z$, then $\mathcal{T}=\mathcal{T}_{Z}^{+}$ and
$\mathcal{T}_{Z}^{-}$ are the triangulations related by flips at $Z$.

######  Theorem 5.6.

Let $\mathbf{w}\in\mathcal{V}$,
$Q_{\mathbf{w}}=\mathrm{Irr}_{\wedge}(\widehat{P}(\mathbf{w}))$, and let
$\mathcal{T}$ and $\tau(\mathcal{T})$ be two triangulations of
$\mathcal{O}(Q_{\mathbf{w}})$ where $\tau$ is a twist. If
$\mathcal{T}=\mathcal{T}_{Z}^{+}$ can be flipped at circuit $Z$ and
$\tau(\mathcal{T}_{Z}^{+})=\tau(\mathcal{T}_{Z}^{+})_{\tau(Z)}^{+}$, then
$\tau(\mathcal{T}_{Z}^{+})_{\tau(Z)}^{-}=\tau(\mathcal{T}_{Z}^{-})$. In other
words, the following diagram commutes.

$\textstyle{\mathcal{T}_{Z}^{+}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\text{flip
in
}Z}$$\scriptstyle{\text{t}wist}$$\textstyle{\mathcal{T}_{Z}^{-}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\text{t}wist}$$\textstyle{\tau(T_{Z}^{+})=\tau(\mathcal{T}_{Z}^{+})_{\tau(Z)}^{+}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\text{flip
in
}\tau(Z)}$$\textstyle{\tau(\mathcal{T}_{Z}^{+})_{\tau(Z)}^{-}=\tau(\mathcal{T}_{Z}^{-})}$

######  Corollary 5.7.

Let $\mathbf{w}\in\mathcal{V}$,
$Q_{\mathbf{w}}=\mathrm{Irr}_{\wedge}(\widehat{P}(\mathbf{w}))$, and let
$\mathcal{T}$ and $\tau(\mathcal{T})$ be two triangulations of
$\mathcal{O}(Q_{\mathbf{w}})$ where $\tau$ is a twist. Then $\mathcal{T}$ and
$\tau(\mathcal{T})$ admit the same number of flips.

###### Proof.

As will be seen later, a twist $\tau$ is an involution on $J(Q_{\mathbf{w}})$
that yields an involution on circuits of $\mathcal{O}(Q_{\mathbf{w}})$. Thus,
we can apply $\tau$ to $\tau(\mathcal{T})$ and recover $\mathcal{T}$. This
shows that there is a bijective correspondence between flips from
$\mathcal{T}$ and flips from $\tau(\mathcal{T})$. ∎

Lastly, we show that twists of regular triangulations lead to regular
triangulations.

######  Theorem 5.8.

Let $\mathbf{w}\in\mathcal{V}$,
$Q_{\mathbf{w}}=\mathrm{Irr}_{\wedge}(\widehat{P}(\mathbf{w}))$, and let
$\mathcal{T}_{\mathbf{w}}$ be the canonical triangulation of
$\mathcal{O}(Q_{\mathbf{w}})$. Then $\mathcal{T}_{\mathbf{w}}$ is a regular
triangulation with height function $\omega(x_{i})=2^{\rho(x_{i})}$ defined in
Definition 5.17. Furthermore, for any twist $\tau$,
$\tau(\mathcal{T}_{\mathbf{w}})$ is a regular triangulation with the
corresponding twisted height function.

For each of these theorems, we have dedicated one subsection that follows to
their proof.

###  5.2. Proof of Theorem 5.1

For the canonical triangulation of $\mathcal{O}(Q_{\mathbf{w}})$, simplices
correspond to maximal chains in $J(Q_{\mathbf{w}})$. In order for a circuit
$Z$ to be supported on a flip in the canonical triangulation, then either
$\mathcal{T}_{+}$ or $\mathcal{T}_{-}$ must be a subcomplex of the canonical
triangulation. Consider the circuits corresponding to a single square
$\mathrm{Sq}(w_{i})=\\{A,A\cup\\{a\\},A\cup\\{b\\},A\cup\\{a,b\\}\\}$ in
$J(Q_{\mathbf{w}})$. If we assign the left $A\cup\\{a\\}$ and right
$A\cup\\{b\\}$ vertices of the square to be have negative signs in the
circuit, and we assign positive signs to the upper vertex $A$ and the lower
vertex $A\cup\\{a,b\\}$, then the canonical triangulation contains
$\mathcal{T}_{-}$, where $\mathcal{T}_{-}$ consists of the two triangles each
formed by the positive vertices and one of the negative vertices in
$\mathrm{Sq}(w_{i})$. Further, for each of these triangles, the link in the
canonical triangulation is the set of all chains contained in $\\{x\in
J(Q_{\mathbf{w}})\mid x<A\cup\\{a,b\\}\\}\cup\\{x\in J(Q_{\mathbf{w}})\mid
x>A\\}$, and thus $\mathcal{T}_{-}$ can be flipped at $\mathrm{Sq}(w_{i})$.
However, $\mathcal{T}_{+}$ is not contained in the canonical triangulation,
because there is not a maximal chain in $J(Q_{\mathbf{w}})$ that runs through
the two negative vertices, which form an antichain in $J(Q_{\mathbf{w}})$.
Thus, for each of the $k+1$ squares in $J(Q_{\mathbf{w}})$, we can flip the
corresponding circuit.

If we have a circuit in $J(Q_{\mathbf{w}})$ that does not come from a square,
then we consider two cases. If the circuit is of size four, then the
corresponding connected induced subgraph has vertices
$w_{i_{1}},w_{i_{1}+1},\ldots,w_{i_{1}+r}$. In this case, because there are
elements of $J(Q_{\mathbf{w}})$ strictly between the elements of the circuit
and they lie in different ranks, the links are different for the two faces in
$\mathcal{T}_{-}$. For example, suppose that $\mathrm{Sq}(w_{i_{1}})$ consists
of the filters $A$, $A\cup\\{a\\}$, $A\cup\\{c\\}$, and $A\cup\\{a,c\\}$.
Suppose also that $\mathrm{Sq}(w_{i_{1}+r})$ consists of the filters $B$,
$B\cup\\{b\\}$, $B\cup\\{c\\}$, and $B\cup\\{b,c\\}$. See Figure 13 for an
example. Then the filters $A,A\cup\\{c\\},B\cup\\{b,c\\}$ form a triangle in
$\mathcal{T}_{-}$, as does $A,B\cup\\{b\\},B\cup\\{b,c\\}$. Note that
$B\cup\\{c\\}$ is in the link of the first triangle but not the second. A
similar argument holds in general, and thus this circuit does not support a
flip.

$A$$A\cup\\{a\\}$$A\cup\\{c\\}$$A\cup\\{a,c\\}$

$\ddots$

$\ddots$

$\ddots$

$B$$B\cup\\{b\\}$$B\cup\\{c\\}$$B\cup\\{b,c\\}$$w_{i_{1}+r}$$w_{i_{1}}$ Figure
13. A circuit failing the link condition.

For a circuit of size greater than four, the word defining the corresponding
induced subgraph either contains a subword of the form $w_{i_{j}}w_{i_{j}+2}$
or contains a turn, i.e., contains one of $RRL$, $LLR$, $RLL$, or $LRR$.
Consider the first case, where a subword of the form $w_{i_{j}}w_{i_{j}+2}$ is
present. See Figure 5 for an example with $w_{4}w_{6}$. In this case, it is
straightforward to verify that there exist at least two incomparable pairs in
the circuit, where the elements of each pair share the same sign in the
circuit and each pair has a different sign. Thus, both $\mathcal{T}_{+}$ and
$\mathcal{T}_{-}$ have simplices containing antichains, and hence the
canonical triangulation does not contain any triangulations arising from
circuits of this type.

Next consider the case where the induced subgraph contains a turn, i.e.,
contains one of $RRL$, $LLR$, $RLL$, or $LRR$. Again see Figure 5 for an
example with $w_{2}w_{3}w_{4}$. In this case, the existence of a turn implies
that there are two antichains $\\{A,B\\}$ and $\\{B,C\\}$ where each filter
has the same sign in the circuit. Again, this implies that both
$\mathcal{T}_{+}$ and $\mathcal{T}_{-}$ have simplices containing antichains,
and hence the canonical triangulation does not contain any triangulations
arising from circuits of this type.

Thus, the canonical triangulation admits only flips in circuits formed by the
squares, and each of the resulting triangulations is distinct, from which the
result follows.

###  5.3. Proof of Theorem 5.2

Let $\mathbf{w}=\varepsilon L^{n-1}$. Then
$\widehat{P}(\mathbf{w})\backslash\\{\hat{0},\hat{1}\\}$ is the ladder with
$n$ squares, and the graph $G(\mathbf{w})$ associated to
$\widehat{P}(\mathbf{w})$ is the path graph with $n$ vertices. By Theorem 4.5,
the circuits of the vertex set of the order polytope
$\mathcal{O}(Q_{\mathbf{w}})$ are in bijection with the nonempty connected
induced subgraphs of $G(\mathbf{w})$, so in this context, every circuit has
exactly $4$ elements, corresponding to some nonempty connected subgraph of the
path graph with $n$ vertices. Since the circuits never contain $\hat{0}$ or
$\hat{1}$, then without loss of generality we only need to concern ourselves
with the remaining $2(n+1)$ vertices of
$\widehat{P}(\mathbf{w})\backslash\\{\hat{0},\hat{1}\\}$, which we label as
$[n+1]\cup[(n+1)^{\prime}]$. See Figure 14.

$1$$2$$3$$n-1$$n$$n+1$$1^{\prime}$$2^{\prime}$$3^{\prime}$$n-1^{\prime}$$n^{\prime}$$n+1^{\prime}$

$\ddots$

$\ddots$

$\mathrm{Sq}_{1}$$\mathrm{Sq}_{2}$$\mathrm{Sq}_{n-1}$$\mathrm{Sq}_{n}$ Figure
14. The $n$-ladder $J(Q_{\mathbf{w}})=\widehat{P}(\mathbf{w})$ of Theorem 5.2.

There are $\binom{n+1}{2}$ circuits; explicitly, the circuits are
$Z_{i,j}=\\{i,i^{\prime},j,j^{\prime}\\}$ for $1\leq i<j\leq n+1$. In
particular, it follows from Theorem 5.1 that the circuits which support a flip
in the canonical triangulation $\mathcal{T}_{\mathbf{w}}$ are $Z_{i,i+1}$ for
$i=1,\ldots,n$.

Next, we define maps on the labels of
$\widehat{P}(\mathbf{w})\backslash\\{\hat{0},\hat{1}\\}$. Given $1\leq i\leq
n$, if the labels on the four vertices of the $i$-th square $\mathrm{Sq}_{i}$
are $a,a^{\prime},b,b^{\prime}$, then $\pi_{i}$ swaps $a$ with $b$, and
$a^{\prime}$ with $b^{\prime}$. In other words, $\pi_{i}$ permutes places, not
values. See Figure 15. Compare this to the twist maps which permute values,
not places. It is clear from this definition that $\pi_{i}$ acts as a simple
transposition on the labels of
$\widehat{P}(\mathbf{w})\backslash\\{\hat{0},\hat{1}\\}$ so that
$\pi_{i}^{2}=1$, and moreover, $\pi_{1},\ldots,\pi_{n}$ generate the symmetric
group $\mathfrak{S}_{n+1}$.

$a$$b$$a^{\prime}$$b^{\prime}$

$\ddots$

$\ddots$

$\ddots$

$\ddots$

$\mathrm{Sq}_{i-1}$$\mathrm{Sq}_{i}$$\mathrm{Sq}_{i+1}$$\longrightarrow$$\pi_{i}$$b$$a$$b^{\prime}$$a^{\prime}$

$\ddots$

$\ddots$

$\ddots$

$\ddots$

$\mathrm{Sq}_{i-1}$$\mathrm{Sq}_{i}$$\mathrm{Sq}_{i+1}$ Figure 15. The action
of $\pi_{i}$ on the labels of $\widehat{P}(\varepsilon L^{n-1})$.

######  Lemma 5.9.

Let $\mathcal{T}_{\mathbf{w}}$ denote the canonical triangulation of
$\mathcal{O}(Q_{\mathbf{w}})$. Let $\mathcal{U}_{i}$ denote the triangulation
of $\mathcal{O}(Q_{\mathbf{w}})$ that differs from $\mathcal{T}_{\mathbf{w}}$
by the flip supported at the circuit $Z_{i,i+1}$ for $1\leq i<n$. Then the
simplices of $\mathcal{U}_{i}$ are the maximal chains of the poset
$\pi_{i}\cdot\widehat{P}(\mathbf{w})$. Thus, $\mathcal{U}_{i}$ is a canonical
triangulation of an order polytope, and hence is regular.

###### Proof.

Let

$Z_{i,i+1}=((Z_{i,i+1})_{+},(Z_{i,i+1})_{-})=(\\{i,(i+1)^{\prime}\\},\\{i+1,i^{\prime}\\})$

be the oriented circuit so that the canonical triangulation
$\mathcal{T}_{\mathbf{w}}$ contains $\mathcal{T}_{Z}^{-}$ but not
$\mathcal{T}_{Z}^{+}$. The $n+1$ maximal chains in $\widehat{P}(\mathbf{w})$
are of the form

$C_{i}:1,2,\ldots,i,i^{\prime},\ldots,n^{\prime},(n+1)^{\prime}$

for $i=1,\ldots,n+1$. To make a flip from $\mathcal{T}_{\mathbf{w}}$ to
$\mathcal{U}_{i}$, each maximal chain in $\widehat{P}(\mathbf{w})$ containing
$\\{i,i+1,(i+1)^{\prime}\\}$ has that triplet replaced by
$\\{i,i+1,i^{\prime}\\}$, and every maximal chain in $\widehat{P}(\mathbf{w})$
containing $\\{i,i^{\prime},(i+1)^{\prime}\\}$ has that triplet replaced by
$\\{i+1,i^{\prime},(i+1)^{\prime}\\}$. So the flip affects only the two chains
$C_{i}$ and $C_{i+1}$, where effectively, $(i+1)^{\prime}$ is replaced by
$i^{\prime}$, and $i$ is replaced by $i^{\prime}$. Thus the simplices of
$\mathcal{U}_{i}$ are precisely the maximal chains in the poset
$\pi_{i}\cdot\widehat{P}(\mathbf{w})$. ∎

We will denote the triangulation $\mathcal{U}_{i}$ by
$\pi_{i}\mathcal{T}_{\mathbf{w}}$.

######  Lemma 5.10.

Let $\mathcal{T}$ be a regular triangulation of $\mathcal{O}(Q_{\mathbf{w}})$
whose simplices are maximal chains in a labeled $n$-ladder poset
$\widehat{P}_{\mathcal{T}}$. There are exactly $n$ regular triangulations that
differ from $\mathcal{T}$ by a circuit flip, and each of these triangulations
have simplices which are the maximal chains in
$\pi_{i}\widehat{P}_{\mathcal{T}}$ for $i=1,\ldots,n$.

###### Proof.

Proceed by induction on the number of flips away from the canonical
triangulation $\mathcal{T}_{\mathbf{w}}$. The base case follows from Lemma
5.9. Suppose $\mathcal{T}=\pi_{i_{\ell}}\cdots\pi_{i_{1}}\mathcal{T}_{c}$ for
some (reduced) sequence of transpositions
$\pi_{i_{\ell}},\ldots,\pi_{i_{1}}\in\mathfrak{S}_{n+1}$. Let
$\pi=\pi_{i_{\ell}}\cdots\pi_{i_{1}}$. The circuits of $\mathcal{T}$ are then

$Z_{\pi^{-1}(j),\pi^{-1}(k)}=\\{\pi^{-1}(j),\pi^{-1}(j^{\prime}),\pi^{-1}(k),\pi^{-1}(k^{\prime})\\}$

for $1\leq j<k\leq n+1$. In particular, for $k=1,\ldots,n$, the four elements
of the circuit $Z_{\pi^{-1}(k),\pi^{-1}(k+1)}$ are labels on the square
$\mathrm{Sq}_{\pi^{-1}(k)}$ of the poset $\widehat{P}_{\mathcal{T}}$, and
these are the only circuits which support a flip as they are the only ones
whose links are the same for the two faces in $\mathcal{T}_{Z}^{-}$. So a flip
in this circuit yields a triangulation $\pi\mathcal{T}$ whose simplices are
maximal chains in the poset $\pi\cdot\widehat{P}_{\mathcal{T}}$. ∎

Since the transpositions $\pi_{1},\ldots,\pi_{n}$ generate
$\mathfrak{S}_{n+1}$, the proof of Theorem 5.2 now follows.

###  5.4. Proof of Theorem 5.6

We use the notation from Definition 5.5. We can naturally extend the action of
$\mathfrak{T}(\mathbf{w})$ on $V_{0}$ to the action of
$\mathfrak{T}(\mathbf{w})$ on subsets of $V_{0}$. The following lemma states
that the twist group also acts on the circuits of the vertices of
$\mathcal{O}(Q_{\mathbf{w}})$.

######  Lemma 5.11.

Let $Z=(Z_{+},Z_{-})$ be a circuit on $V_{0}$ and
$\tau\in\mathfrak{T}(\mathbf{w})$. Then $\tau(Z):=(\tau(Z_{+}),\tau(Z_{-}))$
is also a circuit on $V_{0}$.

###### Proof.

Because $\mathfrak{T}(\mathbf{w})$ is abelian, it suffices to show that
$\tau_{k}(Z)$ is a circuit for every $k$. We use the labeling of the squares
and vertices of $\mathcal{L}^{k}$ given in Figure 11. Also, by Theorem 4.5 we
have $Z=\Gamma(H_{\bf w^{\prime}})$, where $H_{\bf w^{\prime}}$ is an induced
connected subgraph of $G(\bf w)$ corresponding to a subword ${\bf w^{\prime}}$
of ${\bf w}$.

Observe that if $Z$ does not contain any vertex of $\mathcal{L}^{k}$ then
$\tau_{k}(Z)=Z$ and the lemma holds. If every vertex of $Z$ is also a vertex
of $\mathcal{L}^{k}$, then $Z$ consists of four vertices and we have
$Z=(\\{x_{i},x_{j}\\},\\{x_{i+1},x_{j-1}\\})$ up to interchanging
$Z_{+},Z_{-}$ for some $i$ odd and $j$ even. Then,

$\tau_{k}(Z)=(\\{x_{i+1},x_{j-1}\\},\\{x_{i},x_{j}\\})=(Z_{-},Z_{+})$

which is the same circuit as $Z$. It remains to consider the case where $Z$
contains vertices both in $\mathcal{L}^{k}$ and outside of $\mathcal{L}^{k}$.
In this case, it must be that $Z=\Gamma(H_{\bf w^{\prime}})$ where $\bf
w^{\prime}$ contains one or both of $w_{p-1}$ and $w_{q+1}$.

If ${\bf w^{\prime}}$ contains $w_{p-1}$ and no letter in $\mathcal{L}^{k}$,
then $\tau_{k}$ applied to $Z$ replaces $x_{1},x_{3}$ with $x_{2},x_{4}$
respectively. Hence, $\tau_{k}(Z)=\Gamma(H_{{\bf w^{\prime}}w_{p}})$ is again
a circuit. Similar computation holds if ${\bf w^{\prime}}$ contains $w_{q-1}$
and no letter in $\mathcal{L}^{k}$. Since $\tau_{k}^{2}=1$ by Lemma 5.4(a),
this also resolves the case when $\bf w^{\prime}$ ends in $w_{p-1}w_{p}$ or
starts with $w_{q}w_{q+1}$.

The cases when ${\bf w^{\prime}}$ contains $w_{p-1},w_{p+1}$ but not $w_{q+1}$
or ${\bf w^{\prime}}$ contains $w_{q-1},w_{q+1}$ but not $w_{p-1}$ follow
similarly to the case when $\bf w^{\prime}$ contains both $w_{p-1}$ and
$w_{q+1}$; therefore, we only provide a detailed proof for the latter case.
Suppose that $\bf w^{\prime}$ contains both $w_{p-1}$ and $w_{q+1}$. Then
${\bf w^{\prime}}$ contains $w_{p+1},\dots,w_{q-1}$ and it may or may not
contain each of $w_{p},w_{q}$. We treat the situation when ${\bf w^{\prime}}$
contains $w_{q}$ but not $w_{p}$, and the other possibilities follow
similarly. Up to interchanging $Z_{+}$ and $Z_{-}$, we have the following
situation where $x_{1},x_{s-2}\in Z_{-}$ and $x_{s-1},x_{4}\in Z_{+}$ and no
other vertex in $\mathcal{L}^{k}$ appears in the circuit $Z$. This is depicted
in the left-hand side of Figure 16.

In this case,

$\tau_{k}(Z_{-})=\left(Z_{-}\setminus\\{x_{1},x_{s-2}\\}\right)\cup\\{x_{2},x_{s-3}\\}$

and

$\tau_{k}(Z_{+})=\left(Z_{+}\setminus\\{x_{4},x_{s+1}\\}\right)\cup\\{x_{3},x_{s}\\}\,.$

In particular, $\tau_{k}(Z)=\Gamma(H_{\bf{w}^{\prime\prime}})$ where
${\bf{w}^{\prime\prime}}$ is obtained from $\bf{w}^{\prime}$ by adding $w_{p}$
and removing $w_{q}$. Therefore, $\tau_{k}(Z)$ is a circuit. The remaining
cases are proved in a similar fashion. This completes the proof of the lemma.
∎

$x_{1}$$-$$x_{3}$$x_{2}$$x_{4}$$+$

$\ddots$

$\ddots$

$\ddots$

$x_{s-3}$$x_{s-1}$$+$$x_{s-2}$$-$$x_{s}$$x_{1}$$x_{3}$$+$$x_{2}$$-$$x_{4}$

$\ddots$

$\ddots$

$\ddots$

$x_{s-3}$$-$$x_{s-1}$$x_{s-2}$$x_{s}$$+$$\tau_{k}$ Figure 16. Two cases for
proof of Lemma 5.11.

###### Proof of Theorem 5.6.

Let $\mathcal{T}=\mathcal{T}_{Z}^{+}$ and $\mathcal{T}_{Z}^{-}$ be
triangulations related by a flip at the circuit $Z$. Let $\mathcal{T}|_{Z}$
denote the restriction of $\mathcal{T}$ to the circuit $Z$. Since we can flip
$\mathcal{T}$ at $Z$, the links of simplices of $\mathcal{T}|_{Z}$ in
$\mathcal{T}$ match. By Lemma 5.11, the twist $\tau(Z)$ is also a circuit, so
the links of $\tau(\mathcal{T})|_{\tau(Z)}$ in $\tau(\mathcal{T})$ are
obtained from the links of $\mathcal{T}|_{Z}$ in $\mathcal{T}$ by applying the
permutation $\tau$. Thus, they also match. Therefore, we obtain two
triangulations related by a flip through $\tau(Z)$, denoted
$\tau(\mathcal{T})=\tau(\mathcal{T})_{\tau(Z)}^{+}$ and
$\tau(\mathcal{T})_{\tau(Z)}^{-}$. It suffices to show that
$\tau(\mathcal{T})_{\tau(Z)}^{-}$ and $\tau(\mathcal{T}_{Z}^{-})$ are the same
as sets.

Every full-dimensional simplex $\sigma$ in $\mathcal{T}=\mathcal{T}_{Z}^{+}$
that does not contain a simplex supported on $Z$ remains a simplex in
$\mathcal{T}_{Z}^{-}$. Hence $\tau(\mathcal{T}_{Z}^{-})$ contains
$\tau(\sigma)$ as a subset. Also, $\tau(\sigma)$ is a simplex of
$\tau(\mathcal{T})=\tau(\mathcal{T})_{\tau(Z)}^{+}$ that does not a simplex
supported on $\tau(Z)$, so it remains a simplex in
$\tau(\mathcal{T})_{\tau(Z)}^{-}$ after the flip. Every full-dimensional
simplex $\sigma$ in $\mathcal{T}$ that contains a simplex supported on $Z$
becomes $(\sigma\setminus\\{\sigma_{+}\\})\cup\\{\sigma_{-}\\}$ after the
flip, for some appropriate pair of subsets $\sigma_{+}$, $\sigma_{-}$ obtained
from $Z$ by removing a single element in $Z_{+}$, $Z_{-}$ respectively.
Similarly, $\tau(\sigma)$ contains a simplex supported on $\tau(Z)$, and after
the flip supported at the circuit $\tau(Z)$ it becomes
$(\tau(\sigma)\setminus\\{\tau(\sigma+)\\})\cup\\{\tau(\sigma_{-})\\}$ which
equals $\tau((\sigma\setminus\\{\sigma_{+}\\})\cup\\{\sigma_{-}\\})$. ∎

###  5.5. Proof of Theorem 5.8

Given a lattice $\widehat{P}=\widehat{P}(\mathbf{w})$, let
$Q_{\mathbf{w}}=\mathrm{Irr}_{\wedge}(\widehat{P})$ be the poset of meet-
irreducibles. Label the elements of $Q_{\mathbf{w}}$ as in Figure 4. Let
$\sigma$ be a full-dimensional simplex in the canonical triangulation of the
order polytope $\mathcal{O}(Q_{\mathbf{w}})$, i.e.,
$\sigma=\\{\mathbf{v}_{\varnothing},\mathbf{v}_{A_{0}},\dots,\mathbf{v}_{A_{m}}\\}$
is a collection of vertices in $\mathcal{O}(Q_{\mathbf{w}})$ that form a
maximal chain
$\mathbf{0}=\mathbf{v}_{\varnothing}<\mathbf{v}_{A_{0}}<\dots<\mathbf{v}_{A_{m}}=\mathds{1}_{m}$
in $\widehat{P}$, where $m=|Q_{\mathbf{w}}|$. Here $\mathbf{v}_{A_{i}}$ is an
indicator vector of $A_{i}\subset Q_{\mathbf{w}}$. Since the canonical
triangulation is unimodular, we know that every simplex $\sigma$ has
normalized volume $1$. Let $M_{\sigma}$ denote the matrix with columns
$\mathbf{v}_{A_{0}},\dots,\mathbf{v}_{A_{m}}$. We have the following fact that
will be used later in this subsection.

######  Remark 5.12.

A collection of points
$\sigma=\\{\mathbf{v}_{\varnothing},\mathbf{v}_{B_{0}},\dots,\mathbf{v}_{B_{m}}\\}$
in $\mathcal{O}(Q_{\mathbf{w}})$ is a simplex of the canonical triangulation
of $\mathcal{O}(Q_{\mathbf{w}})$ if and only if $\varnothing\subset
B_{0}\subset B_{1}\subset\cdots\subset B_{m}$ forms a maximal chain in
$\widehat{P}$, which holds if and only if $\det M_{\sigma}\not=0$.

$x_{1}=\langle a\rangle$$x_{3}$$x_{2}=\langle a+1\rangle$$x_{4}$$x_{5}=\langle
a+2\rangle$$x_{6}$

$\ddots$

$\ddots$

$\ddots$

$x_{s-5}$$x_{s-3}=\langle a+\frac{s}{2}-2\rangle$$x_{s-1}=\langle
a+\frac{s}{2}-1\rangle$$x_{s-4}$$x_{s-2}$$x_{s}$$\langle
a+\frac{s}{2}\rangle$$\langle a-1\rangle$ Figure 17. Ladder $\mathcal{L}^{k}$
in $\widehat{P}$.

Now we analyze the action of a twist $\tau_{k}$ on the $0/1$ entries of
vertices in $\mathcal{O}(Q_{\mathbf{w}})$. Consider the ladder
$\mathcal{L}^{k}$ in $\widehat{P}$ with vertices labeled $x_{1},\dots,x_{s}$
as in Figure 17 and let $[a]=\\{0,1,2,\dots,a\\}$. Note the inclusion of $0$
in the set $[a]$. Then, after identifying $B$ with $\mathbf{v}_{B}$, we have
the following description of the vertices, for some $a^{\prime}\leq a-1$.

$\begin{array}[]{lll}x_{1}=\mathbf{v}_{[a]\setminus\\{a^{\prime}\\}}=(1^{a^{\prime}},0,1^{a-a^{\prime}},0,\dots,0)&&x_{2}=\mathbf{v}_{[a+1]\setminus\\{a^{\prime}\\}}=(1^{a^{\prime}},0,1^{a-a^{\prime}+1},0,\dots,0)\\\
x_{3}=\mathbf{v}_{[a+1]\setminus\\{a+1\\}}=(1^{a+1},0,\dots,0)&&x_{4}=\mathbf{v}_{[a+1]}=(1^{a+2},0,\dots,0)\\\
x_{5}=\mathbf{v}_{[a+2]\setminus\\{a+1\\}}=(1^{a+1},0,1,0,\dots,0)&&x_{6}=\mathbf{v}_{[a+2]}=(1^{a+3},0,\dots,0)\\\
\vdots&&\vdots\\\
x_{s-1}=\mathbf{v}_{[a+\frac{s}{2}-1]\setminus\\{a+1\\}}=(1^{a+1},0,1^{\frac{s}{2}-2},0\dots,0)&&x_{s}=\mathbf{v}_{[a+\frac{s}{2}-1]}=(1^{a+\frac{s}{2}},0,\dots,0)\\\
\end{array}$

For example in Figure 4, if $k=5$ then $\mathcal{L}^{5}$ is the last ladder in
$\widehat{P}$ and in this case we have $a=15$ and $a^{\prime}=11$. Hence all
vertices of $\mathcal{O}(Q_{\mathbf{w}})$ in $\mathcal{L}^{k}$ are
characterized as follows.

######  Remark 5.13.

A vertex $\mathbf{v}_{A}\in\mathcal{L}^{k}$ if and only if
$[a]\setminus\\{a^{\prime}\\}\subset A$ and
$a+\frac{s}{2},a+\frac{s}{2}+1,\dots,m\not\in A$. Moreover, for every
$\mathbf{v}_{A}\in\mathcal{L}^{k}$, the vector $\tau_{k}(\mathbf{v}_{A})$ is
obtained from $\mathbf{v}_{A}$ by replacing a $0$ or $1$ in position $a+2$ by
$1$ or $0$, respectively.

The next result says that a twist of a canonical triangulation is again a
triangulation.

######  Theorem 5.14.

Let $\mathcal{T}_{\mathbf{w}}$ be the canonical triangulation of
$\mathcal{O}(Q_{\mathbf{w}})$. Then $\tau(\mathcal{T}_{\mathbf{w}})$ is also a
triangulation of $\mathcal{O}(Q_{\mathbf{w}})$ for every
$\tau\in\mathfrak{T}(\mathbf{w})$.

###### Proof.

We prove the theorem in two steps. First, we show that a twist of a simplex in
$\mathcal{T}_{\mathbf{w}}$ is also a simplex. Then, we show that no two
simplices in $\tau(\mathcal{T}_{\mathbf{w}})$ intersect in the interior of
$\mathcal{O}(Q_{\mathbf{w}})$. Since $\mathcal{T}_{\mathbf{w}}$ is a
unimodular triangulation and $\tau(\mathcal{T}_{\mathbf{w}})$ has the same
number of simplices as $\mathcal{T}_{\mathbf{w}}$, this implies the desired
result that $\tau(\mathcal{T}_{\mathbf{w}})$ is also a (unimodular)
triangulation of $\mathcal{O}(Q_{\mathbf{w}})$.

Let
$\sigma=\\{\mathbf{v}_{\varnothing},\mathbf{v}_{A_{0}},\dots,\mathbf{v}_{A_{m}}\\}$
be a simplex in $\mathcal{T}_{\mathbf{w}}$, and we claim that $\tau(\sigma)$
is also a simplex. Note that
$\tau(\mathbf{v}_{\varnothing})=\mathbf{v}_{\varnothing}$ and by Remark 5.12
it suffices to show that $\det M_{\tau(\sigma)}\not=0$. First, we address the
claim when $\tau=\tau_{k}$ is an elementary twist. Label the vertices $x_{i}$
of $\mathcal{L}^{k}$ by $\mathbf{v}_{A}$ for their corresponding subset $A$ of
$P$ as discussed earlier, see Figure 17. The determinant of $M_{\sigma}$ is
$\pm 1$, and by Remark 5.13 the two matrices $M_{\sigma},M_{\tau_{k}(\sigma)}$
differ only in row $a+2$. Recall that by construction, the entry $M_{\sigma}$
in position $(i,j)$ equals 1 if and only if $i-1\in A_{j-1}$. Then, since
$\varnothing\subset A_{0}\subset\dots\subset A_{m}$ is a maximal chain, a row
$i$ in $M_{\sigma}$ is of the form $[0^{q},1^{m+1-q}]$ for some $q\geq 0$ such
that $i-1\not\in A_{0},\dots,A_{q-1}$ and $i-1\in A_{q},\dots,A_{m}$. Let
$\text{Row}_{M}(i)$ denote the $i$-th row of the matrix $M$, so then

$\text{Row}_{M_{\sigma}}(a+2)=[0^{d},1^{m+1-d}]$

for some $d$. We will show that $M_{\tau_{k}(\sigma)}$ is obtained from
$M_{\sigma}$ by a row replacement operation consisting of three rows, as
follows. Let
$\mathbf{v}_{A_{b}},\mathbf{v}_{A_{b+1}},\dots,\mathbf{v}_{A_{c}}$ be vertices
of $\mathcal{L}^{k}\cap\sigma$. If $i\geq b$ then $a\in A_{i}$, while if $i<b$
then $a\not\in A_{i}$. Hence,

$\text{Row}_{M_{\sigma}}(a+1)=[0^{b},1^{m+1-b}]\,.$

Similarly, if $i\geq c+1$ then $a+s/2\in A_{i}$ and if $i<c+1$ then
$a+\frac{s}{2}\not\in A_{i}$. Hence,

$\text{Row}_{M_{\sigma}}(a+1+\frac{s}{2})=[0^{c+1},1^{m-c}]\,.$

Note that $b<d<c$. By Remark 5.13, the $(a+2)$-th row of
$M_{\tau_{k}(\sigma)}$ is obtained from the $(a+2)$-th row of $M_{\sigma}$ by
replacing $0$’s in columns indexed by
$\mathbf{v}_{A_{b}},\dots,\mathbf{v}_{A_{d-1}}$ by $1$’s, and replacing $1$’s
in columns $\mathbf{v}_{A_{d}},\dots,\mathbf{v}_{A_{c}}$ by $0$’s. Then

$\text{Row}_{M_{\tau_{k}(\sigma)}}(a+2)=[0^{b},1^{d-b},0^{c+1-d},1^{m-c}]$

while all other rows of $M_{\tau_{k}(\sigma)}$ remain the same. Then the
following equation holds.

(2)
$\text{Row}_{M_{\tau_{k}(\sigma)}}(a+1)-\text{Row}_{M_{\tau_{k}(\sigma)}}(a+2)+\text{Row}_{M_{\tau_{k}(\sigma)}}(a+1+\frac{s}{2})=[0^{m+1-d},\sigma
1^{d}]=\text{Row}_{M_{\sigma}}(a+2).$

We have shown that $M_{\tau_{k}(\sigma)}$ is obtained from $M_{\sigma}$ by a
row replacement operation, so $\det M_{\tau_{k}(\sigma)}=-\det(M_{\sigma})=\pm
1$. This shows that $\tau_{k}(\sigma)$ is also a simplex. In the case where
$\tau$ is a composition of $\tau_{k}$’s, the same argument works because rows
$a+1$ and $a+1+\frac{s}{2}$ in $M_{\sigma}$ do not change under twists. This
completes the proof of the claim that $\tau(\sigma)$ is a simplex.

Now we claim that the images under $\tau$ of two simplices
$\sigma_{1},\sigma_{2}$ in the canonical triangulation do not intersect in the
interior, that is
$\tau(\sigma_{1})^{\circ}\cap\tau(\sigma_{2})^{\circ}=\varnothing$. Suppose to
the contrary that there exists some
$\tau(p)\in\tau(\sigma_{1})^{\circ}\cap\tau(\sigma_{2})^{\circ}$. Let
$\sigma_{1}=\\{\mathbf{v}_{\varnothing},\mathbf{v}_{A_{0}},\dots,\mathbf{v}_{A_{m}}\\}$
and
$\sigma_{2}=\\{\mathbf{v}_{\varnothing},\mathbf{v}_{B_{0}},\dots,\mathbf{v}_{B_{m}}\\}$.
Then,

$\tau(p)=a_{-1}\mathbf{0}+a_{0}\tau(\mathbf{v}_{A_{0}})+\dots+a_{m}\tau(\mathbf{v}_{A_{m}})=b_{-1}\mathbf{0}+b_{0}\tau(\mathbf{v}_{B_{0}})+\dots+b_{m}\tau(\mathbf{v}_{B_{m}})$

for some $a_{i},b_{i}>0$ and $\sum_{i=-1}^{m}a_{i}=\sum_{i=-1}^{m}b_{i}=1$.
Now, define

$p_{A}:=a_{-1}\mathbf{0}+a_{0}\mathbf{v}_{A_{0}}+\dots+a_{m}\mathbf{v}_{A_{m}}$

and

$p_{B}:=b_{-1}\mathbf{0}+b_{0}\mathbf{v}_{B_{0}}+\dots+b_{m}\mathbf{v}_{B_{m}}\,.$

We will show that $p_{A}=p_{B}$ which implies
$p_{A}\in\sigma_{1}^{\circ}\cap\sigma_{2}^{\circ}=\varnothing$, a
contradiction. Again we will show this in the case $\tau=\tau_{k}$, and the
general case follows in the same way as in the proof of the first claim. Since
$\tau_{k}$ only affects $(a+2)$-th index of points in $\sigma_{1},\sigma_{2}$,
then $p_{A},p_{B}$ are equal to $\tau_{k}(p)$ in all positions except for
$a+2$. Therefore, it suffices to show that $(p_{A})_{a+2}=(p_{B})_{a+2}$.
Observe that

(3)
$\text{Row}_{M_{\tau_{k}(\sigma_{1})}}(a+2)\cdot[a_{0},\dots,a_{m}]=\tau_{k}(p)_{a+2}=\text{Row}_{M_{\tau_{k}(\sigma_{2})}}(a+2)\cdot[b_{0},\dots,b_{m}]\,.$

Note that $\mathbf{0}$ is not a column of $M_{\sigma}$ by construction, so
$a_{-1},b_{-1}$ are omitted in the equation above. Moreover, by equation (2)
we have that $\text{Row}_{M_{\sigma_{1}}}(a+2)$ (respectively
$\text{Row}_{M_{\sigma_{2}}}(a+2)$) is a linear combination of rows $a+1,a+2,$
and $a+1+s/2$ in $M_{\tau_{k}(\sigma_{1})}$ (respectively
$M_{\tau_{k}(\sigma_{2})}$). Hence, after taking the dot product of both sides
of equation (2) with $[a_{0},\dots,a_{m}]$ and with $[b_{0},\dots,b_{m}]$, we
obtain

$(p_{A})_{a+2}=\text{Row}_{M_{\sigma_{1}}}(a+2)\cdot[a_{0},\dots,a_{m}]=\text{Row}_{M_{\sigma_{2}}}(a+2)\cdot[b_{0},\dots,b_{m}]=(p_{B})_{a+2}\,.$

Indeed, this follows because
$\tau(p)_{i}=(p_{A})_{i}=\text{Row}_{M_{\tau_{k}(\sigma_{1})}}(i)\cdot[a_{0},\dots,a_{m}]=\text{Row}_{M_{\tau_{k}(\sigma_{2})}}(i)\cdot[b_{0},\dots,b_{m}]=(p_{B})_{i}$
for all $i\not=a+2$, and for $i=a+2$ we have equation (3).

This shows the desired claim, and we obtain a contradiction to
$\sigma_{1}^{\circ}\cap\sigma_{2}^{\circ}=\varnothing$. ∎

Next we proceed to show that twisting the canonical triangulation yields
regular triangulations. Given a point configuration
$\mathbf{A}=(\mathbf{p}_{1},...,\mathbf{p}_{m})$ in $\mathbb{R}^{d}$ and a
height function $\omega:\mathbf{A}\to\mathbb{R}$, let $\mathbf{A}^{\omega}$ be
the lifted point configuration given by
$\mathbf{A}^{\omega}=\begin{pmatrix}\mathbf{p}_{1}&\cdots&\mathbf{p}_{m}\\\
\omega(\mathbf{p}_{1})&\cdots&\omega(\mathbf{p}_{m})\\\ \end{pmatrix}$. Let
$\mathcal{T}(\mathbf{A},\omega)$ denote the regular triangulation of
$\mathbf{A}$ induced by the height function $\omega$.

For a simplex $\sigma$ in a triangulation $\mathcal{T}$ of $\mathbf{A}$, we
use $\mathbf{A}|_{\sigma}$ to denote the matrix whose columns correspond to
the vertices of $\sigma$, and similarly for $\mathbf{A}^{\omega}|_{\sigma}$.
The main tool we will use is the following theorem. Recall that a _wall_ in a
triangulation is a simplex of codimension one that is a face of two maximal
simplices.

######  Theorem 5.15 ([5], Theorem 2.3.20).

Let $\mathcal{T}$ be a triangulation of a point configuration
$\mathbf{A}\subset\mathbb{R}^{d}$, and let $\omega:\mathbf{A}\to\mathbb{R}$ be
a height function. Then one has $\mathcal{T}=\mathcal{T}(\mathbf{A},\omega)$
if and only if the local folding condition holds, i.e., if for every wall
$\sigma_{0}\in\mathcal{T}$, with incident full-dimensional simplices
$\sigma_{1}$ and $\sigma_{2}$, the point $\mathbf{v}\in V(\sigma_{1})\setminus
V(\sigma_{2})$ lies above the hyperplane containing
$\mathbf{A}^{\omega}|_{\sigma_{2}}$ and vice versa.

We use the notation $(M:\mathbf{v})$ to denote the matrix $M$ with the column
vector $\mathbf{v}$ appended as the last column. Further,
$\mathrm{sign}\det(M)$ denotes the sign of the determinant of $M$.

######  Definition 5.16 ([5], Definition 5.2.4).

Let $B=\\{\mathbf{p}_{r_{1}},...,\mathbf{p}_{r_{d+1}}\\}$ be a basis for
$\mathbf{A}$, i.e. an affinely independent set of full dimension. Then for any
$\mathbf{p}_{j}\in\mathbf{A}$, the linear form

$\displaystyle\Psi_{B,\mathbf{p}_{j}}(\omega)$
$\displaystyle:=\mathrm{sign}\det(\mathbf{p}_{r_{1}},...,\mathbf{p}_{r_{d+1}})\cdot\det\begin{pmatrix}\mathbf{p}_{r_{1}}&\cdots&\mathbf{p}_{r_{d+1}}&\mathbf{p}_{j}\\\
\omega(\mathbf{p}_{r_{1}})&\cdots&\omega(\mathbf{p}_{r_{d+1}})&\omega(\mathbf{p}_{j})\end{pmatrix}$
$\displaystyle:=\mathrm{sign}\det(\mathbf{A}|_{B})\cdot\det(\mathbf{A}^{\omega}|_{B}:(\mathbf{p}_{j},\omega(\mathbf{p}_{j})))$

is called the folding form of $\mathbf{p}_{j}$ with respect to $B$.

The folding form can be used to check the local folding condition of Theorem
5.15 since the point $\mathbf{p}_{j}~{}\in~{}\sigma_{1}\setminus~{}\sigma_{2}$
lies above the hyperplane containing $\mathbf{A}^{\omega}|_{\sigma_{2}}$ if
$\Psi_{\sigma_{2},\mathbf{p}_{j}}(\omega)>0$. Let $\mathbf{w}=w_{0}w_{1}\cdots
w_{k}$ be a fixed word. Let $Q_{\mathbf{w}}$ be the poset for which
$J(Q_{\mathbf{w}})=\widehat{P}(\mathbf{w})$. We will slightly alter the
labeling convention used in the previous section for the elements in
$Q_{\mathbf{w}}$. Relabel the vertices $0,1,2$ to be $1,2,3$ respectively,
relabel vertex $i$ as $i+2$ for $3\leq i\leq n-1$, and relabel $n$ with $4$.
See Figure 18 for an example. This new labeling may seem somewhat peculiar at
first, but it will make an inductive proof for regularity easier for the
following reason: when $k>0$, removing the highest label in $Q_{\mathbf{w}}$
with the new labeling yields the poset $Q_{\mathbf{w}\setminus\\{w_{k}\\}}$,
with $J(Q_{\mathbf{w}\setminus\\{w_{k}\\}})=\widehat{P}(w_{0}\cdots w_{k-1})$.
In other words, removing the highest label in $Q_{\mathbf{w}}$ corresponds
with removing the last box in $\widehat{P}(\mathbf{w})$. We then get the
sequence of posets $Q_{\mathbf{w}}\supset
Q_{\mathbf{w}\setminus\\{w_{k}\\}}\supset\cdots\supset Q_{w_{0}}$, where each
poset is obtained as a subposet from the previous one by removing the vertex
with the highest label. The corresponding posets of upper order ideals are
then $\widehat{P}(w_{0}\cdots w_{k-1}w_{k})\supseteq\widehat{P}(w_{0}\cdots
w_{k-1})\supseteq\cdots\supseteq\widehat{P}(w_{0})$. We label vertices of
$\mathcal{O}(Q_{\mathbf{w}})$ by the generators of their corresponding upper
order ideals. For example, a vertex $\mathbf{v}_{\langle a,b\rangle}$ is the
vertex corresponding to the upper order ideal generated by $a$ and $b$ in
$Q_{\mathbf{w}}$. We label the vertex corresponding to the empty upper order
ideal with $\mathbf{v}_{\varnothing}$.

$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$$14$$15$$17$$16$$18$$19$$1$$2$$3$$5$$6$$7$$8$$9$$10$$11$$12$$13$$14$$15$$16$$17$$19$$18$$20$$4$$1$$2$$3$$5$$6$$7$$8$$9$$10$$11$$12$$13$$14$$15$$16$$17$$19$$18$$4$
Figure 18. The old labeling of $Q_{\mathbf{w}}$ (left). The altered labeling
for $Q_{\mathbf{w}}$ (center). Removing the largest label $20$ in
$Q_{\mathbf{w}}$ with the altered labeling forms
$Q_{\mathbf{w}\setminus\\{w_{k}\\}}$ (right).

As before, we think of $J(Q_{\mathbf{w}})$ as being made up of $\widehat{0}$,
$\widehat{1}$ and ladders $\mathcal{L}^{1},...,\mathcal{L}^{t}$. Label
$\widehat{0}$ and $\widehat{1}$ with $x_{0}$ and $x_{2k+5}$, respectively. In
the case that $\mathbf{w}=\varepsilon$, we resolve the ambiguity as before in
the discussion preceding Definition 5.3. That is, we treat $\varepsilon$ as an
$R$ word. Refer to Figure 20 for an illustration of this labeling. In the case
that $\mathbf{w}\neq\varepsilon$, we label the remaining elements of
$\widehat{P}(\mathbf{w})$ with labels $x_{i}$, where $1\leq i\leq 2k+4$ in
sequential order as follows. First label the element covered by $x_{0}$ with
$x_{1}$, then label the other element of that rung in $\mathcal{L}^{1}$ with
$x_{2}$.

Continue labeling the pairs on the rungs of $\mathcal{L}^{1}$ until all
elements of $\mathcal{L}^{1}$ have labels $x_{1}\ldots,x_{s}$ for some even
integer $s$ such that the even indexed labels are on one side of
$\mathcal{L}^{1}$ and the odd indexed labels are on the other. Note that this
labeling of $\mathcal{L}^{1}$ is consistent with that presented in Figure 11.
Note that since $\mathcal{L}^{1}$ and $\mathcal{L}^{2}$ intersect in a square,
the first two rungs of $\mathcal{L}^{2}$ have already been assigned labels.
Then, we proceed by labeling the unlabeled rungs of $\mathcal{L}^{2}$ in a
similar fashion to the labeling of $\mathcal{L}_{1}$. That is, we label the
first unlabeled rung of $\mathcal{L}^{2}$ with $x_{s+1}$ covering $x_{s+2}$
and so on until all remaining elements of $\mathcal{L}^{2}$ have been labeled.
Continue labeling in this manner for the remaining ladders until every element
of $\widehat{P}(\mathbf{w})$ is assigned a label. The left poset of Figure 19
demonstrates the labeling of $\widehat{P}(\mathbf{w})$ when
$\mathbf{w}=\varepsilon RRLLR$.

We introduce the following terminology and notation for the following proof of
Theorem 5.8. The _canonical order_ on $V(\mathcal{O}(Q_{\mathbf{w}}))$ is
defined by

$x_{0},x_{2},x_{1},x_{4},x_{3},x_{6},x_{5},...,x_{s},x_{s-1},...,x_{2k+4},x_{2k+3},x_{2k+5}\,.$

We call this order the canonical order since it is used to construct a height
function yielding the canonical triangulation. Recall that applying a twist
$\tau\in\mathfrak{T}(\mathbf{w})$ to $\widehat{P}(\mathbf{w})$ permutes the
vertices $V(\mathcal{O}(Q_{\mathbf{w}}))$. Therefore, applying $\tau$ to the
canonical order yields a new ordering, which we call the twisted order with
respect to $\tau$. We denote by $\tau(x_{i})$ the label which replaces $x_{i}$
as a result of the twist.

######  Definition 5.17.

If $x_{i}$ is the $k$-th element in the canonical order, let
$\rho(x_{i})=k-1$. The canonical height function is the function
$\omega:\mathbf{A}\to\mathbb{R}$ given by $\omega(x_{i})=2^{\rho(x_{i})}$.
Furthermore, we define the twisted height function
$\omega_{\tau}:\mathbf{A}\to\mathbb{R}$ to be given by
$\omega_{\tau}(x_{i})=\omega(\tau(x_{i}))$. Note that taking
$\tau=\mathrm{id}$ gives the canonical height function.

For example, consider the vertex $x_{9}$ of $V(\mathcal{O}(Q_{\mathbf{w}}))$
in Figure 19. It appears as the $11$-th element in the canonical order. Thus
$\omega(x_{9})=2^{\rho(x_{9})}=2^{10}$. Applying the twist $\tau_{2}$ on
$V(\mathcal{O}(Q_{\mathbf{w}}))$ gives $\tau_{2}(x_{10})=x_{9}$. Therefore
$\omega_{\tau_{2}}(x_{10})=\omega(\tau_{2}(x_{10}))=\omega(x_{9})=2^{10}$.

$x_{0}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$$x_{7}$$x_{8}$$x_{9}$$x_{10}$$x_{11}$$x_{12}$$x_{14}$$x_{13}$$x_{15}$$\varepsilon$$R$$R$$L$$L$$R$Canonical
order:$x_{0},x_{2},x_{1},x_{4},x_{3},x_{6},x_{5},x_{8},x_{7},$$x_{10},x_{9},x_{12},x_{11},x_{14},x_{13},x_{15}$$x_{0}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{7}$$x_{8}$$x_{5}$$x_{6}$$x_{10}$$x_{9}$$x_{12}$$x_{11}$$x_{14}$$x_{13}$$x_{15}$$\varepsilon$$R$$R$$L$$L$$R$$\tau_{2}$Twisted
order:$x_{0},x_{2},x_{1},x_{4},x_{3},x_{8},x_{7},x_{6},x_{5},$$x_{9},x_{10},x_{11},x_{12},x_{14},x_{13},x_{15}$
Figure 19. An illustration of the canonical order and a twisted order.

We are now ready to prove Theorem 5.8.

###### Proof of Theorem 5.8.

For a fixed word $\mathbf{w}$ of length $k$, let $\mathcal{T}_{\mathbf{w}}$
denote the canonical triangulation of $\mathcal{O}(Q_{\mathbf{w}})$. Let $n$
be the number of elements in $Q_{\mathbf{w}}$, that is, $n=k+4$. Let
$\mathbf{A}_{n}=\begin{pmatrix}\mathbf{v}_{x_{0}}&\mathbf{v}_{x_{1}}&\cdots&\mathbf{v}_{x_{2n-3}}\\\
1&1&\cdots&1\end{pmatrix}$ be the homogenized point configuration associated
with the vertices of the order polytope $\mathcal{O}(Q_{\mathbf{w}})$, where
$\mathbf{v}_{x_{i}}$ is the vertex associated with
$x_{i}\in\widehat{P}(\mathbf{w})$. We will show that
$\tau(\mathcal{T}_{\mathbf{w}})=\mathcal{T}(\mathbf{A}_{n},\omega_{\tau})$ for
all $\tau\in\mathfrak{T}(\mathbf{w})$ by inducting on $n$, or equivalently
$k$. We first check the base case when $n=4$ and $k=0$, i.e., when
$\mathbf{w}=\varepsilon$.

$x_{0}=\varnothing$$x_{1}=\langle 1\rangle$$x_{2}=\langle
2\rangle$$x_{3}=\langle 3\rangle$$x_{5}=\langle 4\rangle$$x_{4}=\langle
2,3\rangle$$\varepsilon$$\widehat{P}=\widehat{P}(\varepsilon):$$1$$2$$3$$4$$Q_{\varepsilon}=\mathrm{Irr}_{\wedge}(\widehat{P}(\varepsilon)):$
Figure 20. Base case in proof of Theorem 5.8 with $\mathbf{w}=\varepsilon$.

Although we previously chose the convention to treat $\varepsilon$ as an $R$,
here it is necessary to also consider the case when $\varepsilon$ is treated
as an $L$ as we will induct on the length of the word and a priori, we do not
know whether $w_{1}=L$ or $w_{1}=R$. Both cases, however, are similar, and we
therefore check the case with $\varepsilon$ treated as an $R$ word (see Figure
20), leaving the other base case for the reader.

Treating $\varepsilon$ as an $R$, we must check that
$\tau(\mathcal{T}_{\varepsilon})=\mathcal{T}(\mathbf{A}_{4},\omega_{\tau})$
for $\tau\in\mathfrak{T}(\varepsilon)=\\{\mathrm{id},\tau_{1}\\}$ where
$\tau_{1}$ exchanges the pairs $(\langle 1\rangle,\langle 2\rangle)$ and
$(\langle 3\rangle,\langle 2,3\rangle)$ in $\widehat{P}$. In this case, the
canonical order is $x_{0}$, $x_{2}$, $x_{1}$, $x_{4}$, $x_{3}$, $x_{5}$. We
begin with $\tau=\mathrm{id}$ and check that the canonical triangulation is
obtained as a regular triangulation with the canonical order and height
function $\omega_{\mathrm{id}}:\mathbf{A}_{4}\to\mathbb{R}$ given by
$\omega_{\mathrm{id}}(x_{i})=2^{\rho(x_{i})}$. We have

$\mathbf{A}_{4}^{\omega_{\mathrm{id}}}=\blockarray{ccccccc}&\mathbf{v}_{\varnothing}\mathbf{v}_{\langle
1\rangle}\mathbf{v}_{\langle 2\rangle}\mathbf{v}_{\langle
3\rangle}\mathbf{v}_{\langle 2,3\rangle}\mathbf{v}_{\langle 4\rangle}\\\
\block{c(cccccc)}1011111\bigstrut[t]\\\ 2001011\\\ 3000111\\\ 4000001\\\
5111111\\\ 614216832\\\ \;.$

From $\widehat{P}$, we know there are two simplices in the canonical
triangulation $\mathcal{T}_{\varepsilon}$ of $\mathcal{O}(Q_{\varepsilon})$,
namely $\sigma_{1}=(\mathbf{v}_{\varnothing},\mathbf{v}_{\langle
1\rangle},\mathbf{v}_{\langle 2\rangle},\mathbf{v}_{\langle
2,3\rangle},\mathbf{v}_{\langle 4\rangle})$ and
$\sigma_{2}=(\mathbf{v}_{\varnothing},\mathbf{v}_{\langle
1\rangle},\mathbf{v}_{\langle 3\rangle},\mathbf{v}_{\langle
2,3\rangle},\mathbf{v}_{\langle 4\rangle})$. The only wall is
$\sigma_{0}=(\mathbf{v}_{\varnothing}$, $\mathbf{v}_{\langle
1\rangle}$,$\mathbf{v}_{\langle 2,3\rangle}$,$\mathbf{v}_{\langle 4\rangle})$,
and so we compute

$\displaystyle\Psi_{\sigma_{1},\mathbf{v}_{\langle
3\rangle}}(\omega_{\mathrm{id}})$
$\displaystyle=\mathrm{sign}\det(\mathbf{A}_{4}|_{\sigma_{1}})\cdot\det(\mathbf{A}_{4}^{\omega_{\mathrm{id}}}|_{\sigma_{1}}:(\mathbf{v}_{\langle
3\rangle},1,16))$
$\displaystyle=\mathrm{sign}\det\begin{pmatrix}\mathbf{v}_{\varnothing}&\mathbf{v}_{\langle
1\rangle}&\mathbf{v}_{\langle 2\rangle}&\mathbf{v}_{\langle
2,3\rangle}&\mathbf{v}_{\langle 4\rangle}\\\ 1&1&1&1&1\\\
\end{pmatrix}\cdot\det\begin{pmatrix}\mathbf{v}_{\varnothing}&\mathbf{v}_{\langle
1\rangle}&\mathbf{v}_{\langle 2\rangle}&\mathbf{v}_{\langle
2,3\rangle}&\mathbf{v}_{\langle 4\rangle}&\mathbf{v}_{\langle 3\rangle}\\\
1&1&1&1&1&1\\\ 1&4&2&8&32&16\\\ \end{pmatrix}$ $\displaystyle=6>0$

and similarly

$\displaystyle\Psi_{\sigma_{2},\mathbf{v}_{\langle
2\rangle}}(\omega_{\mathrm{id}})$
$\displaystyle=\mathrm{sign}\det(\mathbf{A}_{4}|_{\sigma_{2}})\cdot\det(\mathbf{A}_{4}^{\omega_{\mathrm{id}}}|_{\sigma_{2}}:(\mathbf{v}_{\langle
2\rangle},1,2))$
$\displaystyle=\mathrm{sign}\det\begin{pmatrix}\mathbf{v}_{\varnothing}&\mathbf{v}_{\langle
1\rangle}&\mathbf{v}_{\langle 3\rangle}&\mathbf{v}_{\langle
2,3\rangle}&\mathbf{v}_{\langle 4\rangle}\\\ 1&1&1&1&1\\\
\end{pmatrix}\cdot\det\begin{pmatrix}\mathbf{v}_{\varnothing}&\mathbf{v}_{\langle
1\rangle}&\mathbf{v}_{\langle 3\rangle}&\mathbf{v}_{\langle
2,3\rangle}&\mathbf{v}_{\langle 4\rangle}&\mathbf{v}_{\langle 2\rangle}\\\
1&1&1&1&1&1\\\ 1&4&16&8&32&2\\\ \end{pmatrix}$ $\displaystyle=(-1)(-6)>0.$

Thus, by the local folding condition in Theorem 5.15, $\mathbf{v}_{\langle
2\rangle}=\sigma_{1}\setminus\sigma_{2}$ lies above the hyperplane containing
$\mathbf{A}_{4}|_{\sigma_{2}}$, and $\mathbf{v}_{\langle
3\rangle}=\sigma_{2}\setminus\sigma_{1}$ lies above the hyperplane containing
$\mathbf{A}_{4}|_{\sigma_{1}}$. By Theorem 5.15 we then have
$\mathcal{T}_{\varepsilon}=\mathcal{T}(\mathbf{A}_{4},\omega_{\mathrm{id}})$.
Checking that
$\tau_{1}(\mathcal{T}_{\varepsilon})=\mathcal{T}(\mathbf{A}_{4},\omega_{\tau_{1}})$
is done similarly. Appending the row of heights according to the twisted order
determined by $\tau_{1}$, we have

$\mathbf{A}_{4}^{\omega_{\tau_{1}}}=\blockarray{(ccccccc)}\mathbf{v}_{\varnothing}&\mathbf{v}_{\langle
1\rangle}\mathbf{v}_{\langle 2\rangle}\mathbf{v}_{\langle
3\rangle}\mathbf{v}_{\langle 2,3\rangle}\mathbf{v}_{\langle 4\rangle}\\\
111111\\\ 12481632\\\ \,.$

The two simplices in the triangulation $\tau_{1}(\mathcal{T}_{\varepsilon})$
of $\mathcal{O}(Q_{\varepsilon})$ are
$\tau_{1}(\sigma_{1})=(\mathbf{v}_{\varnothing},\mathbf{v}_{\langle
1\rangle},\mathbf{v}_{\langle 2\rangle},\mathbf{v}_{\langle
3\rangle},\mathbf{v}_{\langle 4\rangle})$ and
$\tau_{1}(\sigma_{2})=(\mathbf{v}_{\varnothing},\mathbf{v}_{\langle
2\rangle},\mathbf{v}_{\langle 3\rangle},\mathbf{v}_{\langle
2,3\rangle},\mathbf{v}_{\langle 4\rangle})$. The wall between them is
$\tau_{1}(\sigma_{0})=(\mathbf{v}_{\varnothing},\mathbf{v}_{\langle
2\rangle},\mathbf{v}_{\langle 3\rangle},\mathbf{v}_{\langle 4\rangle})$. We
compute $\Psi_{\tau_{1}(\sigma_{1}),\mathbf{v}_{\langle
2,3\rangle}}(\omega_{\tau_{1}})=6>0$ and
$\Psi_{\tau_{1}(\sigma_{2}),\mathbf{v}_{\langle
1\rangle}}(\omega_{\tau_{1}})=(-1)(-6)>0$. Similarly, in the case that
$\varepsilon$ is treated as an $L$, the reader may check that
$\tau(\mathcal{T}_{\varepsilon})=\mathcal{T}(\mathbf{A}_{4},\omega_{\tau})$
for $\tau\in\mathfrak{T}(\varepsilon)=\\{\mathrm{id},\tau_{1}\\}$. Hence the
base case holds.

We now consider the case $\mathbf{w}=w_{0}w_{1}\cdots w_{k}w_{k+1}$. We assume
the inductive hypothesis, namely that the local folding condition holds for
every wall in $\tau(\mathcal{T}_{w_{0}w_{1}\cdots w_{\ell}})$ of
$\mathcal{O}(Q_{w_{0}w_{1}\cdots w_{\ell}})$ for all $0\leq\ell\leq k$ and for
all $\tau\in\mathfrak{T}(w_{0}w_{1}\cdots w_{\ell})$. That is, for any wall
$\tau(\sigma_{0})=\tau(\sigma_{1})\cap\tau(\sigma_{2})$ in
$\mathcal{T}_{w_{0}w_{1}\cdots w_{\ell}}$, we assume that
$\Psi_{\tau(\sigma_{1}),\mathbf{v}_{i}}(\omega_{\tau})>0$ for
$\mathbf{v}_{i}=\tau(\sigma_{2}\setminus\sigma_{1})$ and
$\Psi_{\tau(\sigma_{2}),\mathbf{v}_{j}}(\omega_{\tau})>0$ for
$\mathbf{v}_{j}=\tau(\sigma_{1}\setminus\sigma_{2})$. The general strategy for
the remainder of the proof is as follows. Simultaneously performing the same
row and column operations on
$(\mathbf{A}_{n+1}^{\omega_{\tau}}|_{\tau(\sigma_{1})}:(\mathbf{v}_{i},1,\omega_{\tau}(\mathbf{v}_{i})))$
and $\mathbf{A}_{n+1}|_{\tau(\sigma_{1})}$ does not change the sign of the
product of their determinants (and thus the sign of
$\Psi_{\tau(\sigma_{1}),\mathbf{v}_{i}}(\omega_{\tau})$), so long as each
operation is possible on both matrices. Furthermore, we add rows to or
subtract rows from the last row of
$(\mathbf{A}_{n+1}^{\omega_{\tau}}|_{\tau(\sigma_{1})}:(\mathbf{v}_{i},1,\omega_{\tau}(\mathbf{v}_{i})))$
without changing the sign of its determinant so that
$(\mathbf{A}_{n+1}^{\omega_{\tau}}|_{\tau(\sigma_{1})}:(\mathbf{v}_{i},1,\omega_{\tau}(\mathbf{v}_{i})))$
contains
$(\mathbf{A}_{\ell+4}^{\omega_{\tau^{\prime}}}|_{\tau^{\prime}(\sigma_{1}^{\prime})}:(\mathbf{v}_{i}^{\prime},1,\omega_{\tau^{\prime}}(\mathbf{v}_{i}^{\prime})))$
as a block submatrix, which is a matrix of a previous case corresponding to a
word $w_{0}w_{1}\cdots w_{\ell}$, with $\ell<k+1$. Here,
$\tau^{\prime}\in\mathfrak{T}(w_{0}\cdots w_{\ell})$ is the restriction of
$\tau$ to the ladders of $\widehat{P}(w_{0}\cdots w_{\ell})$,
$\tau^{\prime}(\sigma^{\prime}_{1})$ is the simplex in
$\mathcal{O}(Q_{w_{0}\cdots w_{\ell}})$ corresponding to the maximal chain in
$\widehat{P}(w_{0}\cdots w_{\ell})$ which is a subset of the maximal chain in
$\widehat{P}(\mathbf{w})$ corresponding with $\tau(\sigma_{1})$, and
$\mathbf{v}^{\prime}_{j}$ is equal to $\mathbf{v}_{j}$ restricted to entries
$1,2,\ldots,\ell+4$. By the inductive hypothesis, we then have
$\Psi_{\tau^{\prime}(\sigma_{1}^{\prime}),\mathbf{v}_{i}^{\prime}}(\omega_{\tau^{\prime}})=\mathrm{sign}\det(\mathbf{A}_{\ell+4}|_{\tau^{\prime}(\sigma_{1}^{\prime})})\cdot\det(\mathbf{A}_{\ell+4}^{\omega_{\tau^{\prime}}}|_{\tau^{\prime}(\sigma_{1}^{\prime})}:(\mathbf{v}_{i}^{\prime},1,\omega_{\tau^{\prime}}(\mathbf{v}^{\prime}_{i})))>0$,
from which we argue that
$\Psi_{\tau(\sigma_{1}),\mathbf{v}_{i}}(\omega_{\tau})>0$. Moreover, via a
similar argument, we can argue that
$\Psi_{\tau(\sigma_{2}),\mathbf{v}_{j}}(\omega_{\tau})>0$.

To apply this strategy, we consider two possibilities, extensions and turns,
each of which admit multiple subcases. To define extensions and turns, suppose
$\widehat{P}(w_{0}\cdots w_{k})$ consists of $t$ ladders
$\mathcal{L}^{1},...,\mathcal{L}^{t}$ with $\widehat{0}$ and $\widehat{1}$.
The case when $w_{k+1}=w_{k}$ is referred to as an extension because it
corresponds with extending the ladder ending with $w_{k}$, namely
$\mathcal{L}^{t}$. Furthermore, we refer to the case when $w_{k+1}\neq w_{k}$
as a turn because it corresponds to a turn in $\widehat{P}(\mathbf{w})$. Note
that a turn effectively adds an additional ladder $\mathcal{L}^{t+1}$ to
$\widehat{P}(w_{0}\cdots w_{k})$ to form $\widehat{P}(\mathbf{w})$. In the
case of an extension, we need to consider both when there is and is not a
twist applied to $\mathcal{L}^{t}$. Furthermore, in each of these cases we
must consider the subcases when the simplices differ by elements in the square
$\mathrm{Sq}(\mathbf{w}_{k+1})$, and when they differ by elements in a square
$\mathrm{Sq}(\mathbf{w}_{i})$ with $i\leq k$.

In the case of a turn, it is somewhat more complicated than for an extension,
as we have two possible twists which result in four cases to check. We can
either twist $\mathcal{L}^{t}$ or the new ladder $\mathcal{L}^{t+1}$ produced
by the turn, or we may twist both or neither. See Figure 22. In each of these
cases, there are more subcases to check than for an extension, as we must
consider when the simplices differ by elements in one of the squares
$\mathrm{Sq}(\mathbf{w}_{k+1})$, $\mathrm{Sq}(\mathbf{w}_{k})$,
$\mathrm{Sq}(\mathbf{w}_{k-1})$, and when they differ in a square
$\mathrm{Sq}(\mathbf{w}_{i})$ with $i\leq k-1$. Extensions and turns combined
result in a total of 36 cases to check, which are listed in Appendix 7.

Extension:$a-1$$a$$a+1$$n-1$$n$$n+1$$4$

$\ddots$

$\ddots$

$\ddots$

$Q_{\mathbf{w}}$$\langle a-1\rangle$$\langle a\rangle$$\langle
a-1,b\rangle$$\langle n-1\rangle$$\langle n\rangle$$\langle
n+1\rangle$$\langle a,n+1\rangle$$\langle a,b\rangle$$\langle
a,n-1\rangle$$\langle a,n\rangle$$\langle 4\rangle$

$\ddots$

$\ddots$

$\ddots$

$\ddots$

$\widehat{P}(\mathbf{w})$Turn:$a-1$$a$$a+1$$n-2$$n-1$$n$$4$$n+1$

$\ddots$

$\ddots$

$\ddots$

$Q_{\mathbf{w}}$$\langle a-1\rangle$$\langle a\rangle$$\langle
a-1,b\rangle$$\langle n-2\rangle$$\langle n-1\rangle$$\langle
n\rangle$$\langle a,n\rangle$$\langle a,b\rangle$$\langle
a,n-2\rangle$$\langle a,n-1\rangle$$\langle n,n+1\rangle$$\langle
4\rangle$$\langle n+1\rangle$

$\ddots$

$\ddots$

$\ddots$

$\ddots$

$\widehat{P}(\mathbf{w})$ Figure 21. The two main cases to check, i.e. an
extension and turn. $\langle n-2\rangle$$\langle n-1\rangle$$\langle
n\rangle$$\langle a,n\rangle$$\langle a,n-2\rangle$$\langle
a,n-1\rangle$$\langle n,n+1\rangle$$\langle 4\rangle$$\langle n+1\rangle$

$\ddots$

$\ddots$

$\ddots$

$\ddots$

No twist$\langle a,n-2\rangle$$\langle a,n-1\rangle$$\langle
a,n\rangle$$\langle n\rangle$$\langle n-2\rangle$$\langle n-1\rangle$$\langle
n,n+1\rangle$$\langle 4\rangle$$\langle n+1\rangle$

$\ddots$

$\ddots$

$\ddots$

$\ddots$

Twist on $\mathcal{L}^{t}$$\langle n-2\rangle$$\langle n\rangle$$\langle
n-1\rangle$$\langle a,n-1\rangle$$\langle a,n-2\rangle$$\langle
a,n\rangle$$\langle n+1\rangle$$\langle 4\rangle$$\langle n,n+1\rangle$

$\ddots$

$\ddots$

$\ddots$

$\ddots$

Twist on $\mathcal{L}^{t+1}$$\langle a,n-2\rangle$$\langle a,n\rangle$$\langle
a,n-1\rangle$$\langle n-1\rangle$$\langle n-2\rangle$$\langle
n\rangle$$\langle n+1\rangle$$\langle 4\rangle$$\langle n,n+1\rangle$

$\ddots$

$\ddots$

$\ddots$

$\ddots$

Twist on $\mathcal{L}^{t}$ and $\mathcal{L}^{t+1}$ Figure 22. The four
possible twists at a turn.

We will prove two of the thirty-six cases here, to demonstrate the techniques
used in the remaining cases, which are checked similarly. The first case we
consider here is an extension case with a twist $\tau$, where $\tau$ twists
the last ladder $\mathcal{L}^{t}$ (and possibly other ladders
$\mathcal{L}^{i}$ with $i<t$). The particular subcase chosen is the one where
the simplices $\tau(\sigma_{1})$ and $\tau(\sigma_{2})$ differ in the final
square $\mathrm{Sq}(\mathbf{w}_{k+1})$. In this case we assume without loss of
generality that $\mathbf{v}_{\langle n\rangle}\in\tau(\sigma_{1})$ and
$\mathbf{v}_{\langle a,n+1\rangle}\in\tau(\sigma_{2})$, see Figure 23. This is
the extension case 2.c in Appendix 7.

$\langle a\rangle$$\langle a-1\rangle$$\langle a,b\rangle$$\langle
a,n-1\rangle$$\langle a,n\rangle$$\langle a,n+1\rangle$$\langle
n+1\rangle$$\langle b\rangle$$\langle n-1\rangle$$\langle n\rangle$$\langle
4\rangle$

$\ddots$

$\ddots$

$\ddots$

$\ddots$

Figure 23. A subcase of an extension, with $\mathcal{L}^{t}$ twisted by
$\tau$. Here $\tau(\sigma_{1})$ is in red, and $\tau(\sigma_{2})$ is in blue.

We need to show that $\Psi_{\tau(\sigma_{1}),\mathbf{v}_{\langle
a,n+1\rangle}}(\omega_{\tau})>0$ and
$\Psi_{\tau(\sigma_{2}),\mathbf{v}_{\langle n\rangle}}(\omega_{\tau})>0$,
where $\tau\in\mathfrak{T}(w_{0}w_{1}\cdots w_{k+1})$ twists
$\mathcal{L}^{t}$. We have
$(\mathbf{A}_{n+1}^{\omega_{\tau}}|_{\tau(\sigma_{1})}:(\mathbf{v}_{\langle
a,n+1\rangle},1,2^{2n-4}))$ is equal to

$\blockarray{ccccccccc}&\mathbf{v}_{\varnothing}\cdots\mathbf{v}_{\langle
a,n-1\rangle}\mathbf{v}_{\langle n\rangle}\mathbf{v}_{\langle
a,n\rangle}\mathbf{v}_{\langle n+1\rangle}\mathbf{v}_{\langle
4\rangle}\mathbf{v}_{\langle a,n+1\rangle}\\\ \block{c(cccccccc)}10\cdots
111111\bigstrut[t]\\\ 20\cdots 1*1*11\\\ 30\cdots 1*1*11\\\ 40\cdots 000010\\\
\vdots\vdots\vdots\vdots\vdots\vdots\vdots\vdots\\\ a0\cdots 101011\\\
\vdots\vdots\vdots\vdots\vdots\vdots\vdots\vdots\\\ n0\cdots 011111\\\
n+10\cdots 000111\\\ n+21\cdots 111111\\\ n+31\cdots
2^{2n-8}2^{2n-7}2^{2n-6}2^{2n-5}2^{2n-3}2^{2n-4}\\\ \;,$

where the $*$ entries are either zeros or ones. In the case that