# Rectangulotopes

Jean Cardinal  Université libre de Bruxelles (ULB<EMAIL_ADDRESS>https://jean.cardinal.web.ulb.be and  Vincent Pilaud  Universitat de Barcelona
(UB<EMAIL_ADDRESS>https://www.ub.edu/comb/vincentpilaud/

###### Abstract.

Rectangulations are decompositions of a square into finitely many axis-aligned
rectangles. We describe realizations of $(n-1)$-dimensional polytopes
associated with two combinatorial families of rectangulations composed of $n$
rectangles. They are defined as quotientopes of natural lattice congruences on
the weak Bruhat order on permutations in $\mathfrak{S}_{n}$, and their skeleta
are flip graphs on rectangulations. We give simple vertex and facet
descriptions of these polytopes, in particular elementary formulas for
computing the coordinates of the vertex corresponding to each rectangulation,
in the spirit of J.-L. Loday’s realization of the associahedron.

VP was partially supported by the Spanish grant PID2022-137283NB-C21 of
MCIN/AEI/10.13039/501100011033 / FEDER, UE, by Departament de Recerca i
Universitats de la Generalitat de Catalunya (2021 SGR 00697), by the French
grant CHARMS (ANR-19-CE40-0017), and by the French–Austrian projects PAGCAP
(ANR-21-CE48-0020 & FWF I 5788).

###### Contents

  1. 1 Introduction
    1. 1.1 Polytopes of permutations, triangulations, and rectangulations
    2. 1.2 Weak and strong rectangulations
    3. 1.3 Weak and strong rectangulotopes
    4. 1.4 Source and target trees of a rectangulation
    5. 1.5 Realizations of weak rectangulotopes
    6. 1.6 Realizations of strong rectangulotopes
    7. 1.7 Plan of the paper
    8. 1.8 Acknowledgments
  2. 2 Quotientopes
    1. 2.1 Weak order and noncrossing arc diagrams
    2. 2.2 Quotients and arc ideals
    3. 2.3 Quotient fans and shards
    4. 2.4 Quotientopes and shard polytopes
  3. 3 Weak rectangulotopes
    1. 3.1 The weak poset
    2. 3.2 The weak rectangulation congruence
    3. 3.3 Up and down arcs
    4. 3.4 Shard polytopes of up and down arcs
    5. 3.5 Submodular functions of weak rectangulotopes
    6. 3.6 Loday coordinates of weak rectangulotopes
  4. 4 Strong rectangulotopes
    1. 4.1 The strong poset
    2. 4.2 The strong rectangulation congruence
    3. 4.3 Yin and yang arcs
    4. 4.4 Shard polytopes of yin and yang arcs
    5. 4.5 Submodular functions of strong rectangulotopes
    6. 4.6 Loday coordinates of strong rectangulotopes

##  1\. Introduction

###  1.1. Polytopes of permutations, triangulations, and rectangulations

The encoding of combinatorial objects in the form of a polyhedral structure is
a recurrent theme in geometric and algebraic combinatorics. An elementary yet
striking example of this idea is the permutahedron $\mathds{P}(n)$. It is the
$(n-1)$-dimensional polytope defined either as the convex hull of the points
$\sum_{i\in[n]}\sigma^{-1}_{i}\cdot{\boldsymbol{e}}_{i}$ for all permutations
$\sigma\in\mathfrak{S}_{n}$, or as the intersection of the hyperplane of
$\mathbb{R}^{n}$ given by $\sum_{i\in[n]}x_{i}=\smash{\binom{n+1}{2}}$ with
the halfspaces given by $\sum_{i\in I}x_{i}\geq\smash{\binom{|I|+1}{2}}$ for
all nonempty proper subsets $\varnothing\neq I\subsetneq[n]$. Its skeleton is
the Cayley graph of the symmetric group for the generators consisting of
adjacent transpositions. See Figure 1 (left) for an illustration when $n=4$.
The many generalizations and extensions of the permutahedra gave rise to a
flourishing theory of deformed permutahedra [Pos09, PRW08, ACEP20, AA23] (also
called generalized permutahedra, or polymatroids).

Among those, the associahedron is a classical and ubiquitous polytope, first
defined by D. Tamari [Tam51] and by J. Stasheff [Sta63] in a topological
context. It has since then been identified as a fundamental object in many
other areas of mathematics, including operads, cluster algebras, combinatorial
Hopf algebras, and physics (see for instance the recent survey from V. Pilaud,
F. Santos and G. Ziegler [PSZ23] and the references therein). It was first
thought of as a purely combinatorial object, before various families of
geometric realizations were shown to exist [Lee89, CFZ02, Lod04, CSZ15, HL07].
The face lattice of the $(n-1)$-dimensional associahedron is the reverse
inclusion poset of non-intersecting diagonals of a convex $(n+3)$-gon. In
particular, its skeleton is the flip graph on triangulations of the
$(n+3)$-gon, or equivalently – via a standard Catalan bijection – the rotation
graph on binary trees with $n$ internal nodes, the structure of which has been
the subject of many investigations, with applications in computer science
[STT88, Pou14]. In 2004, J.-L. Loday published the following elegant
description of the associahedron [Lod04], giving a recipe for computing the
coordinates of a vertex corresponding to a given binary tree. We note that the
inequality description of the same polytope was actually provided in 1993 by
S. Shnider and S. Sternberg [SS93], but Loday’s vertex description largely
popularized this realization. See Figure 1 (right) for an illustration when
$n=4$.

######  Theorem 1.

The associahedron $\mathds{A}(n)$ is realized by:

  1. (i)

the convex hull of the points

$\sum_{i\in[n]}\ell^{T}_{i}\cdot r^{T}_{i}\cdot{\boldsymbol{e}}_{i}$

for all binary trees $T$ with $n$ internal nodes, where $\ell^{T}_{i}$ and
$r^{T}_{i}$ denote the number of leaves in the left and right subtrees of $i$
in $T$, see [Lod04],

  2. (ii)

the intersection of the hyperplane defined by
$\sum_{i\in[n]}x_{i}=\binom{n+1}{2}$ with the halfspaces defined by

$\sum_{i\in I}x_{i}\leq\\#\left\\{J\text{ interval of }[n]\;\middle|\;I\cap
J\neq\varnothing\right\\}$

for all intervals $\varnothing\neq I\subsetneq[n]$, see [SS93].

A natural object associated with the associahedron is the Tamari lattice,
whose cover graph is isomorphic to the skeleton of the associahedron [Tam62,
MHPS12]. The Tamari lattice is known to be the quotient of the weak Bruhat
order by a lattice congruence called the sylvester congruence [LR98, HNT05].
Answering a question of N. Reading [Rea05], V. Pilaud and F. Santos [PS19]
proved that with _every_ lattice congruence of the weak Bruhat order, one can
associate a polytope whose skeleton is the cover graph of the lattice
quotient, and more precisely whose normal fan is the quotient fan defined by
gluing the cones of the braid fan (the type $A$ Coxeter arrangement) that
belong to the same congruence class. Those polytopes are deformed permutahedra
that they called quotientopes. The associahedron is therefore the quotientope
of the sylvester congruence of the weak Bruhat order whose classes are in
bijection with triangulations.

The goal of this paper is to describe the geometry of the quotientopes for two
particular congruences of the weak Bruhat order whose classes are in bijection
with equivalence classes of rectangulations, defined as decompositions of a
square into rectangles.

Figure 1. The permutahedron $\mathds{P}(4)$ (left) and the associahedron
$\mathds{A}(4)$ (right). [PS19, Fig. 1] & [PPR23, Fig. 5]

###  1.2. Weak and strong rectangulations

The combinatorics of rectangulations has been studied for nearly two decades
[ABP06, FFNO11, LR12, Rea12, ABBM+13, He14, CSS18, MM23, FNS24, AB24, ACFF24].
In fact, several combinatorial ideas can even be traced back to the problem of
“squaring the square” studied since the 1930s [Abe30, Abe32, Spr39, BSST40].
Also, some results were initially motivated by applications to the design of
floorplans for very large scale integrated circuits, and published in
electrical engineering journals, see for instance Z. C. Shen and C. C. N. Chu
[SC03], and R. Fujimaki, Y. Inoue, and T. Takahashi [FT07, TF08, ITF09,
FIT09].

We define a rectangulation of size $n$ as a decomposition of the square into
$n$ axis-parallel rectangles with disjoint interiors. The segments of a
rectangulation are the inclusionwise maximal line segments composed of edges
of the rectangles, excluding the edges of the decomposed square. We suppose
throughout that the rectangulations are generic, in the sense that no four
rectangles have a common vertex.

In order to focus on the combinatorial structure of a rectangulation, we
recall two equivalence relations between rectangulations (see for instance
[ACFF24] and references therein). We say that a rectangle $r$ is above another
rectangle $s$ (and $s$ is below $r$) if either the bottom edge of $r$ lies in
the same segment as the top edge of $s$, or if $r$ is above another rectangle
$t$ that is above $s$. We define on the left of and on the right of similarly.
Two rectangulations are said to be weakly equivalent if there exists a
bijection between their rectangles that preserves the above–below and
left–right relations between the rectangles. Weak equivalence classes of
rectangulations will be referred to as weak rectangulations. (Note that this
is a slight, yet convenient abuse of terminology, as weak rectangulations are
really sets of rectangulations.) On the other hand, two rectangulations are
said to be strongly equivalent when there exists a bijection between their
rectangles that not only preserves the above–below and left–right relations,
but also the adjacency relation between rectangles. We will naturally refer to
strong equivalence classes of rectangulations as strong rectangulations.

In order to make sense of these definitions, it is useful to consider wall
slides in a rectangulation: the local changes consisting of shifting a
horizontal segment vertically, or a vertical segment horizontally, while
extending or shortening the incident segments accordingly. Performing a wall
slide in a rectangulation $R$ leads to a rectangulation that is always weakly
equivalent to $R$. However, if the wall slide changes the adjacency relation
between the rectangles, then the resulting rectangulation is not strongly
equivalent to $R$ anymore. A diagonal rectangulation is a rectangulation in
which every rectangle intersects the top–left to bottom–right diagonal of the
square. Examples of rectangulations are given in Figure 2. It is simple to
check that every weak rectangulation has a diagonal representative, hence weak
rectangulations can also be thought of as diagonal rectangulations.

Figure 2. Four rectangulations. The rightmost rectangulation is not weakly
equivalent to any other. The leftmost three are weakly equivalent, but only
the first two are strongly equivalent. Only the third one is diagonal.

###  1.3. Weak and strong rectangulotopes

Weak and strong rectangulations of size $n$ have been shown to define
congruences of the weak Bruhat order on $\mathfrak{S}_{n}$.

The weak rectangulation congruence $\asymp$ (or Baxter congruence) was first
explicitly studied by S. Law and N. Reading [LR12] and revisited in [Rea15,
Thm. 1.1 & Exm. 4.10] in terms of arc diagrams. Its classes are in bijection
with weak rectangulations, but also with Baxter permutations [CGHK78, Mal79],
with twin binary trees [DG96, Gir12], and with many other combinatorial
families [FFNO11]. The corresponding quotientopes will be referred to as the
weak rectangulotopes and denoted by $\mathds{WR}(n)$. We note that weak
rectangulotopes were already constructed as Minkowski sums of two opposite
associahedra in [LR12], even before the general constructions of quotientopes
of [PS19, PPR23]. For $n=4$, the weak rectangulation lattice is represented in
Figure 3 and the weak rectangulotope is represented in Figure 4.

The strong rectangulation congruence
$\mathbin{\smash{\begin{smallmatrix}\backsim\\\\[-8.5359pt]
\sim\end{smallmatrix}}}$ was studied by N. Reading [Rea12], revisited in
[Rea15, Thm. 1.2 & Exm. 4.11] in terms of arc diagrams, and studied more
recently by E. Meehan [Mee17], and A. Asinowski, J. Cardinal, S. Felsner, and
É. Fusy [ACFF24]. Its classes are in bijection with strong rectangulations.
The corresponding quotientopes will be referred to as the strong
rectangulotopes and denoted by $\mathds{SR}(n)$. Strong rectangulotopes can be
obtained as quotientopes [PS19, PPR23] for the strong rectangulation
congruence. For $n=4$, the strong rectangulation lattice is represented in
Figure 5 and the strong rectangulotope is represented in Figure 6.

Figure 3. The weak rectangulation lattice.

Figure 4. The weak rectangulotope $\mathds{WR}(4)$.

Figure 5. The strong rectangulation lattice.

Figure 6. The strong rectangulotope $\mathds{SR}(4)$.

An important motivation for studying these quotientopes is the informative
structure of their skeleta, which are flip graphs on the rectangulations. A
flip is a local, reversible change in the structure of the rectangulation.
Flips in rectangulations come in three flavors:

  * •

simple flips replace a vertical segment incident to exactly two rectangles by
a horizontal segment, and vice-versa,

  * •

pivoting flips transform a pair of adjacent rectangles whose union is
L-shaped, changing a left–right pair into an above–below pair, and vice-versa,

  * •

wall slide flips are wall slides that modify the adjacency of the rectangles,
removing exactly one adjacency and adding exactly one. These are only relevant
in strong rectangulations.

The various types of flips are illustrated in Figure 7. We refer to [LR12,
CSS18, Mee17, ACFF24] for detailed descriptions of the flip graphs on both
weak and strong rectangulations. Just like associahedra encode the rotation
graphs on binary trees, the rectangulotopes directly yield flip graphs on
rectangulations. Namely, the skeleton of $\mathds{WR}(n)$ (resp. of
$\mathds{SR}(n)$) is isomorphic to the flip graph on weak (resp. strong)
rectangulations of size $n$.

(a) Simple flips.

(b) Pivoting flips.

(c) Wall slide flips.

Figure 7. The three types of flips between rectangulations. The flips are
possible only if the grey areas do not intersect any segment of the
rectangulation. [ACFF24, Fig. 19]

Figure 8. A rectangulation $R$ (left) and its pair of binary trees $S(R)$ and
$T(R)$ (right). Example from [ACFF24].

Figure 9. A diagonal rectangulation (left) and its pair of twin binary trees
(right). Example from [ACFF24].

Rectangulotopes enrich the family of natural quotientopes, alongside
associahedra, permutreehedra [PP18], certain brick polytopes [PS12, PS15,
Pil18], and certain graphical zonotopes [Pil18, Pil22], providing instructive
examples of application of the theory of lattice congruences to concrete
combinatorial objects. Our main results are elementary vertex and facet
descriptions of both families of quotientopes. For vertices, we describe the
coordinates of the vertex corresponding to a weak or strong rectangulation
with simple product formulas in the spirit of J.-L. Loday’s realization in
Theorem 1 (i). As mentioned in [PSZ23], there is no such formula for arbitrary
quotientopes, which makes rectangulotopes join the restricted club of Loday
type quotientopes, together with associahedra and permutreehedra [PP18]. For
facets, we show that both weak and strong rectangulotopes have $2^{n}-2$
facets (the maximal possible number of facets of a deformed permutahedron),
and provide simple formulas for the right hand side of the inequality
corresponding to a given proper nonempty subset of $[n]$. We now give the
necessary definitions for precisely stating these vertex and facet
descriptions of the weak and strong rectangulotopes.

###  1.4. Source and target trees of a rectangulation

Fix a rectangulation $R$ of size $n$, and consider the directed graph $D(R)$
whose vertices are all vertices of $R$, and whose edges are obtained as
follows. For each rectangle $r$ of $R$, we include in $D(R)$ four edges
joining the vertices of $r$, where the horizontal edges are oriented from left
to right, and the vertical edges are oriented from bottom to top. Hence, in
the rectangle $r$, its bottom–left corner is its source $s(r)$, while its
top–right corner is its target $t(r)$. Note that since $R$ is generic, the
sources $\left\\{s(r)\;\middle|\;r\in R\right\\}$ and the targets
$\left\\{t(r)\;\middle|\;r\in R\right\\}$ are disjoint. The source tree $S(R)$
(resp. target tree $T(R)$) is the subgraph of $D(R)$ induced by the sources
$\left\\{s(r)\;\middle|\;r\in R\right\\}$ (resp. by the targets
$\left\\{t(r)\;\middle|\;r\in R\right\\}$). It is not difficult to check that
the source tree $S(R)$ (resp. target tree $T(R)$) is a binary tree, rooted at
the bottom–left (resp. top–right) corner of $R$, and oriented from (resp.
towards) its root.

We complete each node of $S(R)$ and $T(R)$ with a vertical (resp. horizontal)
leaf if it has no vertical (resp. horizontal) child. An example is given in
Figure 8. If the rectangulation $R$ is diagonal, we retrieve the well-studied
pair of twin binary trees [DG96, Gir12], see Figure 9.

Recall that the inorder labeling of a binary tree $T$ is the labeling of the
nodes of $T$ such that the label of each node $t$ of $T$ is larger than all
labels in the left subtree of $t$ and larger than all labels in the right
subtree of $t$. For any rectangle $r$ of $R$, the inorder label of the source
$s(r)$ in $S(R)$ coincides with the inorder label of the target $t(r)$ in
$T(R)$. The inorder can also be retrieved from the above–below and left–right
relationships defined before, as the transitive closure of the union of the
below and right partial orders. This enables to unambiguously label the
rectangles of $R$ by the inorder. The resulting labeling coincides with the
NW–SE labeling of [ACFF24]. From now on, the labels of the rectangles in a
rectangulation are the inorder labels, and the two trees $T(R)$ and $S(R)$ are
defined on the vertex set $[n]$ accordingly. For each $i\in[n]$, we refer to
its two subtrees in $T(R)$ as the horizontal and vertical subtrees, and
similarly for $S(R)$.

###  1.5. Realizations of weak rectangulotopes

Our first results are simple vertex and facet descriptions of the weak
rectangulotopes $\mathds{WR}(n)$. For the vertices, we provide a concise
formula for the coordinates, that consists of applying J.-L. Loday’s formula
on each of the source and target trees of the rectangulation. For the facets,
we combine the right hand sides of two opposite associahedra to obtain those
of the weak rectangulotopes. These two descriptions materialize the result of
Law and Reading that the weak rectangulotopes are Minkowski sums of two
opposite associahedra [LR12].

######  Theorem 2.

The weak rectangulotope $\mathds{WR}(n)$ is realized by the polytope
equivalently described as:

  1. (i)

the convex hull of the points

$\sum_{i\in[n]}(\smash{\overset{\frown}{w}}^{R}_{i}-\smash{\overset{\smile}{w}}^{R}_{i})\cdot{\boldsymbol{e}}_{i}$

for all weak rectangulations $R$ of size $n$, with

$\smash{\overset{\frown}{w}}^{R}_{i}\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}h^{T}_{i}\cdot
v^{T}_{i}\qquad\text{and}\qquad\smash{\overset{\smile}{w}}^{R}_{i}\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}h^{S}_{i}\cdot
v^{S}_{i},$

where $S$ and $T$ are the source and target trees of the rectangulation $R$,
and $h^{T}_{i}$ and $v^{T}_{i}$ denote the number of leaves in the horizontal
and vertical subtrees of $i$ in $T$,

  2. (ii)

the intersection of the hyperplane defined by $\sum_{i\in[n]}x_{i}=0$ with the
halfspaces defined by

$\sum_{i\in S}x_{i}\leq\\#\left\\{I\text{ interval of
}[n]\;\middle|\;I\not\subseteq S\text{ and }I\not\subseteq[n]\smallsetminus
S\right\\}$

for all subsets $\varnothing\neq S\subsetneq[n]$.

$(-3,-1,1,3)$ $(-3,-1,5,-1)$ $(-3,3,-3,3)$ $(1,-5,1,3)$ $(-3,0,5,-2)$
$(-3,5,-3,1)$ $(-1,3,-5,3)$ $(2,-5,0,3)$ $(-3,5,0,-2)$ $(-2,0,5,-3)$
$(1,-5,5,-1)$ $(-1,5,-5,1)$ $(3,-5,0,2)$ $(2,0,-5,3)$ $(-2,5,0,-3)$
$(1,-3,5,-3)$ $(3,-5,3,-1)$ $(3,0,-5,2)$ $(-1,5,-1,-3)$ $(3,-3,3,-3)$
$(3,1,-5,1)$ $(3,1,-1,-3)$

Table 1. The vertices of the weak rectangulotope $\mathds{WR}(4)$ of Figure 4.

$(-6,-2,2,6)$ $(-6,-2,9,-1)$ $(-6,5,-5,6)$ $(1,-9,2,6)$ $(-6,1,9,-4)$
$(-6,9,-5,2)$ $(-2,5,-9,6)$ $(4,-9,-1,6)$ $(-6,9,1,-4)$ $(-4,1,9,-6)$
$(2,-9,9,-2)$ $(-2,9,-9,2)$ $(6,-9,-1,4)$ $(4,-1,-9,6)$ $(-4,9,1,-6)$
$(2,-5,9,-6)$ $(6,-9,5,-2)$ $(6,-1,-9,4)$ $(-1,9,-2,-6)$ $(6,-5,5,-6)$
$(6,2,-9,1)$ $(6,2,-2,-6)$ $(1,-9,9,-1)$ $(-1,9,-9,1)$

Table 2. The vertices of the strong rectangulotope $\mathds{SR}(4)$ of Figure
6.

For instance, the weak rectangulotope $\mathds{WR}(4)$ is illustrated in
Figure 4. The coordinates of the vertices of $\mathds{WR}(4)$ corresponding to
all weak rectangulations are gathered in Table 1. The facet inequalities of
$\mathds{WR}(4)$ corresponding to each nonempty proper subset of $[4]$ are
gathered in Table 3.

$J$ $1$ $2$ $3$ $4$ $12$ $13$ $14$ $23$ $24$ $34$ $123$ $124$ $134$ $234$
$f_{\asymp}(J)$ $3$ $5$ $5$ $3$ $4$ $6$ $5$ $5$ $6$ $4$ $3$ $5$ $5$ $3$

Table 3. The facets of the weak rectangulotope $\mathds{WR}(4)$ of Figure 4.

The vertex of $\mathds{WR}(16)$ corresponding to the weak rectangulation of
Figure 9 is

$(-3,0,26,2,-9,5,-69,-4,17,0,-8,59,2,-20,0,2).$

###  1.6. Realizations of strong rectangulotopes

In order to exhibit a similar realization for the strong rectangulotopes, we
need to count subsets of leaves that lie in some subtrees of both the source
and target trees of a rectangulation. Two leaves of the trees $T(R)$ and
$S(R)$ are said to be common leaves if the edges to their parents lie on the
same segment of $R$. We denote by
${}^{i}\\!\\!\\!\raisebox{0.85355pt}{\smash{\raisebox{-7.11317pt}{\includegraphics[scale={.5}]{verticalPattern}}}}\\!\\!\\!{}_{j}$
the situation where the rectangles $r_{i}$ and $r_{j}$ of inorder labels $i$
and $j$ share a vertical segment containing the right edge of $r_{i}$ and the
left edge of $r_{j}$, and the bottom edge of $r_{i}$ is below the top edge of
$r_{j}$. Similarly, we denote by
$\;{}^{i}\\!\\!\\!\\!\\!\smash{\raisebox{-4.26773pt}{\includegraphics[scale={.5}]{horizontalPattern}}}\\!\\!\\!\\!\\!\raisebox{-1.70709pt}{${}_{j}$}\,$
the situation where the rectangles $r_{i}$ and $r_{j}$ share a horizontal
segment containing the bottom edge of $r_{i}$ and the top edge of $r_{j}$, and
the right edge of $r_{i}$ is on the right of the left edge of $r_{j}$. We use
the Iverson bracket $\llbracket\varphi\rrbracket$, which is equal to 1 if
$\varphi$ holds, and 0 otherwise.

######  Theorem 3.

The strong rectangulotope $\mathds{SR}(n)$ is realized by the polytope
equivalently described as:

  1. (i)

the convex hull of the points

$\sum_{i,j\in[n],i<j}(\smash{\overset{\sim}{w}}^{R}_{i,j}-\smash{\overset{\backsim}{w}}^{R}_{i,j})\cdot({\boldsymbol{e}}_{i}-{\boldsymbol{e}}_{j}),$

for all strong rectangulations $R$ of size $n$, with

$\smash{\overset{\sim}{w}}^{R}_{i,j}\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}h^{T}_{i}\cdot
cv^{T,S}_{i,j}\cdot
h^{S}_{j}\cdot\llbracket\;\neg\;{}^{i}\\!\\!\\!\raisebox{0.85355pt}{\smash{\raisebox{-7.11317pt}{\includegraphics[scale={.5}]{verticalPattern}}}}\\!\\!\\!{}_{j}\;\rrbracket\qquad\text{and}\qquad\smash{\overset{\backsim}{w}}^{R}_{i,j}\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}v^{S}_{i}\cdot
ch^{S,T}_{i,j}\cdot
v^{T}_{j}\cdot\llbracket\;\neg\;\;{}^{i}\\!\\!\\!\\!\\!\smash{\raisebox{-4.26773pt}{\includegraphics[scale={.5}]{horizontalPattern}}}\\!\\!\\!\\!\\!\raisebox{-1.70709pt}{${}_{j}$}\;\;\rrbracket,$

where:

     * •

$S$ and $T$ are the source and target trees of the rectangulation $R$,

     * •

$h^{T}_{i}$ and $v^{T}_{i}$ denote the number of leaves in the horizontal and
vertical subtrees of $i$ in $T$,

     * •

$ch^{T,S}_{i,j}$ (resp. $cv^{T,S}_{i,j}$) denote the number of common leaves
of the horizontal (resp. vertical) subtree of $i$ in $T$ and the horizontal
(resp. vertical) subtree of $j$ in $S$,

  2. (ii)

the intersection of the hyperplane defined by $\sum_{i\in[n]}x_{i}=0$ with the
halfspaces defined by

$\sum_{i\in S}x_{i}\leq\\#\left\\{I,J\;\middle|\;I\not\subseteq S\text{ and
}J\not\subseteq[n]\smallsetminus
S\right\\}+\\#\left\\{I,J\;\middle|\;I\not\subseteq[n]\smallsetminus S\text{
and }J\not\subseteq S\right\\}$

for all subsets $\varnothing\neq S\subsetneq[n]$, where $I,J$ denote nonempty
and consecutive intervals of $[n]$.

For instance, the strong rectangulotope $\mathds{SR}(4)$ is illustrated in
Figure 6. The coordinates of the vertices of $\mathds{SR}(4)$ corresponding to
all strong rectangulations are gathered in Table 2. The facet inequalities of
$\mathds{SR}(4)$ corresponding to each nonempty proper subset of $[4]$ are
gathered in Table 4.

$J$ $1$ $2$ $3$ $4$ $12$ $13$ $14$ $23$ $24$ $34$ $123$ $124$ $134$ $234$
$f_{\mathbin{\smash{\begin{smallmatrix}\backsim\\\\[-8.5359pt]
\sim\end{smallmatrix}}}}(J)$ $6$ $9$ $9$ $6$ $8$ $11$ $10$ $10$ $11$ $8$ $6$
$9$ $9$ $6$

Table 4. The facets of the strong rectangulotope $\mathds{SR}(4)$ of Figure 6.

The vertex of $\mathds{SR}(16)$ corresponding to the strong rectangulation of
Figure 8 is

$(-41,5,262,24,-110,50,-525,-50,184,3,-88,450,35,-221,-5,27).$

We think of the formula of Theorem 3 (i) as the analogue of J.-L.-Loday’s
product formula of Theorem 1 (i) for the coordinates of the vertices of the
associahedron. We note however that our formula is quadratic in $n$. It
remains unclear to us if there is a simple linear formula to compute the
coordinates of the vertex of $\mathds{SR}(n)$ corresponding to a given strong
rectangulation.

###  1.7. Plan of the paper

Section 2 is dedicated to the background on quotientopes and their
realizations as Minkowski sums of shard polytopes, due to A. Padrol, V.
Pilaud, and J. Ritter [PPR23], which will be our main tool throughout. Section
3 details the case of weak rectangulations, while Section 4 deals with strong
rectangulations. In both cases, we provide both the vertex and facet
descriptions of these polytopes.

###  1.8. Acknowledgments

This work was initiated at the Workshop on Combinatorics, Algorithms, and
Geometry held on March 4–8, 2024 in Dresden, Germany. The authors thank
Namrata and Torsten Mütze for the organization and the other participants of
the workshop for the stimulating interactions, notably on other combinatorial
aspects of rectangulations.

##  2\. Quotientopes

We now briefly recall some results on the weak Bruhat order and its quotients,
both from a lattice and geometric perspectives. We refer to [Rea05, Rea15,
Rea16a, Rea16b, PS19, PPR23] for details.

###  2.1. Weak order and noncrossing arc diagrams

Denote by $\mathfrak{S}_{n}$ the set of permutations of $[n]$. The inversion
set of $\sigma\in\mathfrak{S}_{n}$ is
$\operatorname{inv}(\sigma)\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\left\\{(\sigma_{i},\sigma_{j})\;\middle|\;1\leq
i<j\leq n\text{ and }\sigma_{i}>\sigma_{j}\right\\}$. The weak Bruhat
order111The weak Bruhat order is usually just referred to as the weak order
[Hum90, BB05]. In this paper, we prefer to use weak Bruhat order to avoid any
confusion with the weak poset defined on weak rectangulations. is the lattice
on the permutations of $\mathfrak{S}_{n}$ defined by the inclusion of their
inversion sets. See LABEL:fig:sylvesterCongruence (left). Note that the cover
relations in the weak Bruhat order are given by the transpositions of two
adjacent letters.

An arc on $[n]$ is a quadruple $(a,b,A,B)$ where $1\leq a<b\leq n$ and
$A\sqcup B$ forms a partition of the interval
${]a,b[}\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\\{a+1,\dots,b-1\\}$.
We represent an arc by an abscissa monotone curve wiggling around the
horizontal axis, starting at point $a$ and ending at point $b$, and passing
above the points of $A$ and below the points of $B$. A noncrossing arc diagram
on $[n]$ is a collection of arcs on $[n]$ where any two arcs do not cross in
their interior and have distinct left endpoints and distinct right endpoints
(but the right endpoint of an arc can be the left endpoint of another arc).

In [Rea15], N. Reading defined an elegant bijection between permutations of
$[n]$ and noncrossing arc diagrams on $[n]$. It sends a permutation $\sigma$
to the noncrossing arc diagram with an arc
$(\sigma_{j+1},\sigma_{j},A_{j},B_{j})$ for each descent $j\in[n-1]$ of
$\sigma$ (i.e. with $\sigma_{j}>\sigma_{j+1}$), where

$\displaystyle A_{j}$
$\displaystyle\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\left\\{\sigma_{i}\;\middle|\;1\leq
i<j\text{ and }\sigma_{j+1}<\sigma_{i}<\sigma_{j}\right\\}$
$\displaystyle\text{and}\qquad B_{j}$
$\displaystyle\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\left\\{\sigma_{k}\;\middle|\;j+1<k\leq
n\text{ and }\sigma_{j+1}<\sigma_{k}<\sigma_{j}\right\\}.$

As illustrated on the right with $\sigma=2531746$, this can also been
visualized by representing the table $(\sigma_{j},j)$ of the permutation
$\sigma$, drawing the segments corresponding to the descents of $\sigma$, and
letting all points fall on the horizontal axis, allowing the segments to bend
but not to cross each other nor to pass through a point. The single arcs
correspond to permutations with a single descent, that is, to join irreducible
permutations of the weak Bruhat order. In general, the noncrossing arc diagram
of a permutation $\sigma$ actually encodes the canonical join representation
of $\sigma$ in the weak Bruhat order (which was known to exist, as the weak
Bruhat order is join semidistributive). See [Rea15] for details.

###  2.2. Quotients and arc ideals

A lattice congruence of the weak Bruhat order is an equivalence relation
$\equiv$ on $\mathfrak{S}_{n}$ that respects the meet and join operations,
i.e. such that $x\equiv x^{\prime}$ and $y\equiv y^{\prime}$ implies $x\wedge
y\,\equiv\,x^{\prime}\wedge y^{\prime}$ and $x\vee y\,\equiv\,x^{\prime}\vee
y^{\prime}$. The lattice quotient $\mathfrak{S}_{n}/{\equiv}$ is the lattice
on the congruence classes of $\equiv$ where $X\leq Y$ if and only if there
exist $x\in X$ and $y\in Y$ such that $x\leq y$, and $X\wedge Y$ (resp. $X\vee
Y$) is the congruence class of $x\wedge y$ (resp. $x\vee y$) for any $x\in X$
and $y\in Y$.

For instance, the sets of linear extensions of binary trees (labeled in
inorder and oriented toward their roots) are the classes of the sylvester
congruence [HNT05]. See LABEL:fig:sylvesterCongruence (middle). The quotient
of the weak Bruhat order by the sylvester congruence is the classical Tamari
lattice. See LABEL:fig:sylvesterCongruence (right).

Respecting the meet and join operation is a strong condition that imposes
additional structure on $\equiv$. In fact, all the congruence classes of
$\equiv$ are intervals of the weak Bruhat order, and the quotient
$\mathfrak{S}_{n}/{\equiv}$ is isomorphic (as a poset) to the subposet of the
weak Bruhat order induced by permutations which are minimal in their class.
Moreover, the latter are precisely the permutations whose noncrossing arc
diagrams only use arcs corresponding to join irreducible permutations which
are minimal in their class, and we denote by $\mathcal{A}_{\equiv}$ this set
of arcs. In other words, the classes of $\equiv$ are in bijection with
noncrossing arc diagrams using only arcs in $\mathcal{A}_{\equiv}$. This
bijection actually translates the fact that canonical join representations
behave properly under lattice quotients.

For instance, the join irreducible permutations minimal in their sylvester
congruence class are precisely the up arcs, i.e. the arcs of the form
$(a,b,{]a,b[},\varnothing)$ (similarly, we call down arcs the arcs of the form
$(a,b,\varnothing,{]a,b[})$). The corresponding noncrossing arc diagrams are
famously known as noncrossing partitions.

An arc $(a,b,A,B)$ is a subarc of an arc
$(a^{\prime},b^{\prime},A^{\prime},B^{\prime})$ if $a^{\prime}\leq a<b\leq b$
and $A\subseteq A^{\prime}$ while $B\subseteq B^{\prime}$. An arc ideal is a
subset of arcs closed by subarcs. The map
${\equiv}\mapsto\mathcal{A}_{\equiv}$ is a bijection between the lattice
congruences of the weak Bruhat order and the arc ideals. In other words, the
lattice of congruences of the weak Bruhat order is distributive, and its poset
of join irreducibles is isomorphic to the subarc order, illustrated on the
right for $n=4$.

###  2.3. Quotient fans and shards

Figure 10. The braid fan (left) and the sylvester fan (right). [PS19, Fig. 1]
& [PPR23, Fig. 5]

The braid arrangement is the hyperplane arrangement consisting of the
hyperplanes
$\left\\{{\boldsymbol{x}}\in\mathbb{R}^{n}\;\middle|\;x_{a}=x_{b}\right\\}$
for all $1\leq a<b\leq n$. It has a chamber for each permutation $\sigma$ of
$[n]$, given by the set of vectors whose coordinates are ordered as $\sigma$.
It has a ray for each nonempty proper subset $\varnothing\neq J\subsetneq[n]$.
(To be more precise when speaking about rays, we should actually consider the
essentialization of the braid arrangement obtained by slicing it with a
hyperplane normal to its lineality space, which is generated by the vector
$(1,\dots,1)$.) See Figure 10 (left).

The shard of an arc $(a,b,A,B)$ is the piece of the braid hyperplane
${x_{a}=x_{b}}$ defined by the inequalities $x_{a^{\prime}}<x_{a}$ for all
$a^{\prime}\in A$ and $x_{b}<x_{b^{\prime}}$ for all $b^{\prime}\in B$. In
other words, the shards decompose each hyperplane $x_{a}=x_{b}$ of the braid
arrangement into $2^{b-a-1}$ cones.

The quotient fan of a congruence $\equiv$ of the weak Bruhat order is the
polyhedral fan $\mathcal{F}_{\equiv}$ where

  * •

the maximal cones are obtained by glueing together the chambers of the braid
arrangement corresponding to permutations in the same congruence class of
$\equiv$,

  * •

the union of the codimension $1$ cones is the union of the shards of the arcs
of $\mathcal{A}_{\equiv}$.

(These two descriptions are equivalent.) By construction, the braid fan
refines the quotient fan $\mathcal{F}_{\equiv}$, and the dual graph of the
quotient fan $\mathcal{F}_{\equiv}$ is isomorphic to the cover graph of the
quotient $\mathfrak{S}_{n}/{\equiv}$. For instance, Figure 10 (right)
represents the sylvester fan (the quotient fan of the sylvester congruence of
LABEL:fig:sylvesterCongruence (middle)) for $n=4$, whose dual graph is the
cover graph of the Tamari lattice of LABEL:fig:sylvesterCongruence (right).
The maximal cone corresponding to a binary tree $T$ is given by
$\mathds{C}^{T}=\left\\{{\boldsymbol{x}}\in\mathbb{R}^{n}\;\middle|\;x_{i}\leq
x_{i}\text{ for each edge }i\to j\text{ in }T\right\\}$.

It was shown in [APR21, Lem. 23] that the ray of the braid arrangement
corresponding to a nonempty proper subset $\varnothing\neq J\subsetneq[n]$ is
preserved in the quotient fan $\mathcal{F}_{\equiv}$ if and only if the arc
ideal $\mathcal{A}_{\equiv}$ contains the $|J|-1$ down arcs joining two
consecutive elements of $J$ and the $n-|J|-1$ up arcs joining two consecutive
elements of $[n]\smallsetminus J$. An immediate consequence is that all
$2^{n}-2$ rays of the braid arrangement are preserved in the quotient fan
$\mathcal{F}_{\equiv}$ if and only if the arc ideal $\mathcal{A}_{\equiv}$
contains all up arcs and all down arcs (in other words, if it is above the
weak rectangulation congruence in the lattice of congruences of the weak
Bruhat order).

###  2.4. Quotientopes and shard polytopes

A quotientope for a lattice congruence $\equiv$ of the weak Bruhat order is a
polytope whose normal fan is the quotient fan $\mathcal{F}_{\equiv}$. In
particular, the skeleton of a quotientope is isomorphic to the cover graph of
the quotient $\mathfrak{S}_{n}/{\equiv}$. For instance, the associahedron
$\mathds{A}(n)$ (Figure 1 (right) when $n=4$) is a quotientope for the
sylvester congruence (LABEL:fig:sylvesterCongruence (middle) when $n=4$), its
normal fan is the sylvester fan (Figure 10 (right) when $n=4$), and its
skeleton is the cover graph of the Tamari lattice
(LABEL:fig:sylvesterCongruence (right) when $n=4$). The existence of
quotientopes was first proved in [PS19] and later better understood in [PPR23]
using Minkowski sums of shard polytopes, the approach we will use throughout
the paper.

The Minkowski sum of two polytopes
$\mathds{P},\mathds{Q}\subset\mathbb{R}^{n}$ is
$\mathds{P}+\mathds{Q}\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\left\\{{\boldsymbol{p}}+{\boldsymbol{q}}\;\middle|\;{\boldsymbol{p}}\in\mathds{P}\text{
and }{\boldsymbol{q}}\in\mathds{Q}\right\\}\subset\mathbb{R}^{n}$. Recall that
for any vector ${\boldsymbol{v}}\neq{\boldsymbol{0}}$ of $\mathbb{R}^{n}$, the
face of $\mathds{P}+\mathds{Q}$ maximizing the scalar product with
${\boldsymbol{v}}$ is the Minkowski sum of the faces of $\mathds{P}$ and
$\mathds{Q}$ maximizing the scalar product with ${\boldsymbol{v}}$. In
particular, if ${\boldsymbol{v}}$ is a generic direction, the vertex of
$\mathds{P}+\mathds{Q}$ that is extremal in direction ${\boldsymbol{v}}$ is
just the sum of the vertices of $\mathds{P}$ and $\mathds{Q}$ that are
extremal in direction ${\boldsymbol{v}}$. Moreover, the normal fan of the
Minkowski sum $\mathds{P}+\mathds{Q}$ is the common refinement of the normal
fans of $\mathds{P}$ and $\mathds{Q}$.

Consider an arc
$\alpha\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}(a,b,A,B)$
on $[n]$. An $\alpha$-alternating matching is a sequence $a\leq
i_{1}<j_{1}<i_{2}<j_{2}<\dots<i_{q}<j_{q}\leq b$ such that
$i_{p}\in\\{a\\}\cup A$ and $j_{p}\in\\{b\\}\cup B$ for all $p\in[q]$. Its
characteristic vector is
$\sum_{p\in[q]}({\boldsymbol{e}}_{i_{p}}-{\boldsymbol{e}}_{j_{p}})$. The shard
polytope of $\alpha$ is the convex hull $\mathds{SP}(\alpha)$ of the
characteristic vectors of all $\alpha$-alternating matchings. We refer to
Figure 11 for an illustration of this definition. It was shown in [PPR23] that
any Minkowski sum of positive scalings of the shard polytopes
$\mathds{SP}(\alpha)$ for all arcs $\alpha$ in the arc ideal
$\mathcal{A}_{\equiv}$ is a quotientope for $\equiv$.

Figure 11. The shard polytopes of the up arc $(1,4,\\{2,3\\},\varnothing)$,
the down arc $(1,4,\varnothing,\\{2,3\\})$, the yin arc
$(1,4,\\{2\\},\\{3\\})$, and the yang arc $(1,4,\\{3\\},\\{2\\})$. The
vertices of the shard polytope of an arc
$\alpha\mbox{\,\raisebox{0.77498pt}{\scriptsize$\mathrm{:}$}$=$\,}(a,b,A,B)$
are labeled by the corresponding $\alpha$-alternating matchings, where we use
solid dots $\bullet$ for elements in $\\{a\\}\cup A$ and hollow dots $\circ$
for elements in $B\cup\\{b\\}$. The corresponding vertex coordinates are
directly read replacing $\bullet$ by $1$ and $\circ$ by $-1$. For instance,
the vertex labeled ${\bullet\cdot\cdot\,\circ}$ has coordinates $(1,0,0,-1)$.
Adapted from [PPR23, Fig. 10].

A set function $f:2^{[n]}\mapsto\mathbb{R}$ is said to be submodular when
$f(X\cup Y)+f(X\cap Y)\leq f(X)+f(Y)$ for any $X,Y\subseteq[n]$. By
definition, any quotientope is a deformed permutahedron, and can thus be
written as

$\Big{\\{}x\in\mathbb{R}^{n}\;\Big{|}\;\sum_{i\in[n]}x_{i}=f([n])\text{ and
}\sum_{i\in S}x_{i}\leq f(S)\text{ for all }\varnothing\neq
S\subseteq[n]\Big{\\}},$

where $f$ is a submodular set function. We will need the following simple
result: Given a collection
$\mathds{P}_{1},\mathds{P}_{2},\ldots,\mathds{P}_{k}$ of deformed permutahedra
defined by submodular set functions $f_{1},f_{2},\ldots,f_{k}$, their
Minkowski sum $\sum_{i}\mathds{P}_{i}$ is defined by the submodular function
$f\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\sum_{i}f_{i}$.

##  3\. Weak rectangulotopes

This section is devoted to weak rectangulations and the proof of Theorem 2.

###  3.1. The weak poset

Given a rectangulation $R$, let us consider its source and target trees $S(R)$
and $T(R)$, and orient the horizontal edges from left to right, and the
vertical edges from bottom to top. This defines two partial orders on $[n]$.
The weak poset $([n],\prec_{w}^{R})$ of the rectangulation $R$ is the
transitive closure of the union of these two partial orders defined by $S(R)$
and $T(R)$. Equivalently, the weak poset can be defined by considering the
adjacency graph of the rectangles in a diagonal representative of the weak
equivalence class of $R$, orienting its edges from left to right and from
bottom to top, and taking the transitive closure of this directed acyclic
graph. These posets were characterized (and called Baxter posets) by E. Meehan
[Mee19]. The weak poset is a two-dimensional lattice, whose minimum is the
root of $S(R)$ and whose maximum is the root of $T(R)$. See Figure 12.

Figure 12. The weak poset of the rectangulation of Figure 8, visualized on the
rectangulation of Figure 8 (left) and on its diagonal rectangulation of Figure
9 (right). Example from [ACFF24].

###  3.2. The weak rectangulation congruence

We consider the set $\mathcal{L}(\prec_{w}^{R})$ of linear extensions of the
weak poset $\prec_{w}^{R}$:

$\mathcal{L}(\prec_{w}^{R})\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\big{\\{}\sigma\in\mathfrak{S}_{n}\;\big{|}\;i\prec_{w}^{R}j\Rightarrow\sigma^{-1}_{i}<\sigma^{-1}_{j}\big{\\}}.$

We recall that Baxter permutations [CGHK78, Mal79] are permutations avoiding
the vincular patterns $2\underline{41}3$ and $3\underline{14}2$, where the
underlining indicates that the symbols must appear contiguously in the
permutation. Similarly, twisted Baxter permutations are permutations avoiding
the patterns $2\underline{41}3$ and $3\underline{41}2$, and co-twisted Baxter
permutations are permutations avoiding the patterns $2\underline{14}3$ and
$3\underline{14}2$. These permutation families are equinumerous and their
sizes are the Baxter numbers, see [OEI10, A001181]. They are central in the
theory of rectangulations and appear in many other contexts [FFNO11].

######  Theorem 4 ([LR12]).

The subsets $\mathcal{L}(\prec_{w}^{R})$ of $\mathfrak{S}_{n}$, for all
rectangulations $R$ of size $n$, are equivalence classes of a congruence
relation $\asymp$ on the weak Bruhat order on $\mathfrak{S}_{n}$. Furthermore:

  * •

the congruence classes are one-to-one with weak rectangulations,

  * •

the minimal elements of the congruence classes are the twisted Baxter
permutations,

  * •

the maximal elements of the congruence classes are the co-twisted Baxter
permutations,

  * •

the congruence classes each contain a single Baxter permutation.

We call this congruence the weak rectangulation congruence (it is sometimes
referred to as the Baxter congruence). It is the intersection of the sylvester
congruence with the anti-sylvester congruence. The weak rectangulotope
$\mathds{WR}(n)$ is the quotientope of the weak rectangulation congruence
$\asymp$ on the weak Bruhat order on $\mathfrak{S}_{n}$.

By construction, the quotient fan $\mathcal{F}_{\asymp}$ has a maximal cone
$\mathds{C}_{w}^{R}$ for each weak rectangulation $R$ of size $n$. This cone
is given by
$\mathds{C}_{w}^{R}=\left\\{{\boldsymbol{x}}\in\mathbb{R}^{n}\;\middle|\;x_{i}\leq
x_{j}\text{ if }i\prec_{w}^{R}j\right\\}$. Note that there is a bijection
between the facets of $\mathds{C}_{w}^{R}$, the cover relations of
$\prec_{w}^{R}$, and the feasible flips in $R$. The definition of the weak
poset just translates the fact that the weak rectangulation fan
$\mathcal{F}_{\asymp}$ is the common refinement of the sylvester fan and the
anti-sylvester fan. Namely, as $\mathds{C}_{w}^{R}$ is the intersection of the
cone of the sylvester fan corresponding to the target tree $T(R)$ with the
cone of the anti-sylvester fan corresponding to the source tree $S(R)$, the
weak poset $\prec_{w}^{R}$ is the transitive closure of the union of the
posets associated to $S(R)$ and $T(R)$.

Note that weak rectangulotopes were first constructed by S. Law and N. Reading
in [LR12] as Minkowski sums of two opposite associahedra. Our vertex and facet
descriptions of Theorem 2 can be directly derived from this construction.
Here, we provide a more pedestrian approach based on Minkowski sums of shard
polytopes, as it will serve as a template for the more involved proof of
Theorem 3 in Section 4.

###  3.3. Up and down arcs

The arc ideal of the weak rectangulation congruence was already considered in
[Rea15, Exm. 4.10].

######  Lemma 5 ([Rea15, Exm. 4.10]).

The weak rectangulation congruence $\asymp$ on $\mathfrak{S}_{n}$ is defined
by the arc ideal composed of arcs that do not cross the horizontal line.

###### Proof.

We consider the forbidden vincular patterns $2\underline{41}3$ and
$3\underline{41}2$ that define the minimal elements of each congruence class
of $\asymp$. We observe that every occurrence of a pattern in a permutation
corresponds to an occurrence of an arc that cross the horizontal line at least
once in the arc diagram of the permutation. The twisted Baxter permutations
are therefore the permutations whose arc diagrams are composed only of arcs
that do not cross the horizontal line. ∎

We classified these arcs into two families: the up arcs and the down arcs. For
an interval $I$ of $[n]$ of size at least $2$, the up arc
$\mathrel{\mathop{\frown}\limits_{\vbox to0.0pt{\kern-7.0pt\hbox{$\scriptstyle
I$}\vss}}}$ (resp. down arc $\mathrel{\mathop{\smile}\limits^{\vbox
to0.60275pt{\kern-2.0pt\hbox{$\scriptstyle I$}\vss}}}$) is the arc that starts
at $\min(I)$ and ends at $\max(I)$, and passes above (resp. below) all
remaining elements of $I$, that is,

$\mathrel{\mathop{\frown}\limits_{\vbox to0.0pt{\kern-7.0pt\hbox{$\scriptstyle
I$}\vss}}}$
$\displaystyle\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\big{(}\min(I),\max(I),I\smallsetminus\\{\min(I),\max(I)\\},\varnothing\big{)}$
and$\mathrel{\mathop{\smile}\limits^{\vbox
to0.60275pt{\kern-2.0pt\hbox{$\scriptstyle I$}\vss}}}$
$\displaystyle\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\big{(}\min(I),\max(I),\varnothing,I\smallsetminus\\{\min(I),\max(I)\\}\big{)}.$

Note that the basic arc $(i,i+1,\varnothing,\varnothing)$ is both an up and
down arc. The up arcs correspond to the sylvester congruence, while the down
arcs correspond to the anti-sylvester congruence.

###  3.4. Shard polytopes of up and down arcs

From the results of Section 2.4, the quotientope is realized by a Minkowski
sum of the shard polytopes of the up arcs and the down arcs. These
quotientopes are simplices and anti-simplices.

######  Lemma 6.

The up shard polytope
$\mathds{SP}(\smash{\raisebox{1.42271pt}{$\mathrel{\mathop{\frown}\limits_{\vbox
to0.0pt{\kern-7.0pt\hbox{$\scriptstyle I$}\vss}}}$}})$ is a translate of the
simplex $\operatorname{conv}\left\\{{\boldsymbol{e}}_{i}\;\middle|\;i\in
I\right\\}$.

######  Lemma 7.

The down shard polytope
$\mathds{SP}(\smash{\raisebox{-1.42271pt}{$\mathrel{\mathop{\smile}\limits^{\vbox
to0.60275pt{\kern-2.0pt\hbox{$\scriptstyle I$}\vss}}}$}})$ is a translate of
the negative simplex
$\operatorname{conv}\left\\{-{\boldsymbol{e}}_{i}\;\middle|\;i\in I\right\\}$.

We refer to Figure 11 for examples of up and down shard polytopes.

######  Proposition 8.

The weak rectangulotope $\mathds{WR}(n)$ is realized by the Minkowski sum of
all up and down shard polytopes.

Since the combinatorial type of a Minkowski sum is invariant to translation of
the summands, we can use the simplices defined in Lemmas 6 and 7 as a
definition of the up and down shard polytopes. Also note that since the basic
arcs $(i,i+1,\varnothing,\varnothing)$ are both up and down, each basic shard
polytope is summed twice in the proposed realization. This, again, does not
change the combinatorial type of the polytope.

Proposition 8 in particular recovers the result of [LR12] that
$\mathds{WR}(n)$ is the sum of two opposite associahedra of J.-L. Loday
[LR12], corresponding to the sylvester and anti-sylvester congruences.

###  3.5. Submodular functions of weak rectangulotopes

The description of the weak rectangulotope $\mathds{WR}(n)$ as a Minkowski sum
in Proposition 8 allows us to easily compute the corresponding submodular
function. The arc ideal of the weak rectangulation congruence contains exactly
all up arcs and all down arcs, hence from the result of [APR21] mentioned in
Section 2.3, all $2^{n}-2$ rays of the braid fan are preserved in the fan of
the weak rectangulotope. This implies that every nonempty proper subset will
define a facet of the weak rectangulotope, and the description of the weak
rectangulotope by its submodular function is actually an irredundant facet
description.

######  Lemma 9.

The weak rectangulotope $\mathds{WR}(n)$ is realized by the following
submodular function:

$f_{\asymp}(S)\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\\#\big{\\{}I\text{
interval of }[n]\;\big{|}\;I\not\subseteq S\text{ and
}I\not\subseteq[n]\smallsetminus S\big{\\}}.$

###### Proof.

The submodular function defining the realization of $\mathds{WR}(n)$ is the
sum of the submodular functions defining the up and down shard polytope in
Lemmas 6 and 7. The shard polytope
$\mathds{SP}(\smash{\raisebox{1.42271pt}{$\mathrel{\mathop{\frown}\limits_{\vbox
to0.0pt{\kern-7.0pt\hbox{$\scriptstyle I$}\vss}}}$}})$ of an up arc
$\mathrel{\mathop{\frown}\limits_{\vbox to0.0pt{\kern-7.0pt\hbox{$\scriptstyle
I$}\vss}}}$ is given by the submodular function

$f_{\smash{\raisebox{1.42271pt}{$\mathrel{\mathop{\frown}\limits_{\vbox
to0.0pt{\kern-7.0pt\hbox{$\scriptstyle
I$}\vss}}}$}}}(S)\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\llbracket
S\cap I\not=\emptyset\rrbracket.$

(Recall that $\llbracket\varphi\rrbracket$ is equal to 1 if $\varphi$ holds,
and $0$ otherwise.) Similarly, the shard polytope
$\mathds{SP}(\smash{\raisebox{-1.42271pt}{$\mathrel{\mathop{\smile}\limits^{\vbox
to0.60275pt{\kern-2.0pt\hbox{$\scriptstyle I$}\vss}}}$}})$ of a down arc
$\mathrel{\mathop{\smile}\limits^{\vbox
to0.60275pt{\kern-2.0pt\hbox{$\scriptstyle I$}\vss}}}$ is given by the
submodular function

$f_{\smash{\raisebox{-1.42271pt}{$\mathrel{\mathop{\smile}\limits^{\vbox
to0.42192pt{\kern-2.0pt\hbox{$\scriptstyle
I$}\vss}}}$}}}(S)\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}-\llbracket
I\subseteq S\rrbracket.$

Their sum

$f_{\asymp}(S)=\sum_{I\text{ interval of
}[n]}f_{\smash{\raisebox{1.42271pt}{$\mathrel{\mathop{\frown}\limits_{\vbox
to0.0pt{\kern-7.0pt\hbox{$\scriptstyle
I$}\vss}}}$}}}(S)+f_{\smash{\raisebox{-1.42271pt}{$\mathrel{\mathop{\smile}\limits^{\vbox
to0.42192pt{\kern-2.0pt\hbox{$\scriptstyle I$}\vss}}}$}}}(S)$

is therefore exactly the number of intervals of $I$ that intersect $S$ but are
not contained in $S$, hence the number of intervals contained neither in $S$
nor in its complement. ∎

This proves the second part of Theorem 2.

###  3.6. Loday coordinates of weak rectangulotopes

For every weak rectangulation $R$, we wish to give the coordinates of a point
${\boldsymbol{p}}(R)\in\mathbb{R}^{n}$ such that $\mathds{WR}(n)$ is the
convex hull of the points ${\boldsymbol{p}}(R)$ for all weak rectangulations
$R$ of size $n$. Recall that in a Minkowski sum of polytopes, the vertex that
is extremal in a generic direction is the sum of the vertices of the summands
that are extremal in this direction. We therefore need to understand which
vertices of the translates of the shard polytopes defined in Lemmas 6 and 7
are extremal for a direction given by a permutation.

######  Lemma 10.

Let $\sigma\in\mathfrak{S}_{n}$ and $I$ be an interval of $[n]$ of size at
least $2$. The unique vertex of the up shard polytope
$\mathds{SP}(\smash{\raisebox{1.42271pt}{$\mathrel{\mathop{\frown}\limits_{\vbox
to0.0pt{\kern-7.0pt\hbox{$\scriptstyle I$}\vss}}}$}})$ (resp. down shard
polytope
$\mathds{SP}(\smash{\raisebox{-1.42271pt}{$\mathrel{\mathop{\smile}\limits^{\vbox
to0.60275pt{\kern-2.0pt\hbox{$\scriptstyle I$}\vss}}}$}})$) that is extreme
with respect to the direction $\sigma^{-1}$ is ${\boldsymbol{e}}_{i}$ (resp.
$-{\boldsymbol{e}}_{i}$), where $i$ is the maximum (resp. the minimum) of
$\sigma^{-1}$ in $I$.

Note that this extremal vertex should only depend on the weak rectangulation
congruence class of $\sigma$. This, in passing, gives us alternative
characterizations of the sylvester congruence $\frown$, the anti-sylvester
congruence $\smile$, and the weak rectangulation congruence $\asymp$. We have
$\sigma\frown\tau$ if and only if $\arg\max_{j\in
I}\sigma^{-1}_{j}=\arg\max_{j\in I}\tau^{-1}_{j}$ for any interval $I$ of
$[n]$. Similarly, $\sigma\smile\tau$ if and only if $\arg\min_{j\in
I}\sigma^{-1}_{j}=\arg\min_{j\in I}\tau^{-1}_{j}$ for any interval $I$ of
$[n]$. Finally, $\sigma\asymp\tau$ if both conditions hold.

The proof of the following lemma actually follows from Loday’s realization in
Theorem 1. For the sake of completeness, and because we will reuse the same
reasoning in Section 4, we give an elementary proof.

######  Lemma 11.

Let $R$ be a rectangulation of size $n$, with target tree $T$, and let
${\boldsymbol{p}}(R)$ the vertex of $\mathds{WR}(n)$ associated with $R$.
Given $i\in[n]$, the number of up arcs $\mathrel{\mathop{\frown}\limits_{\vbox
to0.0pt{\kern-7.0pt\hbox{$\scriptstyle I$}\vss}}}$ such that
${\boldsymbol{e}}_{i}$ is the extremal vertex of
$\mathds{SP}(\smash{\raisebox{1.42271pt}{$\mathrel{\mathop{\frown}\limits_{\vbox
to0.0pt{\kern-7.0pt\hbox{$\scriptstyle I$}\vss}}}$}})$ contributing to
${\boldsymbol{p}}(R)$ is

$\smash{\overset{\frown}{w}}_{i}=h^{T}_{i}\cdot v^{T}_{i},$

where $h^{T}_{i}$ and $v^{T}_{i}$ denote respectively the number of leaves in
the horizontal and vertical subtrees of $i$ in the tree $T$.

###### Proof.

Let $\sigma$ be any permutation in $\mathcal{L}(\prec_{w}^{R})$. From Lemma
10, for an $i\in[n]$, a shard polytope
$\mathds{SP}(\smash{\raisebox{1.42271pt}{$\mathrel{\mathop{\frown}\limits_{\vbox
to0.0pt{\kern-7.0pt\hbox{$\scriptstyle I$}\vss}}}$}})$ contributes to
${\boldsymbol{e}}_{i}$ if and only if $i$ is the index of the maximum of
$\sigma^{-1}$ in $I$. We claim that the number of intervals $I$ satisfying
this condition is the given product.

We first show that the number of choices for the left endpoint of $I$ is equal
to the number $h^{T}_{i}$ of leaves in the horizontal subtree of $i$ in $T$.
Each such leaf determines a left endpoint for $I$, defined as the node of the
tree that follows it in an inorder traversal. Any such node $\ell$ either lies
in the horizontal subtree of $i$, or is $i$ itself. Since the weak poset
extends the order induced by $T$, we have that either $\ell=i$ or
$\ell\prec_{s}^{R}i$, hence $\sigma^{-1}_{\ell}\leq\sigma^{-1}_{i}$.
Therefore, each such choice of left endpoint for $I$ does not contradict the
fact that $i$ is the index of the maximum of $\sigma^{-1}$ in $I$. Now
consider the leaf of $T$ that is immediately left of the leftmost leaf of the
horizontal subtree of $i$. This leaf is associated with the node $\ell$ that
comes next in inorder traversal, which must be an ancestor of $i$ in $T$.
Therefore, we must have $\ell\succ_{s}i$, and
$\sigma^{-1}_{\ell}>\sigma^{-1}_{i}$, and we cannot extend $I$ past this index
on the left. This shows that there are exactly $h^{T}_{i}$ choices for the
choice of the left endpoint of $I$. A symmetric argument shows that there are
exactly $v^{T}_{i}$ choices for the right endpoint of $I$. The combined number
of choices is thus the product $h^{T}_{i}\cdot v^{T}_{i}$. ∎

A symmetric analogue of Lemma 11 holds for down shard polytopes, where the
product contributes to $-{\boldsymbol{e}}_{i}$ instead of
${\boldsymbol{e}}_{i}$, and we consider the tree $S(R)$ instead of the tree
$T(R)$. This concludes the proof of Theorem 2.

##  4\. Strong rectangulotopes

This section is devoted to strong rectangulations and the proof of Theorem 3.

###  4.1. The strong poset

Given a rectangulation $R$, we define the strong poset $([n],\prec_{s}^{R})$
of $R$ by considering two relations on $[n]$ [ACFF24]:

  1. (1)

The adjacency poset $([n],\lhd)$ of $R$, defined by considering the adjacency
graph of the rectangles of $R$ (identified by their inorder labels in $[n]$),
orienting its edges from left to right and from bottom to top, and taking the
transitive closure of this directed acyclic graph.

  2. (2)

The special relation $([n],\LHD)$ of $R$, in which $i\LHD j$ if the two
rectangles $r_{i}$ and $r_{j}$ with respective inorder labels $i$ and $j$ are
such that

    1. (i)

either the right side of $r_{j}$ and the left side of $r_{i}$ lie on the same
vertical segment, and the bottom–right corner of $r_{j}$ is above the top–left
corner of $r_{i}$,

    2. (ii)

or the top side of $r_{j}$ and the bottom side of rectangle $r_{i}$ lie on the
same horizontal segment, and the top–left corner of $r_{j}$ lies on the right
of the bottom–right corner of $r_{i}$.

The strong poset is the transitive closure of the union of the two relations
$\lhd$ and $\LHD$. See Figure 13. The strong poset is a two-dimensional
lattice, whose minimum is the root of $S(R)$ and whose maximum is the root of
$T(R)$. The following statement will be used later.

Figure 13. The adjacency poset (left) and the strong poset (right) of the
rectangulation of Figure 8. Example from [ACFF24].

######  Lemma 12.

For any rectangulation $R$, its strong poset $([n],\prec_{s}^{R})$ is an
extension of its weak poset $([n],\prec_{w}^{R})$.

###### Proof.

Clearly, the strong poset is an extension of the adjacency poset $([n],\lhd)$
of $R$, since it is obtained by adding pairs from the special relation
$([n],\LHD)$. It remains to observe that the adjacency poset of $R$ is an
extension of the weak poset of $R$ (compare for instance Figure 12 (left) and
Figure 13 (left)). For this, we consider a diagonal representative $D$ of the
weak equivalence class of $R$, and recall that the weak poset of $R$ is the
adjacency poset of $D$. By definition, $R$ can be obtained from $D$ by a
sequence of wall slides. Each wall slide in this sequence consists of either a
horizontal segment being pulled down past another horizontal segment on its
right, or a vertical segment being pushed right past another vertical segment
below it. (These are the flips described in Figure 7(c), performed in bottom
to top order on the figure.) Note that each of these wall slides can only add
new pairs in the adjacency poset, hence the adjacency poset of $R$ is always
an extension of that of $D$. ∎

###  4.2. The strong rectangulation congruence

We consider the set $\mathcal{L}(\prec_{s}^{R})$ of linear extensions of the
strong poset $\prec_{s}^{R}$:

$\mathcal{L}(\prec_{s}^{R})\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\big{\\{}\sigma\in\mathfrak{S}_{n}\;\big{|}\;i\prec_{s}^{R}j\Rightarrow\sigma^{-1}_{i}<\sigma^{-1}_{j}\big{\\}}.$

N. Reading introduced 2-clumped permutations [Rea12], defined as the
permutations avoiding the vincular patterns $24\underline{51}3$,
$42\underline{51}3$, $3\underline{51}24$, and $3\underline{51}42$. The
co-2-clumped permutations are defined similarly, as permutations avoiding the
mirror images of these four patterns. These two permutation families are
equinumerous, see [OEI10, A342141]. Reading showed that 2-clumped permutations
are in bijection with strong rectangulations.

######  Theorem 13 ([Rea12, ACFF24]).

The subsets $\mathcal{L}(\prec_{s}^{R})$ of $\mathfrak{S}_{n}$, for all
rectangulations $R$ of size $n$, are equivalence classes of a congruence
relation $\mathbin{\smash{\begin{smallmatrix}\backsim\\\\[-8.5359pt]
\sim\end{smallmatrix}}}$ on the weak Bruhat order on $\mathfrak{S}_{n}$.
Furthermore:

  * •

the congruence classes are one-to-one with strong rectangulations,

  * •

the minimal elements of the congruence classes are the 2-clumped permutations,

  * •

the maximal elements of the congruence classes are the co-2-clumped
permutations.

We call the congruence
$\mathbin{\smash{\begin{smallmatrix}\backsim\\\\[-8.5359pt]
\sim\end{smallmatrix}}}$ the strong rectangulation congruence. The strong
rectangulotope $\mathds{SR}(n)$ is the quotientope of the strong
rectangulation congruence
${\mathbin{\smash{\begin{smallmatrix}\backsim\\\\[-8.5359pt]
\sim\end{smallmatrix}}}}$.

Similarly to the weak case, the quotient fan
$\mathcal{F}_{\mathbin{\smash{\begin{smallmatrix}\backsim\\\\[-8.5359pt]
\sim\end{smallmatrix}}}}$ has a maximal cone $\mathds{C}_{s}^{R}$ for each
strong rectangulation $R$ of size $n$. This cone is given by
$\mathds{C}_{s}^{R}=\left\\{{\boldsymbol{x}}\in\mathbb{R}^{n}\;\middle|\;x_{i}\leq
x_{j}\text{ if }i\prec_{s}^{R}j\right\\}$. Note that there is a bijection
between the facets of $\mathds{C}_{s}^{R}$, the cover relations of
$\prec_{s}^{R}$, and the feasible flips in $R$.

###  4.3. Yin and yang arcs

The arc ideal of the weak rectangulation congruence was already considered in
[Rea15, Exm. 4.11].

######  Lemma 14 ([Rea15, Exm. 4.11]).

The strong rectangulation congruence
$\mathbin{\smash{\begin{smallmatrix}\backsim\\\\[-8.5359pt]
\sim\end{smallmatrix}}}$ on $\mathfrak{S}_{n}$ is defined by the arc ideal
composed of arcs that cross the horizontal line at most once.

###### Proof.

We consider the forbidden vincular patterns $24\underline{51}3$,
$42\underline{51}3$, $3\underline{51}24$, and $3\underline{51}42$ that define
the 2-clumped permutations, the minimal elements of each congruence class of
$\mathbin{\smash{\begin{smallmatrix}\backsim\\\\[-8.5359pt]
\sim\end{smallmatrix}}}$. We observe that every occurrence of a pattern in a
permutation corresponds to an occurrence of an arc that cross the horizontal
line at least twice in the arc diagram of the permutation. The 2-clumped
permutations are therefore the permutations whose arc diagrams are composed
only of arcs that cross the horizontal line at most once. ∎

We classify these arcs into two families, depending on whether the arcs do not
cross the horizontal line from below or from above. For two consecutive
intervals $I$ and $J$ of $[n]$, the yin arc
$\mathrel{\mathop{\frown}\limits_{\vbox to0.0pt{\kern-7.0pt\hbox{$\scriptstyle
I$}\vss}}}$$\mathrel{\mathop{\smile}\limits^{\vbox
to0.60275pt{\kern-2.0pt\hbox{$\scriptstyle J$}\vss}}}$ (resp. yang arc
$\mathrel{\mathop{\smile}\limits^{\vbox
to0.60275pt{\kern-2.0pt\hbox{$\scriptstyle
I$}\vss}}}$$\mathrel{\mathop{\frown}\limits_{\vbox
to0.0pt{\kern-7.0pt\hbox{$\scriptstyle J$}\vss}}}$) is the arc starts at
$\min(I)$ and ends at $\max(J)$, and goes above (resp. below) the remaining
elements of $I$ and below (resp. above) the remaining elements of $J$, that
is,

$\mathrel{\mathop{\frown}\limits_{\vbox to0.0pt{\kern-7.0pt\hbox{$\scriptstyle
I$}\vss}}}$$\mathrel{\mathop{\smile}\limits^{\vbox
to0.60275pt{\kern-2.0pt\hbox{$\scriptstyle J$}\vss}}}$
$\displaystyle\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\big{(}\min(I),\max(J),I\smallsetminus\\{\min(I)\\},J\smallsetminus\\{\max(J)\\}\big{)}$
and$\mathrel{\mathop{\smile}\limits^{\vbox
to0.60275pt{\kern-2.0pt\hbox{$\scriptstyle
I$}\vss}}}$$\mathrel{\mathop{\frown}\limits_{\vbox
to0.0pt{\kern-7.0pt\hbox{$\scriptstyle J$}\vss}}}$
$\displaystyle\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\big{(}\min(I),\max(J),J\smallsetminus\\{\max(J)\\},I\smallsetminus\\{\min(I)\\}\big{)}.$

Note that all up arcs and down arcs are both yin arcs and yang arcs.

Note that the yin (resp. yang) arcs alone form an arc ideal, and we call yin
(resp. yang) congruence the corresponding congruence of the weak order. It can
be checked that the equivalence classes of these congruences are counted by
semi-Baxter permutations, defined as permutations avoiding $2\underline{41}3$,
hence only one of the two forbidden Baxter patterns. These equivalence classes
are in turn in bijection with rectangulations that avoid one of the two
patterns defining diagonal rectangulations, see [ACFF24]. The strong
rectangulation congruence is the intersection of the yin and yang congruences.

###  4.4. Shard polytopes of yin and yang arcs

From the results of Section 2.4, the quotientope is realized by a Minkowski
sum of the shard polytopes of the yin arcs and the yang arcs. These shard
polytopes can be described as follows.

######  Lemma 15.

The yin shard polytope
$\mathds{SP}(\smash{\raisebox{1.42271pt}{$\mathrel{\mathop{\frown}\limits_{\vbox
to0.0pt{\kern-7.0pt\hbox{$\scriptstyle
I$}\vss}}}$}\raisebox{-0.85355pt}{$\mathrel{\mathop{\smile}\limits^{\vbox
to0.60275pt{\kern-2.0pt\hbox{$\scriptstyle J$}\vss}}}$}})$ is
$\operatorname{conv}\\{{\boldsymbol{0}}\\}\cup\left\\{{\boldsymbol{e}}_{i}-{\boldsymbol{e}}_{j}\;\middle|\;i\in
I,\;j\in J\right\\}$.

######  Lemma 16.

The yang shard polytope
$\mathds{SP}(\smash{\raisebox{-0.85355pt}{$\mathrel{\mathop{\smile}\limits^{\vbox
to0.60275pt{\kern-2.0pt\hbox{$\scriptstyle
I$}\vss}}}$}\raisebox{1.42271pt}{$\mathrel{\mathop{\frown}\limits_{\vbox
to0.0pt{\kern-7.0pt\hbox{$\scriptstyle J$}\vss}}}$}})$ is a translate of
$\operatorname{conv}\\{{\boldsymbol{0}}\\}\cup\left\\{{\boldsymbol{e}}_{j}-{\boldsymbol{e}}_{i}\;\middle|\;i\in
I,\;j\in J\right\\}$.

We refer to Figure 11 for examples of yin and yang shard polytopes.

######  Proposition 17.

The strong rectangulotope $\mathds{SR}(n)$ is realized by the Minkowski sum of
all yin and yang shard polytopes.

Since the combinatorial type of a Minkowski sum is invariant to translation of
the summands, we can use the polytopes defined in Lemmas 15 and 16 as a
definition of the yin and yang shard polytopes. Also note that since the up
and down shard polytopes are, up to a translation, both yin and yang, each up
and down shard polytope is summed twice (hence all basic shard polytopes are
summed four times) in the proposed realization. This, again, does not change
the combinatorial type of the polytope.

Proposition 17 gives us an alternative description of $\mathds{SR}(n)$ as the
sum of two opposite quotientopes corresponding to the yin and yang
congruences.

###  4.5. Submodular functions of strong rectangulotopes

From the results of Section 2.4, the submodular function corresponding to our
realization of $\mathds{SR}(n)$ can be obtained as before by summing the
functions defining the yin and yang shard polytopes in Lemmas 15 and 16. Note
again that all rays of the braid fan are preserved in the fan of the strong
rectangulotope, hence our submodular description of the strong rectangulotope
is an irredundant facet description.

######  Lemma 18.

The strong rectangulotope $\mathds{SR}(n)$ is realized by the following
submodular function:

$f_{\mathbin{\smash{\begin{smallmatrix}\backsim\\\\[-8.5359pt]
\sim\end{smallmatrix}}}}(S)\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\\#\big{\\{}I,J\;\big{|}\;I\not\subseteq[n]\smallsetminus
S\text{ and }J\not\subseteq
S\big{\\}}+\\#\big{\\{}I,J\;\big{|}\;I\not\subseteq S\text{ and
}J\not\subseteq[n]\smallsetminus S\big{\\}},$

where $I,J$ are pairs of nonempty consecutive intervals of $[n]$.

###### Proof.

The submodular function defining the realization of $\mathds{WR}(n)$ is the
sum of the submodular functions defining the yin and yang shard polytopes in
Lemmas 15 and 16. The shard polytope
$\mathds{SP}(\smash{\raisebox{1.42271pt}{$\mathrel{\mathop{\frown}\limits_{\vbox
to0.0pt{\kern-7.0pt\hbox{$\scriptstyle
I$}\vss}}}$}\raisebox{-0.85355pt}{$\mathrel{\mathop{\smile}\limits^{\vbox
to0.60275pt{\kern-2.0pt\hbox{$\scriptstyle J$}\vss}}}$}})$ of a yin arc
$\mathrel{\mathop{\frown}\limits_{\vbox to0.0pt{\kern-7.0pt\hbox{$\scriptstyle
I$}\vss}}}$$\mathrel{\mathop{\smile}\limits^{\vbox
to0.60275pt{\kern-2.0pt\hbox{$\scriptstyle J$}\vss}}}$ is given by the
submodular function

$f_{\smash{\raisebox{1.42271pt}{$\mathrel{\mathop{\frown}\limits_{\vbox
to0.0pt{\kern-7.0pt\hbox{$\scriptstyle
I$}\vss}}}$}\raisebox{-0.85355pt}{$\mathrel{\mathop{\smile}\limits^{\vbox
to0.42192pt{\kern-2.0pt\hbox{$\scriptstyle
J$}\vss}}}$}}}(S)\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\llbracket
I\not\subseteq[n]\smallsetminus S\text{ and }J\not\subseteq S\rrbracket.$

(Recall that $\llbracket\varphi\rrbracket$ is equal to 1 if $\varphi$ holds,
and $0$ otherwise.) Similarly, the shard polytope
$\mathds{SP}(\smash{\raisebox{-0.85355pt}{$\mathrel{\mathop{\smile}\limits^{\vbox
to0.60275pt{\kern-2.0pt\hbox{$\scriptstyle
I$}\vss}}}$}\raisebox{1.42271pt}{$\mathrel{\mathop{\frown}\limits_{\vbox
to0.0pt{\kern-7.0pt\hbox{$\scriptstyle J$}\vss}}}$}})$ of a yang arc
$\mathrel{\mathop{\smile}\limits^{\vbox
to0.60275pt{\kern-2.0pt\hbox{$\scriptstyle
I$}\vss}}}$$\mathrel{\mathop{\frown}\limits_{\vbox
to0.0pt{\kern-7.0pt\hbox{$\scriptstyle J$}\vss}}}$ is given by the submodular
function

$f_{\smash{\raisebox{-0.85355pt}{$\mathrel{\mathop{\smile}\limits^{\vbox
to0.42192pt{\kern-2.0pt\hbox{$\scriptstyle
I$}\vss}}}$}\raisebox{1.42271pt}{$\mathrel{\mathop{\frown}\limits_{\vbox
to0.0pt{\kern-7.0pt\hbox{$\scriptstyle
J$}\vss}}}$}}}(S)\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\llbracket
I\not\subseteq S\text{ and }J\not\subseteq[n]\smallsetminus S\rrbracket.$

Their sum

$f_{\mathbin{\smash{\begin{smallmatrix}\backsim\\\\[-8.5359pt]
\sim\end{smallmatrix}}}}(S)\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\sum_{I,J}f_{\smash{\raisebox{1.42271pt}{$\mathrel{\mathop{\frown}\limits_{\vbox
to0.0pt{\kern-7.0pt\hbox{$\scriptstyle
I$}\vss}}}$}\raisebox{-0.85355pt}{$\mathrel{\mathop{\smile}\limits^{\vbox
to0.42192pt{\kern-2.0pt\hbox{$\scriptstyle
J$}\vss}}}$}}}(S)+f_{\smash{\raisebox{-0.85355pt}{$\mathrel{\mathop{\smile}\limits^{\vbox
to0.42192pt{\kern-2.0pt\hbox{$\scriptstyle
I$}\vss}}}$}\raisebox{1.42271pt}{$\mathrel{\mathop{\frown}\limits_{\vbox
to0.0pt{\kern-7.0pt\hbox{$\scriptstyle J$}\vss}}}$}}}(S)$

is therefore as claimed. ∎

This proves the second part of Theorem 3.

###  4.6. Loday coordinates of strong rectangulotopes

As in Section 3.6, we need to understand which vertices of the translates of
the yin and yang shard polytopes defined in Lemmas 15 and 16 are extremal for
a direction given by a permutation.

######  Lemma 19.

Let $\sigma\in\mathfrak{S}_{n}$, let $I$ and $J$ be two consecutive intervals
of $[n]$, and let
$i\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\arg\max_{k\in
I}\sigma^{-1}_{k}$ and
$j\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\arg\min_{k\in
J}\sigma^{-1}_{k}$ (resp.
$i\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\arg\min_{k\in
I}\sigma^{-1}_{k}$ and
$j\mbox{\,\raisebox{0.86108pt}{\scriptsize$\mathrm{:}$}$=$\,}\arg\max_{k\in
J}\sigma^{-1}_{k}$). The unique vertex of the yin (resp. yang) shard polytope
$\mathds{SP}(\smash{\raisebox{1.42271pt}{$\mathrel{\mathop{\frown}\limits_{\vbox
to0.0pt{\kern-7.0pt\hbox{$\scriptstyle
I$}\vss}}}$}\raisebox{-0.85355pt}{$\mathrel{\mathop{\smile}\limits^{\vbox
to0.60275pt{\kern-2.0pt\hbox{$\scriptstyle J$}\vss}}}$}})$ (resp.
$\mathds{SP}(\smash{\raisebox{-0.85355pt}{$\mathrel{\mathop{\smile}\limits^{\vbox
to0.60275pt{\kern-2.0pt\hbox{$\scriptstyle
I$}\vss}}}$}\raisebox{1.42271pt}{$\mathrel{\mathop{\frown}\limits_{\vbox
to0.0pt{\kern-7.0pt\hbox{$\scriptstyle J$}\vss}}}$}})$) that is extreme with
respect to the direction $\sigma^{-1}$ is
${\boldsymbol{e}}_{i}-{\boldsymbol{e}}_{j}$ (resp.
${\boldsymbol{e}}_{j}-{\boldsymbol{e}}_{i}$) if
$\sigma^{-1}_{i}>\sigma^{-1}_{j}$ (resp. $\sigma^{-1}_{i}<\sigma^{-1}_{j}$),
and ${\boldsymbol{0}}$ otherwise.

Note again that by definition, this extremal vertex should only depend on the
strong congruence class of $\sigma$. This, again, gives us alternative
characterizations of the yin congruence $\sim$, the yang congruence
$\backsim$, and the strong rectangulation congruence
$\mathbin{\smash{\begin{smallmatrix}\backsim\\\\[-8.5359pt]
\sim\end{smallmatrix}}}$. We have $\sigma\sim\tau$ if and only if for any pair
of consecutive intervals $I$ and $J$ of $[n]$, $\arg\max_{k\in
I}\sigma^{-1}_{k}=\arg\max_{k\in I}\tau^{-1}_{k}$ and $\arg\min_{k\in
J}\sigma^{-1}_{k}=\arg\min_{k\in J}\tau^{-1}_{k}$ (that is, if
$\sigma\asymp\tau$), and, if we let $i$ and $j$ be defined as in Lemma 19 as
the indices of the maximum in $I$ and the minimum in $J$,
$\sigma^{-1}_{i}>\sigma^{-1}_{j}\Leftrightarrow\tau^{-1}_{i}>\tau^{-1}_{j}$. A
similar statement holds for the yang congruence $\backsim$, by exchanging
$\min$ and $\max$. Finally,
$\sigma\mathbin{\smash{\begin{smallmatrix}\backsim\\\\[-8.5359pt]
\sim\end{smallmatrix}}}\tau$ if both sets of conditions hold.

######  Lemma 20.

Let $R$ be a strong rectangulation of size $n$, let $S$ and $T$ be its source
and target trees, let $([n],\prec_{s}^{R})$ be its strong poset, and let
${\boldsymbol{p}}(R)$ be the vertex of $\mathds{SR}(n)$ corresponding to $R$.
Given a pair $i,j\in[n]$ with $i<j$, the number of yin arcs $\alpha$ such that
${\boldsymbol{e}}_{i}-{\boldsymbol{e}}_{j}$ is the extremal vertex of
$\mathds{SP}(\alpha)$ contributing to ${\boldsymbol{p}}(R)$ is

$h^{T}_{i}\cdot cv^{T,S}_{i,j}\cdot h^{S}_{j}$

if $i\succ_{s}j$, and $0$ otherwise, where

  * •

$h^{T}_{i}$ denotes the number of leaves in the horizontal and vertical
subtrees of $i$ in $T$,

  * •

$cv^{T,S}_{i,j}$ denotes the number of common leaves of the vertical subtree
of $i$ in $T$ and the vertical subtree of $j$ in $S$.

###### Proof.

Let $\sigma$ be any permutation in $\mathcal{L}(\prec_{s}^{R})$. From Lemma
19, for a pair $i<j\in[n]$, there exists a yin arc $\alpha$ whose shard
polytope $\mathds{SP}(\alpha)$ contributes to
${\boldsymbol{e}}_{i}-{\boldsymbol{e}}_{j}$ if and only if
$\sigma^{-1}_{i}>\sigma^{-1}_{j}$, hence if $i\succ_{s}j$. Provided this
holds, the set of yin arcs $\alpha$ such that $\mathds{SP}(\alpha)$
contributes to ${\boldsymbol{e}}_{i}-{\boldsymbol{e}}_{j}$ are defined by
pairs of contiguous intervals $I,J$ of $[n]$ with $i\in I$, $j\in J$, such
that $i$ is the index of the maximum of $\sigma^{-1}$ in $I$, and $j$ is the
index of the maximum of $\sigma^{-1}$ in $J$. We claim that the number of
choices of the three endpoints defining such a pair of intervals $I$ and $J$
is the given product.

We first show that the number of choices for the left endpoint of $I$ is equal
to the number $h^{T}_{i}$ of leaves in the horizontal subtree of $i$ in $T$.
The proof of this follows the exact same lines as that of Lemma 11. Each leaf
determines a left endpoint for $I$, defined as the next node in an inorder
traversal. Any such node $\ell$ either lies in the horizontal subtree of $i$,
or is $i$ itself. Since from Lemma 12 the strong poset extends the order
induced by $T$, we have that either $\ell=i$ or $\ell\prec_{s}^{R}i$, hence
$\sigma^{-1}_{\ell}\leq\sigma^{-1}_{i}$. Therefore, each such choice of left
endpoint for $I$ does not contradict the fact that $i$ is the index of the
maximum of $\sigma^{-1}$ in $I$. Now consider the leaf of $T$ that is
immediately left of the leftmost leaf of the horizontal subtree of $i$. This
leaf is associated with the node $\ell$ that comes next in inorder traversal,
which must be an ancestor of $i$ in $T$. Therefore, we must have
$\ell\succ_{s}i$, and $\sigma^{-1}_{\ell}>\sigma^{-1}_{i}$, and we cannot
extend $I$ past this index on the left. This shows that there are exactly
$h^{T}_{i}$ choices, and not more, for the choice of the left endpoint of $I$.

The rest of the formula comes by symmetric arguments. First, the right
endpoint of $I$ can only be chosen among the leaves of the vertical subtree of
$T$ rooted at $i$. Then the same reasoning holds for the two endpoints of $J$,
replacing $i$ by $j$ and $T$ by $S$. Finally, since the right endpoint of $I$
and the left endpoint of $J$ must be consecutive, the selected leaves must
correspond to the same pair of successive indices of $[n]$. These leaves are
exactly the common leaves defined previously. ∎

Lemma 20 essentially gives us the coefficient
$\smash{\overset{\sim}{w}}^{R}_{i,j}$ in Theorem 3, except that the condition
$\neg\;{}^{i}\\!\\!\\!\raisebox{0.85355pt}{\smash{\raisebox{-7.11317pt}{\includegraphics[scale={.5}]{verticalPattern}}}}\\!\\!\\!{}_{j}$
is replaced by $i\succ_{s}j$. Recall that
${}^{i}\\!\\!\\!\raisebox{0.85355pt}{\smash{\raisebox{-7.11317pt}{\includegraphics[scale={.5}]{verticalPattern}}}}\\!\\!\\!{}_{j}$
denotes the situation where the rectangles $r_{i}$ and $r_{j}$ of inorder
labels $i$ and $j$ share a vertical segment, $r_{i}$ is on the left of
$r_{j}$, and the bottom edge of $r_{i}$ is lower than the top edge of $r_{j}$.
Our aim is to provide a formula for the coordinates of the vertices of the
strong rectangulotope that does not involve the computation of the strong
poset or one of its linear extensions. For that purpose, we prove that for
every pair $i<j\in[n]$ such that $i\prec_{s}^{R}j$, which do not have any
associated yin arc, we have either
${}^{i}\\!\\!\\!\raisebox{0.85355pt}{\smash{\raisebox{-7.11317pt}{\includegraphics[scale={.5}]{verticalPattern}}}}\\!\\!\\!{}_{j}$
or $cv^{T,S}_{i,j}=0$ (hence the product in Lemma 20 is $0$ as well and adding
it does not harm the result).

######  Lemma 21.

Let $R$ be a rectangulation of size $n$, with source and target trees $S$ and
$T$, and strong order $\prec_{s}^{R}$. Given a pair $i,j\in[n]$ such that
$i<j$ and $i\prec_{s}^{R}j$, we have

$cv^{T,S}_{i,j}>0\quad\Longrightarrow\quad{}^{i}\\!\\!\\!\raisebox{0.85355pt}{\smash{\raisebox{-7.11317pt}{\includegraphics[scale={.5}]{verticalPattern}}}}\\!\\!\\!{}_{j}.$

###### Proof.

Consider the two rectangles $r_{i}$ and $r_{j}$ with inorder labels $i$ and
$j$ in $R$. We first observe that the source vertex $s(r_{j})$ is not
contained in the interior of the lower left quadrant of origin $t(r_{i})$.
Indeed, if we assume otherwise, then the line segment from $s(r_{j})$ to
$t(r_{i})$ has positive slope, which implies that $j\lhd i$, which in turn
implies $j\prec_{s}^{R}i$, contradicting our hypothesis. We also observe that
since $i<j$, by definition of the inorder on $S$ and $T$, the rectangle
$r_{j}$ must be below or on the right of $r_{i}$. Combining those two
observations, we conclude that the right edge of $r_{i}$ cannot be on the
right of the left edge of $r_{j}$.

Therefore, there can only be one segment which may contain a leaf to the
vertical subtree of $i$ in $T$ and a leaf of the vertical subtree of $j$ in
$S$, which is the vertical segment supporting the right edge of $r_{i}$ and
the left edge of $r_{j}$. Let us assume that this segment is shared by those
two edges. If the bottom edge of $r_{i}$ is higher than the top edge of
$r_{j}$, we must have $j\LHD i$, which implies $j\prec_{s}^{R}i$,
contradicting our hypothesis again. Thus the bottom edge of $r_{i}$ is lower
than the top edge of $r_{j}$, and
${}^{i}\\!\\!\\!\raisebox{0.85355pt}{\smash{\raisebox{-7.11317pt}{\includegraphics[scale={.5}]{verticalPattern}}}}\\!\\!\\!{}_{j}$,
as claimed. ∎

We omit the proofs of the analogues of Lemma 20 and Lemma 21 for the case of
the yang arcs, which use completely symmetric arguments. This concludes the
proof of Theorem 3.

## References

  * [AA23] Marcelo Aguiar and Federico Ardila.  Hopf monoids and generalized permutahedra.  Mem. Amer. Math. Soc., 289(1437):vi+119, 2023.
  * [AB24] Andrei Asinowski and Cyril Banderier.  From geometry to generating functions: rectangulations and permutations.  Preprint, arXiv:2401.05558, 2024.
  * [ABBM+13] Andrei Asinowski, Gill Barequet, Mireille Bousquet-Mélou, Toufik Mansour, and Ron Y. Pinter.  Orders induced by segments in floorplans and (2-14-3, 3-41-2)-avoiding permutations.  Electron. J. Combin., 20(2):Paper 35, 43, 2013.
  * [Abe30] Michio Abe.  Covering the square by squares without overlapping.  J. Japan Math. Phys., 4(4):359–366, 1930.  (in Japanese).
  * [Abe32] Michio Abe.  On the problem to cover simply and without gap the inside of a square with a finite number of squares which are all different from one another.  Proc. Phys.-Math. Soc. Japan, 14:385–387, 1932.
  * [ABP06] Eyal Ackerman, Gill Barequet, and Ron Y. Pinter.  A bijection between permutations and floorplans, and its applications.  Discrete Appl. Math., 154(12):1674–1684, 2006.
  * [ACEP20] Federico Ardila, Federico Castillo, Christopher Eur, and Alexander Postnikov.  Coxeter submodular functions and deformations of Coxeter permutahedra.  Adv. Math., 365:107039, 36, 2020.
  * [ACFF24] Andrei Asinowski, Jean Cardinal, Stefan Felsner, and Éric Fusy.  Combinatorics of rectangulations: Old and new bijections.  Preprint, arXiv:2402.01483, 2024.
  * [APR21] Doriann Albertin, Vincent Pilaud, and Julian Ritter.  Removahedral congruences versus permutree congruences.  Electron. J. Combin., 28(4):Paper No. 4.8, 38, 2021.
  * [BB05] Anders Björner and Francesco Brenti.  Combinatorics of Coxeter groups, volume 231 of Graduate Texts in Mathematics.  Springer, New York, 2005.
  * [BSST40] R. L. Brooks, C. A. B. Smith, A. H. Stone, and W. T. Tutte.  The dissection of rectangles into squares.  Duke Math. J., 7:312–340, 1940.
  * [CFZ02] Frédéric Chapoton, Sergey Fomin, and Andrei Zelevinsky.  Polytopal realizations of generalized associahedra.  Canad. Math. Bull., 45(4):537–566, 2002.  Dedicated to Robert V. Moody.
  * [CGHK78] F. R. K. Chung, R. L. Graham, V. E. Hoggatt, Jr., and M. Kleiman.  The number of Baxter permutations.  J. Combin. Theory Ser. A, 24(3):382–394, 1978.
  * [CSS18] Jean Cardinal, Vera Sacristán, and Rodrigo I. Silveira.  A note on flips in diagonal rectangulations.  Discrete Math. Theor. Comput. Sci., 20(2):Paper No. 14, 22, 2018\.
  * [CSZ15] Cesar Ceballos, Francisco Santos, and Günter M. Ziegler.  Many non-equivalent realizations of the associahedron.  Combinatorica, 35(5):513–551, 2015.
  * [DG96] S. Dulucq and O. Guibert.  Stack words, standard tableaux and Baxter permutations.  Discrete Math., 157(1-3):91–106, 1996.  Proceedings of the 6th Conference on Formal Power Series and Algebraic Combinatorics (New Brunswick, NJ, 1994).
  * [FFNO11] Stefan Felsner, Éric Fusy, Marc Noy, and David Orden.  Bijections for Baxter families and related objects.  J. Combin. Theory Ser. A, 118(3):993–1020, 2011.
  * [FIT09] Ryo Fujimaki, Youhei Inoue, and Toshihiko Takahashi.  An asymptotic estimate of the numbers of rectangular drawings or floorplans.  In International Symposium on Circuits and Systems (ISCAS 2009), 24-17 May 2009, Taipei, Taiwan, pages 856–859. IEEE, 2009.
  * [FNS24] Éric Fusy, Erkan Narmanli, and Gilles Schaeffer.  On the enumeration of plane bipolar posets and transversal structures.  European J. Combin., 116:Paper No. 103870, 28, 2024.
  * [FT07] Ryo Fujimaki and Toshihiko Takahashi.  A surjective mapping from permutations to room-to-room floorplans.  IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 90-A(4):823–828, 2007.
  * [Gir12] Samuele Giraudo.  Algebraic and combinatorial structures on pairs of twin binary trees.  J. Algebra, 360:115–157, 2012.
  * [He14] Bryan Dawei He.  A simple optimal binary representation of mosaic floorplans and Baxter permutations.  Theoret. Comput. Sci., 532:40–50, 2014.
  * [HL07] Christophe Hohlweg and Carsten E. M. C. Lange.  Realizations of the associahedron and cyclohedron.  Discrete Comput. Geom., 37(4):517–543, 2007.
  * [HNT05] F. Hivert, J.-C. Novelli, and J.-Y. Thibon.  The algebra of binary search trees.  Theoret. Comput. Sci., 339(1):129–165, 2005.
  * [Hum90] James E. Humphreys.  Reflection groups and Coxeter groups, volume 29 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, 1990.
  * [ITF09] Youhei Inoue, Toshihiko Takahashi, and Ryo Fujimaki.  Counting rectangular drawings or floorplans in polynomial time.  IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 92-A(4):1115–1120, 2009.
  * [Lee89] Carl W. Lee.  The associahedron and triangulations of the $n$-gon.  European J. Combin., 10(6):551–560, 1989.
  * [Lod04] Jean-Louis Loday.  Realization of the Stasheff polytope.  Arch. Math. (Basel), 83(3):267–278, 2004.
  * [LR98] Jean-Louis Loday and María O. Ronco.  Hopf algebra of the planar binary trees.  Adv. Math., 139(2):293–309, 1998.
  * [LR12] Shirley Law and Nathan Reading.  The Hopf algebra of diagonal rectangulations.  J. Combin. Theory Ser. A, 119(3):788–824, 2012.
  * [Mal79] C. L. Mallows.  Baxter permutations rise again.  J. Combin. Theory Ser. A, 27(3):394–396, 1979.
  * [Mee17] Emily Meehan.  Posets and Hopf Algebras of Rectangulations.  PhD thesis, North Carolina State University, 2017.
  * [Mee19] Emily Meehan.  Baxter posets.  Electron. J. Combin., 26(3):Paper No. 3.33, 24, 2019.
  * [MHPS12] Folkert Müller-Hoissen, Jean Marcel Pallo, and Jim Stasheff, editors.  Associahedra, Tamari lattices and related structures, volume 299 of Progress in Mathematics.  Birkhäuser/Springer, Basel, 2012.  Tamari memorial Festschrift.
  * [MM23] Arturo Merino and Torsten Mütze.  Combinatorial generation via permutation languages. III. Rectangulations.  Discrete Comput. Geom., 70(1):51–122, 2023.
  * [OEI10] The On-Line Encyclopedia of Integer Sequences.  Published electronically at http://oeis.org, 2010.
  * [Pil18] Vincent Pilaud.  Brick polytopes, lattice quotients, and Hopf algebras.  J. Combin. Theory Ser. A, 155:418–457, 2018.
  * [Pil22] Vincent Pilaud.  Acyclic reorientation lattices and their lattice quotients.  Sém. Lothar. Combin., 86B:Art. 67, 12, 2022.
  * [Pos09] Alexander Postnikov.  Permutohedra, associahedra, and beyond.  Int. Math. Res. Not. IMRN, 2009(6):1026–1106, 2009.
  * [Pou14] Lionel Pournin.  The diameter of associahedra.  Adv. Math., 259:13–42, 2014.
  * [PP18] Vincent Pilaud and Viviane Pons.  Permutrees.  Algebr. Comb., 1(2):173–224, 2018.
  * [PPR23] Arnau Padrol, Vincent Pilaud, and Julian Ritter.  Shard polytopes.  Int. Math. Res. Not. IMRN, 2023(9):7686–7796, 2023.
  * [PRW08] Alex Postnikov, Victor Reiner, and Lauren Williams.  Faces of generalized permutohedra.  Doc. Math., 13:207–273, 2008.
  * [PS12] Vincent Pilaud and Francisco Santos.  The brick polytope of a sorting network.  European J. Combin., 33(4):632–662, 2012.
  * [PS15] Vincent Pilaud and Christian Stump.  Brick polytopes of spherical subword complexes and generalized associahedra.  Adv. Math., 276:1–61, 2015.
  * [PS19] Vincent Pilaud and Francisco Santos.  Quotientopes.  Bull. Lond. Math. Soc., 51(3):406–420, 2019.
  * [PSZ23] Vincent Pilaud, Francisco Santos, and Günter M. Ziegler.  Celebrating Loday’s associahedron.  Arch. Math. (Basel), 121(5-6):559–601, 2023.
  * [Rea05] Nathan Reading.  Lattice congruences, fans and Hopf algebras.  J. Combin. Theory Ser. A, 110(2):237–273, 2005.
  * [Rea12] Nathan Reading.  Generic rectangulations.  European J. Combin., 33(4):610–623, 2012.
  * [Rea15] Nathan Reading.  Noncrossing arc diagrams and canonical join representations.  SIAM J. Discrete Math., 29(2):736–750, 2015.
  * [Rea16a] N. Reading.  Finite Coxeter groups and the weak order.  In Lattice theory: special topics and applications. Vol. 2, pages 489–561. Birkhäuser/Springer, Cham, 2016.
  * [Rea16b] N. Reading.  Lattice theory of the poset of regions.  In Lattice theory: special topics and applications. Vol. 2, pages 399–487. Birkhäuser/Springer, Cham, 2016.
  * [SC03] Zion Cien Shen and Chris C. N. Chu.  Bounds on the number of slicing, mosaic, and general floorplans.  IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 22(10):1354–1361, 2003.
  * [Spr39] R. Sprague.  Beispiel einer Zerlegung des Quadrats in lauter verschiedene Quadrate.  Math. Z., 45:607–608, 1939.
  * [SS93] Steven Shnider and Shlomo Sternberg.  Quantum groups, volume II of Graduate Texts in Mathematical Physics.  International Press, Cambridge, MA, 1993.  From coalgebras to Drinfeld algebras, A guided tour.
  * [Sta63] James Dillon Stasheff.  Homotopy associativity of $H$-spaces. I, II.  Trans. Amer. Math. Soc., 108:293–312, 1963.  108 (1963), 275-292; ibid.
  * [STT88] Daniel D. Sleator, Robert E. Tarjan, and William P. Thurston.  Rotation distance, triangulations, and hyperbolic geometry.  J. Amer. Math. Soc., 1(3):647–681, 1988.
  * [Tam51] Dov Tamari.  Monoïdes préordonnés et chaînes de Malcev.  Université de Paris, Paris, 1951.  Thèse.
  * [Tam62] Dov Tamari.  The algebra of bracketings and their enumeration.  Nieuw Arch. Wisk. (3), 10:131–146, 1962.
  * [TF08] Toshihiko Takahashi and Ryo Fujimaki.  Fujimaki–Takahashi squeeze: Linear time construction of constraint graphs of floorplan for a given permutation.  IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 91-A(4):1071–1076, 2008.