# An exact characterization of saturation for permutation matrices

Benjamin Aram Berendsohn Institut für Informatik, Freie Universität Berlin,
<EMAIL_ADDRESS>Work supported by DFG grant KO 6140/1-1.

###### Abstract

A 0-1 matrix $M$ _contains_ a 0-1 matrix _pattern_ $P$ if we can obtain $P$
from $M$ by deleting rows and/or columns and turning arbitrary 1-entries into
0s. The saturation function $\mathrm{sat}(P,n)$ for a 0-1 matrix pattern $P$
indicates the minimum number of 1s in an $n\times n$ 0-1 matrix that does not
contain $P$, but changing any 0-entry into a 1-entry creates an occurrence of
$P$. Fulek and Keszegh recently showed that each pattern has a saturation
function either in $\mathcal{O}(1)$ or in $\Theta(n)$. We fully classify the
saturation functions of _permutation matrices_.

##  1 Introduction

In this paper, all matrices are 0-1 matrices. For cleaner presentation, we
write matrices with dots ($\begin{smallmatrix}\bullet\end{smallmatrix}$)
instead of 1s and spaces instead of 0s, for example:

$\displaystyle\left(\begin{smallmatrix}0&1&0\\\ 0&0&1\\\
1&0&0\end{smallmatrix}\right)=\left(\begin{smallmatrix}&\bullet&\\\
&&\bullet\\\ \bullet&&\end{smallmatrix}\right)$

In line with this notation, we call a row or column _empty_ if it only
contains 0s. Furthermore, we refer to changing an entry from 0 to 1 as
_adding_ a 1-entry, and to the reverse as _removing_ a 1-entry.

A _pattern_ is a matrix that is not all-zero. A matrix $M$ _contains_ a
pattern $P$ if we can obtain $P$ from $M$ by deleting rows and/or columns, and
removing arbitrary 1-entries. If $M$ does not contain $P$, we say $M$ _avoids_
$P$. Matrix pattern avoidance can be seen as a generalization of two other
well-known areas in extremal combinatorics. Pattern avoidance in permutations
(see, e.g., Vatter’s survey [Vat14]) corresponds to the case where both $M$
and $P$ are permutation matrices; and forbidden subgraphs in bipartite graphs
correspond to avoiding a pattern $P$ and all other patterns obtained from $P$
by permutation of rows and/or columns.111For this, we interpret the $M$ and
$P$ as adjacency matrices of bipartite graphs. There are also close
connections to the extremal theory of ordered graphs [PT06] and posets
[GNPV21].

A classical question in extremal graph theory is to determine the maximum
number of edges in an $n$-vertex graph avoiding a fixed pattern graph $H$. The
corresponding problem in forbidden submatrix theory is determining the maximum
_weight_ (number of 1s) of an $m\times n$ matrix avoiding the pattern $P$,
denoted by $\mathrm{ex}(P,m,n)$. We call $\mathrm{ex}(P,n)=\mathrm{ex}(P,n,n)$
the _extremal function_ of the pattern $P$. The study of the extremal function
originates in its applications to (computational) geometry [Mit87, Für90,
BG91]. A systematic study initiated by Füredi and Hajnal [FH92] has produced
numerous results (e.g. [Kla00, Kla01, MT04, Tar05, Kesz09, Ful09, Gen09,
Pet11a, Pet11b]), and further applications in the analysis of algorithms have
been discovered [Pet10, CGK+15].

Clearly, for non-trivial patterns, $\mathrm{ex}(P,n)$ is at least linear and
at most quadratic. Large classes of patterns with linear and quasi-linear
extremal functions have been identified [Kesz09, Pet11a]. On the other hand,
there are patterns with nearly quadratic extremal functions [ARSz99].

A natural counterpart to the extremal problem is the _saturation problem_. A
matrix $M$ is _saturating_ for a pattern $P$, or _$P$ -saturating_ if it
avoids $P$ and is maximal in this respect, i.e., turning any 0-entry of $M$
into a 1 creates an occurrence of $P$. Clearly, $\mathrm{ex}(P,m,n)$ can also
be defined as the maximum weight of an $m\times n$ matrix that is
$P$-saturating. The function $\mathrm{sat}(P,m,n)$ indicates the _minimum_
weight of an $m\times n$ matrix that is $P$-saturating. We focus on square
matrices and the _saturation function_
$\mathrm{sat}(P,n)=\mathrm{sat}(P,n,n)$.

The saturation problem for matrix patterns was first considered by Brualdi and
Cao [BC20] as a counterpart of saturation problems in graph theory.222We refer
to [FK20] for references to graph saturation results. Fulek and Keszegh [FK20]
started a systematic study. They proved that, perhaps surprisingly, every
pattern $P$ satisfies $\mathrm{sat}(P,n)\in\mathcal{O}(1)$ or
$\mathrm{sat}(P,n)\in\Theta(n)$, where the hidden constants depend on $P$.
This is in stark contrast to the extremal problem, where a wide range of
different orders of magnitude is attained by various patterns. Fulek and
Keszegh also present large classes of patterns with linear saturation
functions. For our purposes, their most important result is that every
_decomposable_ pattern has linear saturation function. We call a pattern $P$
decomposable if it has the form

$\displaystyle\begin{pmatrix}A&\mathbf{0}\\\ \mathbf{0}&B\end{pmatrix}\text{
or }\begin{pmatrix}\mathbf{0}&A\\\ B&\mathbf{0}\end{pmatrix}$

for two matrices $A,B\neq\mathbf{0}$, where $\mathbf{0}$ denotes an all-0
matrix of the appropriate size. Otherwise, we call $P$ _indecomposable_. Also,
patterns of the first form $\left(\begin{smallmatrix}A&\mathbf{0}\\\
\mathbf{0}&B\end{smallmatrix}\right)$ are called _sum decomposable_ , and
patterns not of that form are called _sum indecomposable_.333These terms are
derived from the theory of permutation patterns (see, e.g., Vatter [Vat14]).
We are not aware of a standard term for this property in the context of 0-1
matrices.

$\displaystyle Q=\left(\begin{smallmatrix}&\bullet&&&\\\ &&&&\bullet\\\
&&\bullet&&\\\ \bullet&&&&\\\ &&&\bullet&\end{smallmatrix}\right)$ Figure 1:
The matrix with saturation function $\mathcal{O}(1)$ found by Fulek and
Keszegh [FK20].

Fulek and Keszegh also found a single non-trivial pattern with bounded
saturation function ($Q$, pictured in Figure 1), and conjectured that there
are many more. Geneson [Gen20] recently confirmed this by proving that almost
all _permutation matrices_ have bounded saturation function. A permutation
matrix is matrix with exactly one 1-entry in each row and each column. A
different class of matrices with bounded saturation function, containing both
permutation matrices and non-permutation matrices where found recently by the
author [Ber20].444These results have been incorporated into this paper in
Sections 1.1 and 2.

In this paper, we show that, in fact, _all_ indecomposable permutation
matrices have bounded saturation function. This completes the characterization
of permutation matrices in terms of their saturation function.

######  Theorem 1.1.

A permutation matrix has linear saturation function if and only if it is
decomposable.

A simple generalization of the technique that Fulek and Keszegh used to prove
that $\mathrm{sat}(Q,n)\in\mathcal{O}(1)$ implies the following: To prove
Theorem 1.1, it is sufficient to find a _vertical witness_ for every
indecomposable permutation matrix $P$, where we define a vertical witness for
$P$ to be a matrix $M$ (of arbitrary size) that avoids $P$, has an empty row,
and adding a 1-entry in that empty row creates an occurrence of $P$ in $M$.

We therefore construct vertical witnesses for all permutation matrices. Our
constructions are based on the fact that indecomposable permutation matrices
contain a certain substructure which we call _spanning oscillation_.

We also generalize a partial result to a class that contains non-permutation
patterns:

theoremrestateFourTravGen Let $P$ be a pattern that contains four 1-entries
$x_{1},x_{2},x_{3},x_{4}$ such that for each $i\in[4]$, there are no other
1-entries in the same row or column as $x_{i}$, and $x_{i}$ is in the first or
last row or column, and $x_{1},x_{2},x_{3},x_{4}$ form one of the two patterns

$\displaystyle\left(\begin{smallmatrix}&\bullet&&\\\ &&&\bullet\\\
\bullet&&&\\\
&&\bullet&\end{smallmatrix}\right),\left(\begin{smallmatrix}&&\bullet&\\\
\bullet&&&\\\ &&&\bullet\\\ &\bullet&&\end{smallmatrix}\right).$

Then $\mathrm{sat}(P,n)\in\mathcal{O}(1)$.

In Section 1.1 we define (vertical) witnesses, and in Section 1.2, we define
spanning oscillations. In Section 1.4 we introduce an alternative
characterization of pattern containment that simplifies our proofs. In
Sections 2, 3, and 4, we construct vertical witnesses for all permutation
matrices, based on different types of spanning oscillations, which proves
Theorem 1.1. We also prove Theorem 1.1 in Section 2.

We now introduce conventions and notation used throughout the paper. Some more
definitions that are only needed for Sections 2, 3, and 4 will be introduced
in Section 1.4.

We identify 1-entries in an $m\times n$ matrix $M$ as their positions
$(i,j)\in[m]\times[n]$, where $i$ is the row of the 1-entry (from top to
bottom), and $j$ is its column (from left to right). $E(M)$ denotes the set of
1-entries in $M$. For two 1-entries $x=(i,j)\in E(M)$ and
$x^{\prime}=(i^{\prime},j^{\prime})\in E(M)$, we write
$x<_{\mathrm{v}}x^{\prime}$ if $i<i^{\prime}$ and $x<_{\mathrm{h}}x^{\prime}$
if $j<j^{\prime}$. Define $x\leq_{\mathrm{v}}x^{\prime}$ and
$x\leq_{\mathrm{h}}x^{\prime}$ analogously. We also say $x$ is _above_
$x^{\prime}$ if $x<_{\mathrm{v}}x^{\prime}$, and use _below_ , _to the right_
, and _to the left_ similarly.

In a permutation matrix $P$, we denote the leftmost (rightmost, topmost,
bottommost) 1-entry of $P$ by $\ell_{P}$ ($r_{P}$, $t_{P}$, $b_{P}$). Note
that in an indecomposable $k\times k$ permutation matrix with $k\geq 2$, these
four 1-entries are pairwise distinct.

Let $M$ be an arbitrary matrix. Denote by $\mathrm{rot}(M)$ the matrix
obtained by 90-degree clockwise rotation of $M$, denote by $\mathrm{rev}(M)$
the matrix obtained by reversing all rows of $P$, and denote by
$\mathrm{trans}(M)$ the transpose of $M$, i.e., the matrix obtained by
swapping the roles of rows and columns.555We do not use the common superscript
T, as it will later be used with the meaning “top”.

###  1.1 Witnesses

Let $P$ be a matrix pattern without empty rows or columns. An _explicit
witness_ 666An explicit witness is what Fulek and Keszegh [FK20] call a
_witness_. for $P$ is a matrix $M$ that is $P$-saturating and contains at
least one empty row and at least one empty column. If
$\mathrm{sat}(P,n)\in\mathcal{O}(1)$, then $P$ has an explicit witness: assume
$\mathrm{sat}(P,n)\leq c_{P}$, then there exists a $(c_{P}+1)\times(c_{P}+1)$
$P$-saturating matrix $M$ with at most $c_{P}$ 1-entries. Clearly, $M$ has an
empty row and an empty column.

Fulek and Keszegh note that the reverse is also true: We can replace an empty
row (column) in a $P$-saturating matrix by an arbitrary number of empty rows
(columns), and the resulting arbitrarily large matrix will still be
$P$-saturating. As such, an $m_{0}\times n_{0}$ explicit witness for $P$ of
weight $w$ implies that $\mathrm{sat}(P,m,n)\leq w$ for each $m\geq m_{0}$ and
$n\geq n_{0}$. Note that it is critical here that $P$ has no empty rows or
columns. Otherwise, inserting empty rows or columns into $M$ might create an
occurrence of $P$.

We call a row (column) of a matrix $M$ _$P$ -expandable_ if the row (column)
is empty and adding a single 1-entry anywhere in that row (column) creates a
new occurrence of $P$ in $M$. An explicit witness for $P$ is thus a saturating
matrix with at least one $P$-expandable row and an $P$-expandable column. We
define a _witness_ for $P$ (used implicitly by Fulek and Keszegh) as a matrix
that avoids $P$ and has at least one $P$-expandable row and at least one
$P$-expandable column. Clearly, an explicit witness is a witness. The
following lemma shows that finding a witness is sufficient to show that
$\mathrm{sat}(P,n)\in\mathcal{O}(1)$.

######  Lemma 1.2.

If a pattern $P$ without empty rows or columns has an $m_{0}\times n_{0}$
witness, then $P$ has an $m_{0}\times n_{0}$ explicit witness.

###### Proof.

Let $M$ be an $m_{0}\times n_{0}$ witness for $P$. If $M$ is $P$-saturating,
then we are done. Otherwise, there must be a 0-entry $(i,j)$ in $M$ that can
be changed to 1 without creating an occurrence $P$. Choose one such 0-entry
and turn it into 1. Note that $(i,j)$ cannot be contained in an expandable row
or column of $M$, so the resulting matrix is still a witness. Thus, we obtain
an explicit witness after repeating this step at most $m_{0}\cdot n_{0}$
times. ∎

####  1.1.1 Vertical and horizontal witnesses

Fulek and Keszegh also considered the asymptotic behavior of the functions
$\mathrm{sat}(P,m_{0},n)$ and $\mathrm{sat}(P,m,n_{0})$, where $m_{0}$ and
$n_{0}$ are fixed. The dichotomy of $\mathrm{sat}(P,n)$ also holds in this
setting:

######  Theorem 1.3 ([FK20, Parts of Theorem 1.3]).

For every pattern $P$, and constants $m_{0},n_{0}$,

  1. (i)

either $\mathrm{sat}(P,m_{0},n)\in\mathcal{O}(1)$ or
$\mathrm{sat}(P,m_{0},n)\in\Theta(n)$;

  2. (ii)

either $\mathrm{sat}(P,m,n_{0})\in\mathcal{O}(1)$ or
$\mathrm{sat}(P,m,n_{0})\in\Theta(m)$.

We can adapt the notion of witnesses in order to classify
$\mathrm{sat}(P,m_{0},n)$ and $\mathrm{sat}(P,m,n_{0})$. Let $P$ be a matrix
pattern without empty rows or columns. A _horizontal (vertical) witness_ for
$P$ is a matrix $M$ that avoids $P$ and contains an expandable column
(row).777A horizontal witness can be expanded horizontally, a vertical witness
can be expanded vertically. Clearly, $P$ has a horizontal witness with $m_{0}$
rows if and only if $\mathrm{sat}(P,m_{0},n)$ is bounded; and $P$ has a
vertical witness with $n_{0}$ columns if and only if $\mathrm{sat}(P,m,n_{0})$
is bounded. Further note that $M$ is a witness for $P$ if and only if $M$ is
both a horizontal witness and a vertical witness.

We now prove that we can essentially restrict our attention to the
classification of $\mathrm{sat}(P,m_{0},n)$ and $\mathrm{sat}(P,m,n_{0})$. The
following two lemmas are a generalization of the technique used by Fulek and
Keszegh to prove that $\mathrm{sat}(Q,n)\in\mathcal{O}(1)$ for the pattern $Q$
depicted in Figure 1.

######  Lemma 1.4.

Let $P$ be a matrix pattern without empty rows or columns, and only one
1-entry in the last row (column). Let $W$ be a horizontal (vertical) witness
for $P$. Then, appending an empty row (column) to $W$ again yields a
horizontal (vertical) witness.

###### Proof.

We prove the lemma for horizontal witnesses, and appending a row. The other
case follows by symmetry. Let $W$ be an $m_{0}\times n_{0}$ horizontal witness
for $P$, where the $j$-th column of $W$ is expandable. Let $W^{\prime}$ be the
matrix obtained by appending a row to $W$. Clearly, $W^{\prime}$ still does
not contain $P$. Moreover, adding an entry in $W^{\prime}$ at $(i,j)$ for any
$i\neq n_{0}+1$ creates a new occurrence of $P$. It remains to show that
adding an entry at $(n_{0}+1,j)$ creates an occurrence of $P$.

We know that adding an entry at $(n_{0},j)$ in $W^{\prime}$ creates an
occurrence of $P$. Let $I$ the set of positions of 1-entries in $W(P)$ that
form the occurrence of $P$. Since $P$ has only one entry in the last row, all
positions $(i^{\prime},j^{\prime})\in I\setminus\\{(n_{0},j)\\}$ satisfy
$i^{\prime}<n_{0}+1$. Thus, adding a 1-entry at $(n_{0}+1,j)$ instead of
$(n_{0},j)$ creates an ocurrence of $P$ at positions
$I\setminus\\{(n_{0},j)\\}\cup\\{(n_{0}+1,j)\\}$, which implies that
$W^{\prime}$ is a horizontal witness. ∎

######  Lemma 1.5.

Let $P$ be a indecomposable pattern without empty rows or columns, and with
only one 1-entry in the last row and one 1-entry in the last column. Then
$\mathrm{sat}(P,n)\in\mathcal{O}(1)$ if and only if there exist constants
$m_{0},n_{0}$ such that $\mathrm{sat}(P,m_{0},n)\in\mathcal{O}(1)$ and
$\mathrm{sat}(P,m,n_{0})\in\mathcal{O}(1)$.

###### Proof.

Suppose that $\mathrm{sat}(P,n)\in\mathcal{O}(1)$. Then $P$ has an
$m_{0}\times n_{0}$ witness $M$, and thus $\mathrm{sat}(P,m_{0},n)$ is at most
the weight of $M$, for every $n\geq n_{0}$. Similarly,
$\mathrm{sat}(P,m,n_{0})\in\mathcal{O}(1)$.

Now suppose that $\mathrm{sat}(P,m_{0},n)\in\mathcal{O}(1)$ and
$\mathrm{sat}(P,m,n_{0})\in\mathcal{O}(1)$. Then, for some $m_{1},n_{1}$,
there exists an $m_{0}\times n_{1}$ horizontal witness $W_{\mathrm{H}}$ and an
$m_{1}\times n_{0}$ vertical witness $W_{\mathrm{V}}$. Consider the following
$(m_{0}+m_{1})\times(n_{0}+n_{1})$ matrix, where $\mathbf{0}_{m\times n}$
denotes the all-0 $m\times n$ matrix:

$\displaystyle W=\begin{pmatrix}\mathbf{0}_{m_{0}\times
n_{0}}&W_{\mathrm{H}}\\\ W_{\mathrm{V}}&\mathbf{0}_{m_{1}\times
n_{1}}\end{pmatrix}$

We first show that $W$ does not contain $P$. Suppose it does. Since $P$ is
contained neither in $W_{\mathrm{H}}$ nor in $W_{\mathrm{V}}$, an occurrence
of $P$ in $W$ must contain 1-entries in both the bottom left and top right
quadrant. But then $P$ is decomposable, a contradiction.

By Lemma 1.4, $W_{\mathrm{V}}^{\prime}=(W_{\mathrm{V}},\mathbf{0}_{m_{1}\times
n_{1}})$ is a vertical witness, and
$W_{\mathrm{H}}^{\prime}=\binom{W_{\mathrm{H}}}{\mathbf{0}_{m_{1}\times
n_{1}}}$ is a horizontal witness. The expandable row in
$W_{\mathrm{V}}^{\prime}$ and the expandable column in
$W_{\mathrm{H}}^{\prime}$ are both also present in $W$. This implies that $W$
is a witness for $P$, so $\mathrm{sat}(P,n)\in\mathcal{O}(1)$. ∎

Figure 2 shows an example of a witness, constructed with Lemma 1.5, using
vertical/horizontal witnesses presented later in Section 2, and an explicit
witness constructed using Lemma 1.2.

$\displaystyle\left(\begin{smallmatrix}&&\bullet&\\\ \bullet&&&\\\
&&&\bullet\\\ &\bullet&&\end{smallmatrix}\right)\hskip
28.45274pt\left(\setcounter{MaxMatrixCols}{11}\begin{smallmatrix}&&&&&&&&\cdot&\bullet&\\\
&&&&&&&\bullet&\cdot&&\\\ &&&&&&&&\cdot&&\bullet\\\ &&&&&&\bullet&&\cdot&&\\\
&&&&&&&&\cdot&\bullet&\\\ &&&&&&&\bullet&\cdot&&\\\ &&\bullet&&&&&&\cdot&&\\\
\bullet&&&&\bullet&&&&\cdot&&\\\
\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot\\\
&\bullet&&&&\bullet&&&\cdot&&\\\
&&&\bullet&&&&&\cdot&&\end{smallmatrix}\right)\hskip
28.45274pt\left(\setcounter{MaxMatrixCols}{11}\begin{smallmatrix}\bullet&\bullet&\bullet&\bullet&&\bullet&\bullet&\bullet&\cdot&\bullet&\bullet\\\
&&&&&&&\bullet&\cdot&\bullet&\bullet\\\
&&&&&\bullet&\bullet&\bullet&\cdot&\bullet&\bullet\\\
&&&&&\bullet&\bullet&\bullet&\cdot&\bullet&\\\
&&&&&\bullet&&\bullet&\cdot&\bullet&\\\
&\bullet&\bullet&\bullet&&\bullet&&\bullet&\cdot&\bullet&\bullet\\\
&\bullet&\bullet&\bullet&&\bullet&&&\cdot&&\\\
\bullet&\bullet&&\bullet&\bullet&\bullet&&&\cdot&&\\\
\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot&\cdot\\\
\bullet&\bullet&&\bullet&\bullet&\bullet&&&\cdot&&\\\
\bullet&&&\bullet&\bullet&\bullet&&&\cdot&\bullet&\bullet\end{smallmatrix}\right)$
Figure 2: A pattern (left), a witness (middle) and an explicit witness (right)
for the pattern. The small dots indicate the expandable row/column.

Observe that the transformations $\mathrm{rev}$, $\mathrm{rot}$, and
$\mathrm{trans}$ all preserve witnesses. However, the latter two change
vertical witnesses to horizontal witnesses, and vice versa. Formally:

######  Observation 1.6.

Let $P$ be a matrix with a vertical witness $W$. Then $\mathrm{rev}(W)$ is a
vertical witness of $\mathrm{rev}(P)$, $\mathrm{rot}(W)$ is a horizontal
witness of $\mathrm{rot}(P)$, and $\mathrm{trans}(W)$ is a horizontal witness
of $\mathrm{trans}(P)$.∎

Recall that our goal is to show that every indecomposable permutation matrix
has a witness. Since indecomposable permutation matrices are closed under
transposition, Lemmas 1.5 and 1.6 imply that it suffices to find a _vertical_
witness for each indecomposable permutation matrix. The same is true for every
class of permutation matrices satisfying the conditions of Lemma 1.5 that is
closed under transposition or 90-degree clockwise rotation. This is useful to
prove Theorem 1.1.

######  Lemma 1.7.

Let $\mathcal{P}$ be a class of indecomposable patterns without empty rows or
columns, and with only one 1-entry in the last row and one 1-entry in the last
column. If $\mathcal{P}$ is closed under transposition or 90-degree clockwise
rotation and each pattern in $\mathcal{P}$ has a vertical witness, then
$\mathrm{sat}(P,n)\in\mathcal{O}(1)$ for each $P\in\mathcal{P}$.

###### Proof.

Suppose that $\mathcal{P}$ is closed under transposition and each
$P\in\mathcal{P}$ has a vertical witness. By Lemma 1.5, it suffices to show
that each pattern in $\mathcal{P}$ has a horizontal witness. Let
$P\in\mathcal{P}$. Then $\mathrm{trans}(P)\in\mathcal{P}$ has a vertical
witness $W$. By 1.6, $\mathrm{trans}(W)$ is a horizontal witness for
$\mathrm{trans}(\mathrm{trans}(P))=P$.

The case that $\mathcal{P}$ is closed under 90-degree rotation can be handled
analogously. ∎

###  1.2 Spanning oscillations

We now introduce _spanning oscillations_ , a class of substructures that
characterizes indecomposable permutation matrices.

For a permutation matrix $P$, the _permutation graph_ $G_{P}$ of the
underlying permutation can be defined as follows: The vertex set is $E(P)$,
and two 1-entries $x,y\in E(P)$ have an edge between them if $x$ is below and
to the left of $y$ (or vice versa).

An _oscillation_ in a permutation matrix of $P$ is a sequence
$X=(x_{1},x_{2},\dots,x_{m})$ of distinct 1-entries in $P$ such that $X$ forms
an induced path in $G_{P}$, i.e., there is an edge between $x_{i}$ and
$x_{i+1}$ for each $i\in[m-1]$, and no other edges between 1-entries in $X$.
Oscillations have been studied before in several contexts [Pra73, BRV08,
Vat11]. Vatter showed that a permutation matrix $P$ is sum indecomposable if
and only if it has an oscillation that starts with $\ell_{P}$ and ends with
$r_{P}$ [Vat11, Propositions 1.4, 1.7]. Our characterization of indecomposable
permutations is very similar. Call an oscillation
$X=(x_{1},x_{2},\dots,x_{m})$ _spanning_ if
$\\{x_{1},x_{2}\\}=\\{\ell_{P},t_{P}\\}$ and
$\\{x_{m-1},x_{m}\\}=\\{b_{P},r_{P}\\}$.

######  Lemma 1.8.

Let $P$ be a sum indecomposable permutation matrix such that $t_{P}$ is to the
left of $b_{P}$ or $\ell_{P}$ is above $r_{P}$. Then $P$ has a spanning
oscillation.

###### Proof.

We write $\ell,t,b,r$ for $\ell_{P},t_{P},b_{P},r_{P}$. By symmetry, we can
assume that $t$ is to the left of $b$ (otherwise, replace $P$ by
$\mathrm{trans}(P)$, noting that $G_{P}=G_{\mathrm{trans}(P)}$). Recall that
$\ell,t,b,r$ are pairwise distinct, as $P$ is indecomposable and not $1\times
1$.

Since $P$ is sum indecomposable, it has an oscillation
$X^{\prime}=(x_{1}^{\prime},x_{2}^{\prime},\dots,x_{m}^{\prime})$ with
$x_{1}^{\prime}=\ell$, $x_{m}^{\prime}=r$. Suppose first that $t$ occurs in
$X^{\prime}$. Since $G_{P}$ has an edge between $\ell$ and $t$, and $X$ is an
_induced_ path in $G_{P}$, this means that $x_{2}^{\prime}=t$. Otherwise, note
that $t$ is connected in $G_{P}$ to precisely those 1-entries that are to the
left of $t$. Let $i$ be maximal such that $x_{i}$ is to the left of $t$. If
$i=1$, then $(t,\ell,x_{2}^{\prime},\dots,x_{m}^{\prime})$ is an induced path
in $G_{P}$. Otherwise, $\ell,t,x_{i}^{\prime},\dots,x_{m}^{\prime}$ is an
induced path in $G_{P}$. In either case, we have an oscillation
$X^{\prime\prime}=(x_{1}^{\prime\prime},x_{2}^{\prime\prime},\dots,x_{m}^{\prime\prime})$
that starts with $\\{\ell,t\\}$ and ends with $r$.

It remains to make sure that $b$ is among the last two 1-entries in the
oscillation. If $b$ occurs in $X^{\prime\prime}$, then
$X_{m-1}^{\prime\prime}=b$, as with $t$. Otherwise, let $j$ be minimal such
that $x_{j}$ is to the right of $b$. If $j=m$, then
$X=(x_{1}^{\prime\prime},x_{2}^{\prime\prime},\dots,x_{m-1}^{\prime\prime},r,b)$
is an induced path in $G_{P}$. Otherwise,
$X=(x_{1}^{\prime\prime},x_{2}^{\prime\prime},\dots,x_{j}^{\prime\prime},b,r)$
is an induced path in $G_{P}$. Since $\ell,t$ are both to the left of $b$, we
have $j\geq 2$, so $X$ is a spanning oscillation. ∎

We obtain the following characterization of indecomposable permutation
matrices.

######  Corollary 1.9.

A permutation matrix $P$ is indecomposable if and only if $P$ or
$\mathrm{rev}(P)$ has a spanning oscillation or $P$ is the $1\times 1$
permutation matrix.

###### Proof.

First, assume $P$ is indecomposable. If $t_{P}$ is to the left of $b_{P}$,
then Lemma 1.8 implies that $P$ has a spanning oscillation. If $t_{P}$ is to
the right of $b_{P}$, then Lemma 1.8 implies that $\mathrm{rev}(P)$ has a
spanning oscillation. If $t_{P}=b_{P}$, then $P$ is $1\times 1$.

Second, assume $P$ has a spanning oscillation. Then $P$ is sum indecomposable.
Suppose $P$ is decomposable, then $P$ has the form
$\left(\begin{smallmatrix}\mathbf{0}&B\\\
A&\mathbf{0}\end{smallmatrix}\right)$, so $t$ is to the right of $b$ and
$\ell$ is below $r$. But then $\ell,b,t,r$ form the complete bipartite graph
$K_{2,2}$ in $G_{P}$, implying that $P$ has no spanning oscillation, a
contradiction. A symmetric argument shows that $P$ is indecomposable if
$\mathrm{rev}(P)$ has a spanning oscillation. ∎

(Spanning) oscillations have a very rigid structure, which we now describe
more concretely, in terms of relative positions of 1-entries. Let $P$ be a
permutation matrix and $X=(x_{1},x_{2},\dots,x_{m})$ be a spanning oscillation
of $P$. For $2\leq i\leq m-1$, call $x_{i}$ an _upper_ 1-entry if $x_{i}$ is
above and to the right of $x_{i-1}$ and $x_{i+1}$, and call $x_{i}$ a _lower_
1-entry if $x_{i}$ is below and to the left of $x_{i-1}$ and $x_{i+2}$. Since
$G_{P}$ contains the edges $\\{x_{i-1},x_{i}\\}$ and $\\{x_{i},x_{i+1}\\}$,
but not the edge $\\{x_{i},x_{i+2}\\}$, every 1-entry (except $x_{1},x_{m}$)
is either upper or lower. Clearly, upper and lower 1-entries alternate, i.e.,
$x_{i}$ is upper if and only if $x_{i+1}$ is lower, for $2\leq i<m-1$. It is
convenient to also call $\ell_{P},b_{P}$ lower 1-entries and $t_{P},r_{P}$
upper 1-entries. We then have:

######  Observation 1.10.

Let $P$ be a permutation matrix and $X=(x_{1},x_{2},\dots,x_{m})$ be a
spanning oscillation of $P$. If $x_{1}=\ell_{P}$, then all $x_{i}$ with odd
$i$ are lower 1-entries, and all $x_{i}$ with even $i$ are upper 1-entries. If
$x_{1}=t_{P}$, then all $x_{i}$ with odd $i$ are upper 1-entries, and all
$x_{i}$ with even $i$ are lower 1-entries.∎

It is easy to see that, if $x_{1}=\ell_{P}$, then $x_{3}$, $x_{4}$ must be
below and to the right of $x_{1}$. By induction, and by considering symmetric
cases, we can prove:

######  Observation 1.11.

Let $P$ be a permutation matrix and $X=(x_{1},x_{2},\dots,x_{m})$ be a
spanning oscillation of $P$. Then $x_{i}$ is above and to the left of $x_{j}$
for each $i\in[m-2]$ and $i+2\leq j\leq m$.

This leaves us with only two possible spanning oscillations for each length
$m$, see Figure 3. Observe that spanning oscillations are preserved by
transposition and 180-degree rotation, in the following sense. Let $P$ be a
permutation matrix and $X$ be a spanning oscillation of $P$. Let
$P^{\prime}=\mathrm{trans}(P)$ (resp.,
$P^{\prime}=\mathrm{rot}^{2}(P)=\mathrm{rot}(\mathrm{rot}(P))$). Then
$P^{\prime}$ has a spanning oscillation $X^{\prime}$ that corresponds to the
transpose (resp., the 180-degree rotation) of $X$. With slight abuse of
notation we write $X^{\prime}=\mathrm{trans}(X)$ (resp.,
$X^{\prime}=\mathrm{rot}^{2}(X)$).

$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$$x_{7}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$$x_{7}$
Figure 3: The spanning oscillations of length $m$, for $m=4,5,6,7$. The dashed
line segments indicate the edges of the permutation graph. The borders
indicate the possible positions for other 1-entries if the spanning
oscillation is tall (top row) or wide (bottom row).

A spanning oscillation $X=(x_{1},x_{2},\dots,x_{m})$ is _tall_ if the
following two properties are satisfied for each $2\leq i\leq m-2$ where
$x_{i}$ is an upper 1-entry.

  1. (i)

$P$ has no 1-entry that is below $x_{i+1}$ and to the left of $x_{i}$.

  2. (ii)

$P$ has no 1-entry that is above $x_{i}$ and to the right of $x_{i+1}$.

A spanning oscillation $X$ is _wide_ if $\mathrm{trans}(X)$ is tall. We now
show that we can always assume that a minimum-length spanning oscillation is
tall (or wide).

######  Lemma 1.12.

Let $P$ be a permutation matrix and $X=(x_{1},x_{2},\dots,x_{m})$ be a
spanning oscillation of $P$ of minimum length $m$. Then $P$ has a tall
spanning oscillation of length $m$ that starts with $x_{1},x_{2}$ and ends
with $x_{m-1},x_{m}$.

###### Proof.

Suppose $X$ is not tall, so it violates (i) or (ii) at some index $i$ with
$2\leq i\leq m-2$. We now show how to construct a spanning oscillation
$X^{\prime}$ of length $m$ that starts with $x_{1},x_{2}$, ends with
$x_{m-1},x_{m}$, and violates (i) or (ii) less often than $X$. Repeating this,
we eventually obtain a tall spanning oscillation.

Suppose first that $X$ violates (i) at index $i$. Then $x_{i}$ is an upper
1-entry, and there is a $y\in E(P)$ such that $y$ is below $x_{i+1}$ and to
the left of $x_{i}$. Assume $y$ is the bottommost such 1-entry. Note
$y\notin\\{\ell_{P},b_{P}\\}$, and that $x_{i+2}$ is above $x_{i+1}$ by 1.10.

Let $j$ be minimal such that $x_{j}$ is to the right of $y$. Since
$\ell_{P}<_{\mathrm{h}}y<_{\mathrm{h}}x_{i}$, we have $2\leq j\leq i$. Let $k$
be maximal such that $x_{k}$ is above $y$. Since
$x_{i+2}<_{\mathrm{v}}y<_{\mathrm{v}}b_{P}$, we have $i+2\leq k\leq m-1$.

Consider the sequence
$X^{\prime}=(x_{1},x_{2},\dots,x_{j},y,x_{k},x_{k+1},\dots,x_{m})$. We want to
show that $X^{\prime}$ is a spanning oscillation of $P$. Let $j^{\prime}<j$.
By definition of $j$, we know that $x_{j^{\prime}}$ is to the left of $y$. By
1.11, $x_{j^{\prime}}$ is above $x_{i+1}$, implying that $x_{j^{\prime}}$ is
above $y$. Thus, $G_{P}$ has no edge between $x_{j^{\prime}}$ and $y$.
Similarly, we can prove that there is no edge between $y$ and $x_{k^{\prime}}$
for each $k^{\prime}>k$. This means that $X^{\prime}$ is an oscillation. Since
$2\leq j$ and $k\leq m-1$, we know that $X^{\prime}$ starts with $x_{1},x_{2}$
and ends with $x_{m-1},x_{m}$, implying that $X^{\prime}$ is a spanning
oscillation.

By assumption, $P$ has no spanning oscillation shorter than $P$, so $X$ must
have length $m$, implying that $j=i$ and $k=i+2$. Further, $X^{\prime}$ does
not violate (i) at index $i$, since, by choice of $y$, there are no 1-entries
below $y$ and to the left of $x_{j}=x_{i}$. Thus, $X^{\prime}$ has strictly
less overall violations of (i) or (ii) than $X$.

The second case, where $X$ violates (ii), can be proven symmetrically. ∎

Clearly, the statement of Lemma 1.12 is also true when replacing “tall” with
“wide”, using the same proof on $\mathrm{trans}(P)$.

###  1.3 Structure of the main proof

We divide the proof of Theorem 1.1 into three cases, proven in Sections 2, 3,
and 4. In Section 2, we handle the special case of length-4 spanning
oscillations:

######  Lemma 1.13.

Each permutation matrix with a spanning oscillation of length 4 has a vertical
witness.

In Section 3, we prove: lemmarestateInvTravWit Each permutation matrix $P$
with a wide spanning oscillation of length $m\geq 5$ that starts with $t_{P}$
has a vertical witness.

The final and most involved case is treated in Section 4: lemmarestateTravWit
Each permutation matrix $P$ with a tall spanning oscillation of even length
$m\geq 6$ that starts with $\ell_{P}$ has a vertical witness.

It is not immediately obvious that Lemmas 1.13, 1.13, and 1.13 cover all
indecomposable permutation matrices. We now show that this is the case.

######  Corollary 1.14.

Every indecomposable permutation matrix has a vertical witness.

###### Proof.

Let $P$ be an indecomposable permutation matrix. If $P$ is $1\times 1$, any
all-zero matrix is a witness of $P$. Otherwise, one of $P$ and
$\mathrm{rev}(P)$ has a spanning oscillation $X$ by Corollary 1.9. By 1.6, it
suffices to find a vertical witness for either $P$ or $\mathrm{rev}(P)$, so
without loss of generality, assume that $X$ is a spanning oscillation of $P$,
and that $X$ has minimum length $m$. If $m=4$, we can apply Lemma 1.13. If
$m\geq 5$ and $X$ starts with $t_{P}$, then Lemma 1.12 implies that $P$ also
has a wide spanning oscillation of size $m$ that starts with $t_{P}$, so we
can apply Lemma 1.13.

Now assume $m\geq 5$ and $X$ starts with $\ell_{P}$. If $m$ is even, we can
apply Lemma 1.13, since by Lemma 1.12 we can assume that $X$ is tall.
Otherwise, if $m$ is odd, 1.10 implies that $X$ ends with $b_{P}$. This means
that the spanning oscillation $\mathrm{rot}^{2}(X)$ of $\mathrm{rot}^{2}(P)$
starts with $t_{\mathrm{rot}^{2}(P)}$, so we can apply Lemma 1.13 to obtain a
witness $W^{\prime}$ of $\mathrm{rot}^{2}(P)$. 1.6 implies that
$\mathrm{rot}^{2}(W^{\prime})$ is a witness of $P$. ∎

###  1.4 Embeddings

In the following sections, we use an alternative definition of pattern
containment based on sets of 1-entries. Let $P$ be a pattern and $M$ be a
matrix. We say a function $\phi\colon E(P)\rightarrow E(M)$ is an _embedding_
of $P$ into $M$ if for $x,y\in E(P)$ we have
$x<_{\mathrm{h}}y\Leftrightarrow\phi(x)<_{\mathrm{h}}\phi(y)$ and
$x<_{\mathrm{v}}y\Leftrightarrow\phi(x)<_{\mathrm{v}}\phi(y)$.

Note that if we allow empty rows or columns in $P$, then $E(P)$ does not
determine $P$, since appending an empty row or column to $P$ does not change
$E(P)$. This means that the existence of an embedding of $P$ into $M$ does not
necessarily imply that $P$ is contained in $M$. However, we only consider
patterns without empty rows or columns in this paper, and in that case,
equivalence holds. lemmarestateEquivContainment Let $P$, $M$ be matrices, and
let $P$ have no empty rows or columns. Then $P$ is contained in $M$ if and
only if there is an embedding of $P$ into $M$.

A proof of Section 1.4 is provided in Appendix A. We now introduce some
notation used in the following sections.

Let $x=(i,j)$, $y=(i^{\prime},j^{\prime})$ be two 1-entries. The _horizontal
distance_ between $x$ and $y$ is
$\mathrm{d}^{\mathrm{h}}((i,j),(i^{\prime},j^{\prime}))=|i-i^{\prime}|$, and
the _vertical distance_ between $x$ and $y$ is
$\mathrm{d}^{\mathrm{v}}((i,j),(i^{\prime},j^{\prime}))=|j-j^{\prime}|$. The
_width_ $0pt(A)$ (resp. _height_ $0pt(A)$) of a set $A\subseteq E(M)$ is the
maximum horizontal (resp. vertical) distance between 1-two entries in $A$.

Let $\phi$ be an embedding of $P$ into $M$, and let $x,y\in E(M)$. We define
variants of the above notions that only “count” 1-entries of $M$ that are hit
by $\phi$. This will be useful if we have some, but not full information about
$\phi$. Let $\mathrm{d}^{\mathrm{h}}_{\phi}(x,y)$ be the number of 1-entries
$z\in E(P)$ such that $x<_{\mathrm{h}}\phi(z)\leq_{\mathrm{h}}y$, and let
$\mathrm{d}^{\mathrm{v}}_{\phi}(x,y)$ be the number of 1-entries $z\in E(P)$
such that $x<_{\mathrm{v}}\phi(z)\leq_{\mathrm{v}}y$. For $A\subseteq E(M)$,
let $0pt_{\phi}(A)=\max_{x,y\in A}\mathrm{d}^{\mathrm{h}}_{\phi}(x,y)$, and
$0pt_{\phi}(A)=\max_{x,y\in A}\mathrm{d}^{\mathrm{v}}_{\phi}(x,y)$.

######  Observation 1.15.

Let $\phi$ be an embedding of $P$ into $M$, let $x,y\in E(P)$, and let
$\phi(x),\phi(y)\in A\subseteq E(M)$. Then

$\displaystyle\mathrm{d}^{\mathrm{h}}(x,y)=\mathrm{d}^{\mathrm{h}}_{\phi}(\phi(x),\phi(y))\leq\mathrm{d}^{\mathrm{h}}(\phi(x),\phi(y))\leq
0pt(A);\text{ and}$
$\displaystyle\mathrm{d}^{\mathrm{v}}(x,y)=\mathrm{d}^{\mathrm{v}}_{\phi}(\phi(x),\phi(y))\leq\mathrm{d}^{\mathrm{v}}(\phi(x),\phi(y))\leq
0pt(A).$ ∎

##  2 Spanning oscillations of length 4

In this section, we show Theorem 1.1, which immediately implies Lemma 1.13.

*

Let $\mathcal{P}$ denote the class of patterns defined in Theorem 1.1. Note
that $\mathcal{P}$ is closed under transposition. Thus, by Lemma 1.7, it is
sufficient to prove that each $P\in\mathcal{P}$ has a vertical witness.

Let $\mathcal{P}^{\prime}$ be the subset of patterns $P\in\mathcal{P}$ where
the unique leftmost 1-entry $\ell$ of $P$ is above the unique rightmost
1-entry $r$ of $P$. It is easy to see that $P$ has the following form, where
the boxes contain arbitrarily many 1-entries:

$\ell$$t$$b$$r$

Since for each $P\in\mathcal{P}\setminus\mathcal{P}^{\prime}$, we have
$\mathrm{rev}(P)\in\mathcal{P}^{\prime}$, 1.6 implies that it is sufficient to
prove that each $P\in\mathcal{P}^{\prime}$ has a vertical witness.

$\displaystyle\left(\begin{smallmatrix}&&\bullet&\\\ \bullet&&&\\\
&&&\bullet\\\
&\bullet&&\end{smallmatrix}\right)\rightarrow\left(\begin{smallmatrix}&&\bullet\\\
\bullet&&\\\ &&\\\
&\bullet&\end{smallmatrix}\right),\left(\begin{smallmatrix}&\bullet&\\\ &&\\\
&&\bullet\\\
\bullet&&\end{smallmatrix}\right)\rightarrow\left(\begin{smallmatrix}&&\bullet&&&\\\
\bullet&&&&\bullet&\\\ \cdot&\cdot&\cdot&\cdot&\cdot&\cdot\\\
&\bullet&&&&\bullet\\\ &&&\bullet&&\end{smallmatrix}\right)$ Figure 4:
Construction of $S(Q_{1})$ from $Q_{1}$. The small dots indicate the
expandable row.

######  Lemma 2.1.

Each $P\in\mathcal{P}^{\prime}$ has a vertical witness.

###### Proof.

Let $P\in\mathcal{P}^{\prime}$ be a $k_{1}\times k_{2}$ pattern, let
$\ell=(i,j)$ be the unique leftmost 1-entry in $P$, and let
$r=(i^{\prime},j^{\prime})$ be the unique rightmost 1-entry in $P$. Note that
$i<i^{\prime}$

Let $P_{\mathrm{L}}$ and $P_{\mathrm{R}}$ be the submatrices of $P$ obtained
by removing the rightmost, resp. leftmost, column. Note that in
$P_{\mathrm{L}}$, the $i^{\prime}$-th row is empty, and in $P_{\mathrm{R}}$,
the $i$-th row is empty. We place a copy of $P_{\mathrm{L}}$ to the left of
$P_{\mathrm{R}}$, so that the two empty rows coincide. Formally, obtain $L$
from $P_{\mathrm{L}}$ by appending $i^{\prime}-i>0$ rows (at the bottom),
obtain $R$ from $P_{\mathrm{R}}$ by prepending $i^{\prime}-i>0$ rows (at the
top), and define $S(P)$ as the concatenation $(L,R)$. Note that $S(P)$ is a
$(k_{1}+i^{\prime}-i)\times(2k_{2}-2)$ matrix, and that the $i^{\prime}$-th
row of $S(P)$ is empty. Figure 4 shows an example of the construction. In the
following, we will use $L$ and $R$ interchangeably with the corresponding
subsets of $E(S(P))$.

We claim that the $i^{\prime}$-th row is $P$-expandable. Indeed, adding a
1-entry in the $i^{\prime}$-th row in the first $k-1$ columns (to the left of
$R$) completes an occurrence of $P$ with $R$, and adding a 1-entry in the last
$k-1$ columns (to the right of $L$) completes an occurrence of $P$ with $L$.

It remains to show that $S(P)$ avoids $P$. Suppose $S(P)$ contains $P$, so
there is an embedding $\phi$ of $P$ into $S(P)$. Let $t,b\in E(P)$ be the
unique topmost, respectively bottommost, 1-entry in $P$.

Suppose first that $\phi(b)\in L$. Since
$0pt(L)=\mathrm{d}^{\mathrm{v}}(t,b)=k-1$, and the $i^{\prime}$-th row of $P$
is empty, we have $0pt_{\phi}(L)<\mathrm{d}^{\mathrm{v}}(t,b)$. This implies
that $\phi(t)$ is above $L$. But $S(P)$ has no 1-entries above $L$, a
contradiction.

Otherwise, $\phi(b)\in R$. Since $t$ is to the right of $b$, this implies that
$\phi(t)\in R$. But a similar argument as above shows that
$0pt_{\phi}(R)<\mathrm{d}^{\mathrm{v}}(t,b)$, a contradiction.

Thus, $S(P)$ avoids $P$ and has a $P$-expandable row, implying that $S(P)$ is
a vertical witness of $P$. ∎

##  3 Spanning oscillations starting with $t$

In this section, we prove: *

In Section 3.1 we present a construction of (possible) witnesses, which we
first use for the case $m=5$ in Section 3.2, and then for the case $m\geq 5$
in Section 3.3.

###  3.1 Witness construction

Let $P$ be an $k\times k$ permutation matrix such that $\ell=\ell_{P}$ is
above $r=r_{P}$, and let $q=(i_{q},j_{q})\in E(P)$, such that $q$ is above
$\ell$. We first construct a matrix $S^{\prime}(P,q)$ with a $P$-expandable
row, and then modify $S^{\prime}(P,q)$ to obtain the matrix $S(P,q)$, which
retains the expandable row and will be shown to avoid $P$ if $P$ has a wide
spanning oscillation $(t_{P},\ell_{P},x_{3},x_{4},\dots,x_{m})$ with $m\geq 5$
and we choose $q=x_{3}$.

Let $P_{\mathrm{R}}$ ($P_{\mathrm{L}}$) be the submatrix of $P$ obtained by
removing the leftmost (rightmost) column. Both $P_{\mathrm{R}}$ and
$P_{\mathrm{L}}$ have an empty row. To start the construction of
$S^{\prime}(P,q)$, we place a copy of $P_{\mathrm{R}}$ to the _left_ of a copy
of $P_{\mathrm{L}}$, such that the two copies do not intersect, and the empty
rows are aligned. We denote the copy of $P_{\mathrm{R}}$ in the construction
with $R$ and the copy of $P_{\mathrm{L}}$ with $L$. Note that, compared to the
construction in Section 2, $L$ and $R$ switch places.

Let $P_{\mathrm{L}}^{\prime}$ consist of all columns to the left of $q$, and
$P_{\mathrm{R}}^{\prime}$ consist of all columns to the right of $q$. To
finish the construction of $S^{\prime}(P,q)$, we place a copy of
$P_{\mathrm{L}}^{\prime}$ to the left of $R$ and a copy of
$P_{\mathrm{R}}^{\prime}$ to the right of $L$, such that the empty $i_{q}$-th
rows of $P_{\mathrm{L}}^{\prime}$ and $P_{\mathrm{R}}^{\prime}$ are aligned
with the empty row in $R$ and $L$. Denote the copies of
$P_{\mathrm{L}}^{\prime}$ and $P_{\mathrm{R}}^{\prime}$ as $L^{\prime}$ and
$R^{\prime}$ and let $P^{\prime}=L^{\prime}\cup R^{\prime}$.

Clearly, the empty row in $S^{\prime}(P,q)$ is expandable: Adding a 1-entry to
the left of $R$ will complete the partial occurrence $R$ of $P$, adding a
1-entry to the right of $L$ will complete $L$, and adding a 1-entry inside $R$
or $L$ will complete $P^{\prime}$.

We modify $S^{\prime}(P,q)$ to obtain $S(P,q)$ as follows.888This modification
resembles the principle of Geneson’s construction. [Gen20] Let $B$ be the set
of entries in $P^{\prime}=L^{\prime}\cup R^{\prime}$ that are below the
leftmost 1-entry in $P^{\prime}$ (the copy of $\ell$ in $P^{\prime}$). Move
$B$ down by a fixed number of rows, such that each 1-entry in $B$ is lower
than all 1-entries in $R\cup L$. Clearly, the expandable row stays expandable
after this change.

Figure 5 sketches the constructions. In the following sections, we denote the
1-entries in $S(P,q)$ as follows. If $x$ is a 1-entry in $P$, then let
$x^{\mathrm{R}}$ be the copy of $x$ in $R$, let $x^{\mathrm{L}}$ be the copy
of $x$ in $L$, and let $x^{\prime}$ be the copy of $x$ in $P^{\prime}$. For
subsets $X\subseteq E(P)$, we use $X^{\mathrm{R}}$, $X^{\mathrm{L}}$ and
$X^{\prime}$ similarly.

$q$$\ell$$r$$P$

$L$$R$$R^{\prime}$$L^{\prime}$$S^{\prime}(P,q)$

$L$$R$$R^{\prime}$$L^{\prime}$$L^{\prime}_{1}$$L^{\prime}_{2}$$S(P,q)$

Figure 5: $P$ and the two witness constructions $S^{\prime}(P,q)$ and
$S(P,q)$. The expandable row and the distance between $R$, $L$ and
$P^{\prime}$ are exaggerated.

We now show a property of $S(P,q)$ that is useful in both of the following
subsections.

######  Lemma 3.1.

Let $P$ be a $k\times k$ permutation matrix and $q\in E(P)$ such that
$q<_{\mathrm{v}}\ell<_{\mathrm{v}}r$ and $t$ is to the left of $b$. If $\phi$
is an embedding of $P$ in $S(P,q)$, then $\phi(t)\notin L^{\prime}$ and
$\phi(b)\in R^{\prime}$.

###### Proof.

Let $L^{\prime}_{2}$ denote the portion of $L^{\prime}$ below $\ell^{\prime}$,
and let $L^{\prime}_{1}=L^{\prime}\setminus L^{\prime}_{2}$.

We first show that $\phi(t)\notin L^{\prime}$. Suppose $\phi(t)\in
L^{\prime}$. Then also $\phi(\ell)\in L^{\prime}$. Since
$0pt(L^{\prime}_{2})<\mathrm{d}^{\mathrm{v}}(\ell,b)$, and there are no
nonempty rows below $L^{\prime}_{2}$, we know that $\phi(\ell)\notin
L^{\prime}_{2}$, and thus $\phi(t),\phi(\ell)\in L^{\prime}_{1}$. But
$0pt_{\phi}(L^{\prime}_{1})\leq\mathrm{d}^{\mathrm{v}}(t,l)-1$, a
contradiction.

$\phi(t)\notin L^{\prime}$ already shows that $\phi(b)\notin L^{\prime}$,
since $b$ is to the right of $t$. It remains to show that $\phi(b)\notin R\cup
L$. First, suppose that $\phi(b)\in L$. Then there are at most $k-2$ nonempty
rows above $\phi(b)$, but $\mathrm{d}^{\mathrm{v}}(t,b)=k-1$, a contradiction.

Second, suppose that $\phi(b)\in R$. Then $\phi(t)\in L^{\prime}\cup R$,
because $t$ is to the left of $b$. Since $q$ is above $\ell$, we have
$\mathrm{d}^{\mathrm{v}}(t,q)<\mathrm{d}^{\mathrm{v}}(t,\ell)$, so $t^{R}$ is
above $t^{\prime}$, and thus $t^{R}$ is the highest 1-entry in $L^{\prime}\cup
R$. But then
$\mathrm{d}^{\mathrm{v}}_{\phi}(\phi(t),\phi(b))\leq\mathrm{d}^{\mathrm{v}}_{\phi}(t^{\mathrm{R}},b^{\mathrm{R}})\leq\mathrm{d}^{\mathrm{v}}(t,b)-1$,
a contradiction. ∎

###  3.2 Length-5 spanning oscillations

$\ell$$t$$q$$b$$r$

$L$$R$$R^{\prime}$$L^{\prime}$

Figure 6: $P$ and $S(P,q)$ in the case of Lemma 3.2.

######  Lemma 3.2.

Let $P$ be a permutation matrix with a spanning oscillation
$X=(t_{P},x_{2},x_{3},x_{4},x_{5})$. Then $S(P,x_{3})$ avoids $P$.

###### Proof.

Let $q=x_{3}$, and write $\ell,t,b,r$ for $\ell_{P},t_{P},b_{P},r_{P}$. Note
that $x_{2}=\ell$ and $x_{4}=b$, so $q$ is above $\ell$ and to the right of
$b$. Figure 6 sketches $P$ and $S(P,q)$. Suppose $\phi$ is an embedding of $P$
into $S(P,q)$. By Lemma 3.1, $\phi(b)\in R^{\prime}$. But
$0pt(R^{\prime})=\mathrm{d}^{\mathrm{h}}(q,r)-1<\mathrm{d}^{\mathrm{h}}(b,r)$,
a contradiction. ∎

###  3.3 Longer spanning oscillations

We now consider the case where $P$ has a wide spanning oscillation
$(t_{P},x_{2},\dots,x_{m})$ of length greater than five. We first prove a
general statement on spanning oscillations starting with $t_{P}$.

######  Lemma 3.3.

Let $P$ be a permutation matrix and $X=(t_{P},x_{2},\dots,x_{m})$ be a
spanning oscillation of $P$ with $m\geq 6$. Then, removing $t=t_{P}$, the
columns to the left of $t$, and the rows above $x_{3}$ (as well as all newly
created rows or columns) does not make $P$ decomposable.

###### Proof.

Suppose it does, and let $P_{0}$ be the resulting decomposable pattern. Since
$x_{3}$ is the highest 1-entry in $P_{0}$ (slightly abusing notation), and
$x_{3}$ is above $r=r_{P}$ and to the left of $b=b_{P}$, we know that $P_{0}$
has the form $\left(\begin{smallmatrix}A&\mathbf{0}\\\
\mathbf{0}&B\end{smallmatrix}\right)$, where $x_{3}$ lies in $A$ and $r$, $b$
lie in $B$. This means that $x_{4}$ lies in $A$, since
$t<_{\mathrm{h}}x_{4}<_{\mathrm{h}}x_{3}$. Let $P_{1}$ be the matrix obtained
from $P_{0}$ by further removing all columns to the right of $x_{4}$. Clearly,
$P_{1}$ is decomposable, but $(x_{3},x_{4},\dots,x_{m})$ is a spanning
oscillation of $P_{1}$, a contradiction. ∎

We are now ready to prove the main result of this subsection.

$A$$B$$C$$r$$b$$q$$t$$\ell$

$L$$R$$R^{\prime}$$L^{\prime}_{1}$$L^{\prime}_{2}$$t^{\prime}$$\ell^{\prime}$

Figure 7: $P$ and $S(P,q)$ in the case of Lemma 3.4.

######  Lemma 3.4.

Let $X=(t_{P},x_{2},\dots,x_{m})$ be a wide spanning oscillation of $P$ with
$m\geq 6$. Then $P$ has a vertical witness.

###### Proof.

We write $\ell,t,b,r$ for $\ell_{P},t_{P},b_{P},r_{P}$ in the following. Let
$q=x_{3}$, and let $P_{0}$ be the set of 1-entries of $P$ that are to the
right of $t$ and not above $q$. By Lemma 3.3, $P_{0}$ does not correspond to a
decomposable pattern. Let $A$ denote the set of 1-entries to the right of $q$.
Note that $b,r\in A$, and, by wideness of $X$, all 1-entries in $A$ are below
$\ell$. Let $x$ be the highest 1-entry in $A$, and let $B$ be the set of
1-entries below $x$, to the left of $q$ and to the right of $t$. Then
$B\neq\emptyset$, otherwise $P_{0}$ would be decomposable. Finally,
$C=P_{0}\setminus(A\cup B)$ consists of the 1-entries to the right of $t$, not
above $q$, and above $x$. Figure 7 shows a sketch of $P$ and $S(P,X)$. Note
that $A^{\prime}=R^{\prime}$.

Suppose $\phi$ is an embedding of $P$ into $S(P,q)$. By Lemma 3.1, $\phi(b)\in
R^{\prime}$ and $\phi(t)\notin L^{\prime}$. Since all 1-entries in $B$ are to
the right of $t$, this implies $\phi(y)\notin L^{\prime}$ for each $y\in B$.
Moreover,
$0pt(R^{\prime})=\mathrm{d}^{\mathrm{h}}(q,r)-1<\mathrm{d}^{\mathrm{h}}(y,r)$
for each $y\in B$, so we have $\phi(B)\subseteq L\cup R$.

Let $L^{\prime}_{2}$ denote the portion of $L^{\prime}$ below $\ell^{\prime}$
and let $L^{\prime}_{1}=L^{\prime}\setminus L^{\prime}_{2}$. Note that
$L^{\prime}_{2}$ is below all 1-entries in $L\cup R$. Since all 1-entries in
$C$ are above all 1-entries in $B$, and all 1-entries in $A$ are to the right
of all 1-entries in $B$, we have $\phi(P_{0})=\phi(A\cup B\cup C)\subseteq
L^{\prime}_{1}\cup L\cup R\cup R^{\prime}$. Since $R^{\prime}=A^{\prime}$, all
1-entries in $R^{\prime}$ are to the right and below all 1-entries in
$L^{\prime}_{1}\cup L\cup R$, so $L^{\prime}_{1}\cup L\cup R\cup R^{\prime}$
can be decomposed into the two blocks $L^{\prime}_{1}\cup L\cup R$ and
$R^{\prime}$. Further, $\phi(b)\in R^{\prime}$ by Lemma 3.1, and since
$0pt(R^{\prime})<\mathrm{d}^{\mathrm{v}}(q,b)$, we have $\phi(q)\notin
R^{\prime}$. This means that $P_{0}$ is decomposable, a contradiction. ∎

##  4 Even-length spanning oscillations starting with $\ell$

In this section, we prove: *

For our witness construction to work, we need to define a substructure that
generalizes (tall) spanning oscillations of even length that start with
$\ell$. We call that substructure a _traversal_. Defining our witness
construction for traversals instead of spanning oscillations will allow us to
make a maximality assumption that is required for the proof that the witness
avoids $P$.

###  4.1 Traversals

Let $P$ be a permutation matrix and let $m\geq 4$. A _traversal_ of $P$ is a
sequence $X$ of distinct 1-entries $x_{1},x_{2},\dots,x_{m}$ such that

  1. (i)

$x_{1}=\ell_{P}$, $x_{2}=t_{P}$, $x_{m-1}=b_{P}$, $x_{m}=r_{P}$;

  2. (ii)

$x_{1}<_{\mathrm{h}}x_{3}<_{\mathrm{h}}x_{2}<_{\mathrm{h}}x_{5}<_{\mathrm{h}}x_{4}<_{\mathrm{h}}\dots<_{\mathrm{h}}x_{m-1}<_{\mathrm{h}}x_{m-2}<_{\mathrm{h}}x_{m}$;

  3. (iii)

$\ell_{P}<_{\mathrm{v}}x_{4}<_{\mathrm{v}}x_{6}<_{\mathrm{v}}\dots<_{\mathrm{v}}x_{m}$;

  4. (iv)

$x_{3}<_{\mathrm{v}}x_{5}<_{\mathrm{v}}\dots<_{\mathrm{v}}x_{m-3}<_{\mathrm{v}}r_{P}$;
and

  5. (v)

$x_{s}$ is below $x_{s+1}$ for each odd $s\in[m-1]$.

$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$$x_{7}$$x_{8}$ Figure 8: A tall
traversal. The solid lines indicate possible positions for other 1-entries.

Intuitively, property (ii) keeps the horizontal order of its 1-entries fixed,
in the same way it is fixed in an even-length spanning oscillation starting
with $\ell_{P}$. Vertically, however, we allow to arrange the 1-entries more
freely. There are still _upper_ (even) and _lower_ (odd) 1-entries as in 1.10
(this is implied by (iii), (iv), (v)), and we keep the order within the upper,
resp. lower, 1-entries with (iii), (iv). But we drop the condition that
$x_{i}$ is above $x_{j}$ for each odd $i\leq m-3$ and even $j\geq i+3$. This
means that we are allowed to “move” some upper 1-entries upwards, and some
lower 1-entries downwards, as long as the vertical order among upper (lower)
1-entries is kept intact. (iii), (iv) additionally ensure that we cannot move
any 1-entries above $\ell_{P}$ or below $r_{P}$. Figure 8 shows the shortest
traversal that is not an oscillation.

We say a traversal $(x_{1},x_{2},\dots,x_{m})$ is _tall_ if it satisfies the
following two properties for each even $2\leq i\leq m-2$.

  1. (vi)

$P$ has no 1-entry that is below $x_{i+1}$ and to the left of $x_{i}$.

  2. (vii)

$P$ has no 1-entry that is above $x_{i}$ and to the right of $x_{i+1}$.

It is easy to see that each tall spanning oscillation of even length that
starts with $\ell$ is a tall traversal.

###  4.2 Maximality assumption

Let $P$ be a permutation matrix with a tall traversal $X$. We can assume that
$X$ is maximal in the sense that no tall traversal of $P$ has $X$ as a proper
subsequence. We now show that such a _maximally tall_ traversal also cannot be
extended to a larger non-tall traversal in the following sense. Call a
traversal $(x_{1},x_{2},\dots,x_{m})$ _extendable_ if there is an odd $s$ with
$5\leq s\leq m-5$, and two 1-entries $y_{1},y_{2}$ in $P$ such that
$(x_{1},x_{2},\dots,x_{s},y_{1},y_{2},x_{s+1},\dots,x_{m})$ is an traversal of
$P$.

######  Lemma 4.1.

Let $X=(x_{1},x_{2},\dots,x_{m})$ be a maximally tall traversal of the
permutation matrix $P$. Then $X$ is non-extendable.

###### Proof.

Suppose $X$ is extendable. Then there exists an odd $s$ with $5\leq s\leq m-5$
and 1-entries $y_{1},y_{2}\in E(P)$ such that
$Y=(x_{1},x_{2},\dots,x_{s},y_{1},y_{2},x_{s+1},\dots,x_{m})$ is a traversal
of $P$. We show that then $P$ has an tall traversal of length $m+2$ with $X$
as a subsequence. This contradicts our assumption that $X$ is maximally tall.

Note that property (v) of $X$ implies that $x_{s+1}$ is above $x_{s}$. Further
using properties (ii), (iii), (iv) of $Y$, it follows that the relative
positions of $x_{s-1}$, $x_{s}$, $y_{1}$, $y_{2}$, $x_{s+1}$, and $x_{s+2}$
are fixed as shown in Figure 9.

$x_{s-1}$$x_{s+1}$$x_{s}$$x_{s+2}$$y_{1}$$y_{2}$ Figure 9: Arrangement of
$x_{s-1},x_{s},y_{1},y_{2},x_{s+1},x_{s+2}$ in Lemma 4.1. The shaded areas
must be empty, since $X$ is tall.

Let $y_{1}^{\prime}$ and $y_{2}^{\prime}$ be 1-entries in $P$ such that

  1. (a)

$y_{2}^{\prime}$ is to the left of $y_{1}^{\prime}$;

  2. (b)

$y_{1}^{\prime}$ is above or equal to $y_{1}$ and $y_{2}^{\prime}$ is below or
equal to $y_{2}$; and

  3. (c)

$\mathrm{d}^{\mathrm{v}}(y_{1}^{\prime},y_{2}^{\prime})$ is maximal under the
previous two conditions.

and let
$Y^{\prime}=(x_{1},x_{2},\dots,x_{s},y_{1}^{\prime},y_{2}^{\prime},x_{s+1},\dots,x_{m})$.
We first show that $Y^{\prime}$ is a traversal. $Y^{\prime}$ clearly satisfies
(i). Since $y_{1}^{\prime}$ is not below $y_{1}$, it is above $x_{s+1}$, so
tallness of $X$ implies that $y_{1}^{\prime}$ is to the left of $x_{s+2}$.
Symmetrically, $y_{2}^{\prime}$ is to the right of $x_{s-1}$, so (a) implies
$x_{s-1}<_{\mathrm{h}}y_{2}^{\prime}<_{\mathrm{h}}y_{1}^{\prime}<_{\mathrm{h}}x_{s+2}$,
and thus $Y^{\prime}$ satisfies (ii).

Since $x_{s-1}$ is to the left of $y_{1}^{\prime}$, tallness of $X$ implies
that $y_{1}^{\prime}$ is below $x_{s-1}$. We already observed that
$y_{1}^{\prime}$ is above $x_{s+1}$, so we have
$x_{s-1}<_{\mathrm{v}}y_{1}^{\prime}<_{\mathrm{v}}x_{s+1}$. Similarly, we have
$x_{s}<_{\mathrm{v}}y_{s}^{\prime}<_{\mathrm{v}}x_{s+2}$. Together with
$x_{s+1}<_{\mathrm{v}}x_{s}$, this implies the remaining traversal properties
(iii), (iv), (v).

It remains to show that $Y^{\prime}$ is tall. Suppose $Y$ violates tallness
property (vi). Since $X$ is tall, the only way this can happen is if there is
a 1-entry $z$ below $y_{2}^{\prime}$ and to the left of $y_{1}^{\prime}$. Then
$z$ is also below $y_{2}$, but
$\mathrm{d}^{\mathrm{v}}(y_{1}^{\prime},z)>\mathrm{d}^{\mathrm{v}}(y_{1}^{\prime},y_{2}^{\prime})$,
violating our assumption (c). A symmetric argument shows that $Y$ satisfies
(vii). ∎

###  4.3 Construction

Fix a $k\times k$ permutation matrix $P$. Throughout this subsection, we write
$\ell,b,t,r$ for $\ell_{P},b_{P},t_{P},r_{P}$. For a 1-entry $x=(i,j)\in
E(P)$, denote by $P^{\mathrm{L}}_{x}$ the submatrix of $P$ consisting of all
columns to the left of $x$ (i.e., the leftmost $j-1$ columns), and denote by
$P^{\mathrm{R}}_{x}$ the submatrix of $P$ consisting of all columns to the
right of $x$ (i.e., the rightmost $k-j$ columns). Note that in both
$P^{\mathrm{L}}_{x}$ and $P^{\mathrm{R}}_{x}$, the $i$-th row is empty. Also
note that the constructions in Sections 2 and 3 implicitly used
$P^{\mathrm{L}}_{x},P^{\mathrm{R}}_{x}$, with $x\in\\{\ell,r,q\\}$.

Let $X=(x_{1},x_{2},\dots,x_{m})$ be a traversal of $P$ with $m\geq 6$, and
write $(i_{s},j_{s})=x_{s}$ for $s\in[m]$. Then the $(2k-1)\times(m-2)k$
matrix $S(P,X)$ is constructed as follows. Let $L_{s}^{\prime}$ be the
$(2k-1)\times(j_{s}-1)$ matrix consisting of a copy of
$P^{\mathrm{L}}_{x_{s}}$ that is shifted down by $k-i_{s}$ rows (i.e., we
prepend $k-i_{s}$ rows and append $i_{s}-1$ rows to $P^{\mathrm{L}}_{x_{s}}$).
Similarly, let $R_{s}^{\prime}$ be the $(2k-1)\times(k-j_{s})$ matrix
consisting of a copy of $P^{\mathrm{R}}_{x_{s}}$ that is shifted down by
$k-i_{s}$ rows. Note that the empty $i_{s}$-th ($j_{s}$-th) row of
$P^{\mathrm{L}}_{x_{s}}$ ($P^{\mathrm{R}}_{x_{s}}$) corresponds to the $k$-th
row of $L_{s}^{\prime}$ ($R_{s}^{\prime}$). Finally, we define
$S^{\prime}(P,X)$ as the following horizontal concatenation of matrices:

$\displaystyle
S^{\prime}(P,X)=(L_{3}^{\prime},R_{1}^{\prime},L_{4}^{\prime},R_{3}^{\prime},L_{5}^{\prime},R_{4}^{\prime},\dots,L_{m-3}^{\prime},R_{m-4}^{\prime},L_{m-2}^{\prime},R_{m-3}^{\prime},L_{m}^{\prime},R_{m-2}^{\prime}).$

$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$$L_{3}^{\prime}$$R_{1}^{\prime}$$L_{4}^{\prime}$$R_{3}^{\prime}$$L_{6}^{\prime}$$R_{4}^{\prime}$
Figure 10: A matrix $P$ consisting of a 6-traversal $X$, and the corresponding
construction $S^{\prime}(P,X)$. Some empty columns in $S^{\prime}(P,X)$ have
been omitted. The dotted line indicates the expandable row.

Note the irregularities at the beginning and the end. Notably,
$L_{2}^{\prime},R_{2}^{\prime},L_{m-1}^{\prime},R_{m-1}^{\prime}$ are not used
in the construction. $L_{1}^{\prime}$ and $R_{m}^{\prime}$ are not used,
either, but they are empty anyway, since $x_{1}=\ell$ and $x_{m}=r$. See
Figure 10 for an example.

We claim that the $k$-th row of $S^{\prime}(P,X)$ is expandable. Indeed, for
each $i$ with $3\leq i\leq m-2$, adding a 1-entry in the $k$-th row between
$L_{i}^{\prime}$ and $R_{i}^{\prime}$ will complete a copy of $P$ with
$L_{i}^{\prime}$ and $R_{i}^{\prime}$. Moreover, adding a 1-entry in the
$k$-th row to the left of $R_{1}^{\prime}$ or to the right of $L_{m}^{\prime}$
will complete a copy of $P$.

As in the previous section, we will not directly use $S^{\prime}(P,X)$, but
rather a modified construction that preserves the expandable row. In the
following, we will slightly abuse notation by writing $L_{s}^{\prime}$
($R_{s}^{\prime}$) for the subsets of $E(S^{\prime}(P,X))$ that correspond to
$L_{s}^{\prime}$ ($R_{s}^{\prime}$).

Let $S(P,X)$ be a $((2m-6)k+1)\times(m-2)k$ matrix, constructed as follows.
Start with a copy of $S^{\prime}(P,X)$, shifted down by $(m-4)k$ rows, such
that the expandable $k$-th row of $S(P,X)$ corresponds to the $(m-3)k$-th row
of $S^{\prime}(P,X)$. Now, for each $s\in\\{5,6,\dots,m-1,m-2,m\\}$, take all
1-entries in $L_{s}^{\prime}\cup R_{s}^{\prime}$ that are above the
$((m-3)k-1)$-th row (i.e., at least two rows above the expandable row), and
move them up by $(s-4)k$ rows. Similarly, for each
$s\in\\{1,3,4,\dots,m-4\\}$, take all 1-entries in $L_{s}^{\prime}\cup
R_{s}^{\prime}$ that are below the $((m-3)k+1)$-th row (i.e., at least two
rows below the expandable row), and move them down by $(m-s-3)k$ rows. Figure
11 shows the rough structure of $S(P,X)$ when $m=12$ and $X$ is tall.

Let $L_{s}$ ($R_{s}$) denote the the modified set of entries in $S(P,X)$
corresponding to $L_{s}^{\prime}$ ($R_{s}^{\prime}$). Clearly, $L_{s}$ and
$R_{s}$ still form a partial occurrence of $P$ with a single 1-entry missing
between them in the $(m-3)k$-th row, and $R_{1}$, $L_{m}$ similarly form
occurrences when adding a 1-entry in the left- or rightmost part of that row.
Thus:

######  Lemma 4.2.

If $X$ is a traversal of $P$, then $S(P,X)$ has an expandable row.

Note that the construction used in Section 2 can be seen as a special case of
both $S(P,X)$ and $S^{\prime}(P,X)$ when $m=4$.

The rest of this section is dedicated to the proof that if $X$ is a non-
extendable tall traversal of a permutation matrix $P$, then $S(P,X)$ avoids
$P$, implying that $S(P,X)$ is a vertical witness of $P$. We first fix some
notation and make a few observations about $S(P,X)$. Let $T$ denote the set of
1-entries that are above row $(m-3)k-1$ (at least two rows above the
expandable row). Similarly, let $B$ denote the set of 1-entries that are below
row $(m-3)k+1$, and let $M$ denote the remaining 1-entries. For a subset
$A\subseteq E(S(P,X))$, let $A^{\mathrm{T}}=A\cap T$, let
$A^{\mathrm{B}}=A\cap B$ and let $A^{\mathrm{M}}=A\cap M$. For a 1-entry
$p\neq x_{s}$, let $p^{s}$ denote the copy of $p$ in $L_{s}\cup R_{s}$.

######  Observation 4.3.

Let $s,u\in\\{1,3,4,\dots,m-3,m-2,m\\}$ with $s<u$. If $u\geq 5$, then every
1-entry in $L_{s}^{\mathrm{T}}\cup R_{s}^{\mathrm{T}}$ is below every 1-entry
in $L_{u}^{\mathrm{T}}\cup R_{u}^{\mathrm{T}}$. Moreover, if $s\leq m-4$, then
every 1-entry in $L_{s}^{\mathrm{B}}\cup R_{s}^{\mathrm{B}}$ is below every
1-entry in $L_{u}^{\mathrm{B}}\cup R_{u}^{\mathrm{B}}$.∎

Since $X$ is tall, there are no 1-entries below and to the left of $x_{s}$ if
$s$ is odd, or above and to the right of $x_{s}$ if $s$ is even. This implies:

######  Observation 4.4.

$L_{s}^{\mathrm{B}}=\emptyset$ and $R_{s+1}^{\mathrm{T}}=\emptyset$ for each
odd $s$ with $3\leq s\leq m-3$.∎

We now consider the width and height of relevant parts of $S(P,X)$.

######  Observation 4.5.

For each $s\in\\{1,3,4,\dots,m-3,m-2,m\\}$,

  * •

$0pt(L_{s})=\mathrm{d}^{\mathrm{h}}(\ell,x_{s})-1$;

  * •

$0pt(R_{s})=\mathrm{d}^{\mathrm{h}}(x_{s},r)-1$;

  * •

$0pt(L_{s}^{\mathrm{T}}\cup
R_{s}^{\mathrm{T}})=\mathrm{d}^{\mathrm{v}}(t,x_{s})-2$, if
$L_{s}^{\mathrm{T}}\cup R_{s}^{\mathrm{T}}\neq\emptyset$;

  * •

$0pt_{\phi}(L_{s}^{\mathrm{M}}\cup R_{s}^{\mathrm{M}})\leq 1$; and

  * •

$0pt(L_{s}^{\mathrm{B}}\cup
R_{s}^{\mathrm{B}})=\mathrm{d}^{\mathrm{v}}(x_{s},b)-2$, if
$L_{s}^{\mathrm{B}}\cup R_{s}^{\mathrm{B}}\neq\emptyset$.∎

Let $3\leq s\leq m-3$ be odd. Since $X$ is tall, there are no 1-entries in $P$
above $x_{s-1}$ and to the right of $x_{s}$. Thus, $x_{s-1}^{s}$ is the
topmost 1-entry in $R_{s}$. Similarly, $x_{s+2}^{s+1}$ is the bottommost
1-entry in $L_{s+1}$. This implies the following improved bounds:

######  Observation 4.6.

For each odd $s\in\\{3,4,\dots,m-2\\}$:

  * •

$0pt(R_{s}^{\mathrm{T}})\leq\mathrm{d}^{\mathrm{v}}(x_{s-1},x_{s})-2$, if
$R_{s}^{\mathrm{T}}\neq\emptyset$; and

  * •

$0pt(L_{s+1}^{\mathrm{B}})\leq\mathrm{d}^{\mathrm{v}}(x_{s+1},x_{s+2})-2$, if
$L_{s+1}^{\mathrm{B}}\neq\emptyset$.∎

$R_{1}^{\mathrm{T}}$$R_{1}^{\mathrm{B}}$$L_{3}^{\mathrm{T}}$$R_{3}^{\mathrm{T}}$$R_{3}^{\mathrm{B}}$$L_{4}^{\mathrm{T}}$$L_{4}^{\mathrm{B}}$$R_{4}^{\mathrm{B}}$$L_{5}^{\mathrm{T}}$$R_{5}^{\mathrm{T}}$$R_{5}^{\mathrm{B}}$$L_{6}^{\mathrm{T}}$$L_{6}^{\mathrm{B}}$$R_{6}^{\mathrm{B}}$$L_{7}^{\mathrm{T}}$$R_{7}^{\mathrm{T}}$$R_{7}^{\mathrm{B}}$$L_{8}^{\mathrm{T}}$$L_{8}^{\mathrm{B}}$$R_{8}^{\mathrm{B}}$$L_{9}^{\mathrm{T}}$$R_{9}^{\mathrm{T}}$$R_{9}^{\mathrm{B}}$$L_{10}^{\mathrm{T}}$$L_{10}^{\mathrm{B}}$$R_{10}^{\mathrm{B}}$$L_{12}^{\mathrm{T}}$$L_{12}^{\mathrm{B}}$$M$$M$
Figure 11: A sketch of the block structure of $S(P,X)$ with $|X|=12$.

###  4.4 $S(P,X)$ avoids $P$

In this section, we show:

######  Lemma 4.7.

Let $P$ be a permutation matrix, $m\geq 6$ be even and let
$X=(x_{1},x_{2},\dots,x_{m})$ be a non-extendable tall traversal of $P$. Then
$S(P,X)$ avoids $P$.

Together with Lemmas 4.1 and 4.2, this implies Lemma 1.13. For the remainder
of this section, fix $P$ and $X$ as in Lemma 4.7, and write $\ell,b,t,r$ for
$\ell_{P},b_{P},t_{P},r_{P}$. We use the same notation for parts of $S(P,X)$
as defined in Section 4.3. Suppose $\phi$ is an embedding of $P$ into
$S(P,X)$. Our overall strategy is to distinguish cases based on the location
of $\phi(t)$, and derive a contradiction in each case.

Note that we make no further assumptions on $P,X,\phi$, so each lemma or
corollary in this section holds on its own for every choice of $P,X,\phi$ (we
only fix $P,X,\phi$ for brevity). This allows us to make use of the following
_symmetry_ argument. Note that $S(P,X)$ is usually not symmetric, in the sense
that its 180-degree rotation $\mathrm{rot}^{2}(S(P,X))$ is equal to $S(P,X)$.
However, it is easy to see that $\mathrm{rot}^{2}(S(P,X))$ is equal to
$S(\mathrm{rot}^{2}(P),\mathrm{rot}^{2}(X))$. Now, in Lemma 4.8, for example,
we show that $\phi(t)\notin L_{3}$ for each choice of $P,X,\phi$, in
particular for $\mathrm{rot}^{2}(P),\mathrm{rot}^{2}(X)$ and every embedding
$\phi^{\prime}$ of $\mathrm{rot}^{2}(P)$ into $\mathrm{rot}^{2}(S(P,X))$.
Since $L_{3}$ in
$S(\mathrm{rot}^{2}(P),\mathrm{rot}^{2}(X))=\mathrm{rot}^{2}(S(P,X))$
corresponds to $R_{m-2}$ in $S(P,X)$, $t$ in $\mathrm{rot}^{2}(P)$ corresponds
to $b$ in $P$, and $\phi$ corresponds to some embedding $\phi^{\prime}$, we
also have $\phi(b)\notin R_{m-2}$.

####  4.4.1 $\phi(t)$ in the front or the back

We first consider some special cases, showing that $\phi(t)$ cannot lie in the
leftmost few “blocks” of $S(P,X)$, and symmetric statements for $\phi(b)$. The
proofs in this section also serve as a warm-up for what follows.

######  Lemma 4.8.

$\phi(t)\notin L_{3}$ and $\phi(b)\notin R_{m-2}$.

###### Proof.

By symmetry, it suffices to show $\phi(t)\notin L_{3}$. Suppose $\phi(t)\in
L_{3}$. Then also $\phi(\ell)\in L_{3}$, since $S(P,X)$ contains no 1-entries
to the left of $L_{3}$. But
$0pt(L_{3})=\mathrm{d}^{\mathrm{h}}(\ell,x_{3})-1<\mathrm{d}^{\mathrm{h}}(\ell,t)-1$,
thus we cannot have both $\phi(\ell)$ and $\phi(t)$ in $L_{3}$, a
contradiction. ∎

######  Lemma 4.9.

$\phi(t)\notin R_{1}$ and $\phi(b)\notin L_{m}$.

###### Proof.

By symmetry, it suffices to show $\phi(t)\notin R_{1}$. Suppose $\phi(t)\in
R_{1}$. Note that $0pt_{\phi}(R_{1}^{\mathrm{T}}\cup
R_{1}^{\mathrm{M}})\leq\mathrm{d}^{\mathrm{v}}(t,\ell)<\mathrm{d}^{\mathrm{v}}(t,x_{3})$,
so $\phi(x_{3})\in B$. Since $x_{3}$ is to the right of $t$ and
$L_{3}^{\mathrm{B}}=\emptyset$, we have $\phi(x_{3})\in R_{1}^{\mathrm{B}}$.
Since $r$ is below $x_{3}$, and all 1-entries in $S(P,X)$ that are to the
right of $R_{1}$ are above $R_{1}^{\mathrm{B}}$, we have $\phi(r)\in
R_{1}^{\mathrm{B}}$. Since $0pt(R_{1})<\mathrm{d}^{\mathrm{h}}(\ell,r)$, this
implies that $\phi(\ell)$ is to the left of $R_{1}$. But since $t\in R_{1}$
and the highest 1-entry $t^{1}$ of $R_{1}$ is at most
$\mathrm{d}^{\mathrm{h}}(t,\ell)$ rows above the expandable row, $\phi(\ell)$
must be below the expandable row. This is a contradiction, since there are no
1-entries to the left of $R_{1}$ and below the expandable row. ∎

If $m=6$ (see Figure 12), then the only remaining possibility is
$\phi(t),\phi(b)\in L_{4}\cup R_{3}$, which implies $\phi(t)\in L_{4}$ or
$\phi(b)\in R_{3}$ (since $t$ is to the left of $b$). Thus, the following
lemma concludes the case $m=6$.

$R_{1}^{\mathrm{T}}$$R_{1}^{\mathrm{B}}$$L_{3}^{\mathrm{T}}$$R_{3}^{\mathrm{T}}$$R_{3}^{\mathrm{B}}$$L_{4}^{\mathrm{T}}$$L_{4}^{\mathrm{B}}$$R_{4}^{\mathrm{B}}$$L_{6}^{\mathrm{T}}$$L_{6}^{\mathrm{B}}$$M$$M$
Figure 12: A sketch of the block structure of $S(P,X)$ with $|X|=6$.

######  Lemma 4.10.

If $m=6$, then $\phi(t)\notin L_{4}$ and $\phi(b)\notin R_{3}$.

###### Proof.

By symmetry, it suffices to show $\phi(t)\notin L_{4}$. This can be done with
essentially the same argument as in the proof of Lemma 2.1. Suppose
$\phi(t)\in L_{4}$. Then $\phi(t)$ is not above $t^{4}\in L_{4}$. By Lemmas
4.8 and 4.9, $\phi(b)\in L_{4}\cup R_{3}$. The lowest 1-entry in $L_{4}\cup
R_{3}$ is $b^{4}$, so $\phi(b)$ is not below $b^{4}$. But
$\mathrm{d}^{\mathrm{v}}_{\phi}(t^{4},b^{4})<\mathrm{d}^{\mathrm{v}}(t,b)$
(note the empty expandable row), a contradiction. ∎

We now continue with the case $m\geq 8$.

######  Lemma 4.11.

If $m\geq 8$, then $\phi(t)\notin L_{4}$ and $\phi(b)\notin R_{m-3}$.

###### Proof.

By symmetry, it suffices to show $\phi(t)\notin L_{4}$. Suppose $\phi(t)\in
L_{4}$. We have $0pt_{\phi}(L_{4}^{\mathrm{T}}\cup
L_{4}^{\mathrm{M}})\leq\mathrm{d}^{\mathrm{v}}(t,x_{4})<\mathrm{d}^{\mathrm{v}}(t,x_{3})$,
implying $x_{3}\in B$. Since $x_{3}$ is to the left of $t$, this means that
$\phi(x_{3})\in R_{1}^{\mathrm{B}}\cup L_{4}^{\mathrm{B}}$. If $\phi(x_{3})\in
R_{1}^{\mathrm{B}}$, then also $\phi(r)\in R_{1}^{\mathrm{B}}$, but then
$\phi(r)$ is to the left of $\phi(t)$, which is impossible. Thus, we have
$\phi(x_{3})\in L_{4}^{\mathrm{B}}$.

This implies that $\phi(r)\in L_{4}^{\mathrm{B}}\cup R_{3}^{\mathrm{B}}\cup
R_{4}^{\mathrm{B}}$. As such, $\phi$ maps no 1-entry of $P$ to the right of
$R_{4}$, and thus $\phi$ maps no 1-entry into the rows below $M$ and above
$L_{4}^{\mathrm{B}}\cup R_{4}^{\mathrm{B}}$. If now $\phi(x_{3})$ is above or
equal to $x_{3}^{4}$, then
$\mathrm{d}^{\mathrm{v}}_{\phi}(\phi(t),\phi(x_{3}))\leq\mathrm{d}^{\mathrm{v}}_{\phi}(t^{4},x_{3}^{4})<\mathrm{d}^{\mathrm{v}}(t,x_{3})$
(note the empty expandable row), a contradiction. Thus, $\phi(x_{3})$ must be
below $x_{3}^{4}$. By tallness of $X$, this also implies that $x_{3}$ is to
the right of $x_{3}^{4}$, and $\phi(t)$ is to the right of $t^{4}$, since $t$
is to the right of $x_{3}$ and
$\mathrm{d}^{\mathrm{h}}(t^{4},x_{3}^{4})=\mathrm{d}^{\mathrm{h}}(t,x_{3})$.
Similarly, $\phi(x_{4})$ is to the right of $L_{4}$.

Consider now $\phi(x_{5})$. Since $\phi(x_{3})$ is below $x_{3}^{4}$ and
$x_{5}^{4}$ is the bottommost 1-entry in $L_{4}^{\mathrm{B}}$, we know that
$\phi(x_{5})$ is below $L_{4}^{\mathrm{B}}$. This implies $\phi(x_{5})\in
R_{3}^{\mathrm{B}}\cup R_{4}^{\mathrm{B}}$. Suppose $\phi(x_{5})\in
R_{4}^{\mathrm{B}}$. Then also $\phi(r)\in R_{4}^{\mathrm{B}}$. But
$0pt(R_{4})=\mathrm{d}^{\mathrm{h}}(x_{4},r)-1<\mathrm{d}^{\mathrm{h}}(x_{5},r)$,
a contradiction. Thus, $\phi(x_{5})\in R_{3}^{\mathrm{B}}$. This implies
$\phi(b),\phi(r)\in R_{3}^{\mathrm{B}}$, and $\phi(x_{4})\in R_{3}$.

Recall that $\phi(t)\in L_{4}\setminus\\{t^{4}\\}$, so $t$ is below $t^{4}$.
As $0pt_{\phi}(L_{4}^{\mathrm{T}}\cup M)\leq\mathrm{d}^{\mathrm{v}}(t,x_{4})$,
this means that $\phi(x_{4})\in R_{3}^{\mathrm{B}}$. But
$0pt(R_{3}^{\mathrm{B}})=\mathrm{d}^{\mathrm{v}}(x_{3},b)-2<\mathrm{d}^{\mathrm{v}}(x_{4},b)$,
a contradiction. ∎

######  Lemma 4.12.

Let $m\geq 8$. If $\phi(t)\in R_{3}$, then $\phi(b)$ is to the right of
$R_{4}$. Moreover, if $\phi(b)\in L_{m-2}$, then $\phi(t)$ is to the left of
$L_{m-3}$.

###### Proof.

By symmetry, proving the first statement suffices. Let $\phi(t)\in R_{3}$ and
suppose $\phi(b)$ is not to the right of $R_{4}$. The portion of $R_{3}$ above
the expandable row has height at most $\mathrm{d}^{\mathrm{v}}(t,x_{3})-1$, so
$\phi(x_{3})$ must lie below the expandable row. Let $q_{3}$ be the 1-entry
directly below $x_{3}$ in $P$. Clearly, $\phi(q_{3}),\phi(b),\phi(r)\in B$,
and since $\phi(b)$ is to the right of $R_{4}$, we have $\phi(b)\in
R_{3}^{\mathrm{B}}\cup R_{4}^{\mathrm{B}}$. We separately consider three
cases.

  1.  _Case_ 1:

$\phi(r)\in R_{3}^{\mathrm{B}}$, Since $X$ is tall, $q_{3}$ is to the right of
$t$, so $\phi(q_{3})\in R_{3}^{\mathrm{B}}$. But
$0pt(R_{3}^{\mathrm{B}})=\mathrm{d}^{\mathrm{v}}(x_{3},b)-2=\mathrm{d}^{\mathrm{v}}(q_{3},b)-1$,
a contradiction.

  2.  _Case_ 2:

$\phi(r)\in R_{4}^{\mathrm{B}}$. Consider $x_{5}$. Since $x_{5}$ is below
$x_{3}$, we have $\phi(x_{5})\in B$. Since $x_{5}$ is to the right of $t$, and
above and to the left of $r$, we have $\phi(x_{5})\in R_{4}^{\mathrm{B}}$. But
$0pt(R_{4})=\mathrm{d}^{\mathrm{h}}(x_{4},r)-1<\mathrm{d}^{\mathrm{h}}(x_{5},r)$,
a contradiction.

  3.  _Case_ 3:

$\phi(r)$ is to the right of $R_{4}$. Then $\phi(r)$ is also above
$L_{4}^{\mathrm{B}}\cup R_{4}^{\mathrm{B}}$. Consider again $x_{5}$. We know
that $\phi(x_{5})$ is below $M$ and above $L_{4}^{\mathrm{B}}\cup
R_{4}^{\mathrm{B}}$. Since $x_{5}$ is to the left of $b$, we also know that
$\phi(x_{5})$ is not to the right of $R_{4}$. But there are no such 1-entries
in $S(P,X)$.∎

We proceed with some more special cases, showing that $\phi(t)$ also cannot
lie in the rightmost few blocks of $S(P,X)$.

######  Lemma 4.13.

Let $m\geq 8$. Then, $\phi(t)$ lies to the left of $L_{m-2}$, and $\phi(b)$
lies to the right of $R_{3}$.

###### Proof.

By symmetry, it suffices to prove that $\phi(t)$ lies to the left of
$L_{m-2}$. If $\phi(b)$ lies to the left of $L_{m-2}$, then $\phi(t)$ does,
too. $\phi(b)\notin R_{m-3}\cup L_{m}\cup R_{m-2}$ by Lemmas 4.8, 4.9, and
4.11. The only remaining possibility is that $\phi(b)\in L_{m-2}$, where Lemma
4.12 implies that $\phi(t)$ lies to the left of $L_{m-3}$, and thus to the
left of $L_{m-2}$. ∎

To show that $\phi(t)\notin L_{m-3}\cup R_{m-4}$, we use the following more
general lemma, to be used in later sections. Figures 11 and 13 are useful to
visualize the proof.

######  Lemma 4.14.

Let $s$ be odd with $5\leq s\leq m-3$. If $\phi(t)\in L_{s}\cup R_{s-1}$, then
$\phi(b)$ lies to the right of $R_{s-1}$.

###### Proof.

Suppose not. Then, $\phi(b)\in L_{s}\cup R_{s-1}$.

  1.  _Case_ 1:

$\phi(\ell)\notin L_{s}\cup R_{s-1}$. Since $\ell$ is to the left of $t$, this
means that $\phi(\ell)$ is to the left of $L_{s}$. This implies that
$\phi(\ell)$ is also below $L_{s}^{\mathrm{T}}$, and thus $\phi(x_{4})$ is
below $L_{s}^{\mathrm{T}}$. Since $x_{4}$ is to the right of $t$, we have
$\phi(x_{4})\in M\cup B$, which implies $\phi(x_{5})\in B$, as
$0pt_{\phi}(M)\leq 1<\mathrm{d}^{\mathrm{v}}(x_{4},x_{5})$. Since $x_{5}$ is
to the right of $t$ and to the left of $b$, we further know $\phi(x_{5})\in
R_{s-1}^{\mathrm{B}}$. Since $0pt(R_{s-1})<\mathrm{d}^{\mathrm{h}}(x_{5},r)$,
this implies that $\phi(r)$ is to the right of $R_{s-1}$. But then $\phi(r)$
is above $\phi(x_{5})$, a contradiction.

  2.  _Case_ 2:

$\phi(\ell)\in L_{s}\cup R_{s-1}$. Then $\phi$ maps no 1-entry to the left of
$L_{s}$. It is easy to see that there must be some $y\in E(P)$ such that
$\phi(y)\in R_{s}^{\mathrm{T}}$, otherwise $P$ is decomposable (more
precisely, $P=\left(\begin{smallmatrix}A&\mathbf{0}\\\
\mathbf{0}&B\end{smallmatrix}\right)$, where $\phi(E(A))\subseteq L_{s}$).
Since $\phi(b)\in L_{s}\cup R_{s-1}$, we know that $b$ is to the left of $y$.
Tallness of $X$ implies that $y$ is not above $x_{m-2}$. now consider
$x_{s-1}$. We know $x_{s-1}\leq_{\mathrm{h}}x_{m-4}<_{\mathrm{h}}b$ and
$x_{s-1}\leq_{\mathrm{v}}x_{m-4}<_{\mathrm{v}}x_{m-2}\leq_{\mathrm{v}}y$.
Thus, $\phi(x_{s-1})\in L_{s}^{\mathrm{T}}$. But
$0pt(L_{s}^{\mathrm{T}})<\mathrm{d}^{\mathrm{v}}(\ell,x_{s})<\mathrm{d}^{\mathrm{v}}(\ell,x_{s-1})$,
a contradiction.∎

######  Corollary 4.15.

If $m\geq 8$, then $\phi(t)\notin L_{m-3}\cup R_{m-4}$ and $\phi(b)\notin
L_{5}\cup R_{4}$.

###### Proof.

By symmetry, it suffices to prove that $\phi(t)\notin L_{m-3}$. Suppose
$\phi(t)\in L_{m-3}$. By Lemmas 4.8, 4.9, 4.11, and 4.12, $\phi(b)$ cannot lie
in $L_{m-2}$ or further left. This contradicts Lemma 4.14. ∎

We now consolidate and reformulate the above results. For the more involved
proofs in Sections 4.4.2 and 4.4.3, it will be convenient to organize the
“middle” blocks $L_{i},R_{i}$ of $S(P,X)$ into two sets of _groups_ , as
follows. For each odd $s$ with $5\leq s\leq m-5$, let $G_{s}=L_{s}\cup
R_{s-1}\cup L_{s+1}\cup R_{s}$, and let $H_{s}=L_{s+1}\cup R_{s}\cup
L_{s+2}\cup R_{s+1}$. A sketch of $G_{s}$ and $H_{s}$ can be found in Figure
13. Combining Lemmas 4.8, 4.9, 4.11, 4.13, and 4.15 yields:

######  Corollary 4.16.

If $m\geq 8$, then:

  * •

$\phi(t)$ lies to the right of $L_{4}$ and to the left of $L_{m-3}$. In other
words, $\phi(t)\in R_{3}$ or $\phi(t)\in G_{s}$ for some odd $s$ with $5\leq
s\leq m-5$; and

  * •

$\phi(b)$ lies to the right of $R_{4}$ and to the left of $R_{m-3}$. In other
words, $\phi(b)\in L_{m-2}$ or $\phi(b)\in H_{s}$ for some odd $s$ with $5\leq
s\leq m-5$.

At this stage, we cannot easily show that both $\phi(t)\notin R_{3}$ and
$\phi(b)\notin L_{m-2}$, but we can show that at least one of the two must be
true.

######  Lemma 4.17.

If $m\geq 8$, then $\phi(t)\notin R_{3}$ or $\phi(b)\notin L_{m-2}$

###### Proof.

Suppose $\phi(t)\in R_{3}$ and $\phi(b)\in L_{m-2}$. Since
$0pt(R_{3}^{\mathrm{T}})<\mathrm{d}^{\mathrm{v}}(t,x_{3})$, we have
$\phi(x_{3})\in M$, implying $\phi(x_{5})\in B$. More precisely, since $b\in
L_{m-2}$, we have $\phi(x_{5})\in L_{m-2}^{\mathrm{B}}\cup
R_{m-3}^{\mathrm{B}}\cup L_{m}^{\mathrm{B}}\cup R_{m-2}^{\mathrm{B}}$.
Similarly, $\phi(x_{m-2})\in T\cup M$, implying $\phi(x_{m-4})\in
L_{3}^{\mathrm{T}}\cup R_{1}^{\mathrm{T}}\cup L_{4}^{\mathrm{T}}\cup
R_{3}^{\mathrm{T}}$. In particular, $\phi(x_{5})$ is to the right of
$\phi(x_{m-4})$. But $x_{5}<_{\mathrm{h}}x_{4}\leq_{\mathrm{h}}x_{m-4}$, a
contradiction. ∎

Note that Corollaries 4.16 and 4.17 completely resolve the case $m=8$.

In the following two subsections, we show that the remaining possibilities
also lead to a contradiction. In Section 4.4.2 we treat the easier case, where
$\phi(t)\in G_{s}$ for some odd $s$ with $5\leq s\leq m-5$, and $\phi(b)$ is
to the right of $R_{s+1}$ (i.e., to the right of $H_{s}$). This also handles
the symmetric case where $\phi(b)\in H_{s}$ and $\phi(t)$ is to the left of
$G_{s}$. In Section 4.4.3, we consider the case where $\phi(t)\in G_{s}$ and
$\phi(b)\in H_{s}$.

$L_{s}^{\mathrm{T}}$$L_{s+1}^{\mathrm{T}}$$R_{s}^{\mathrm{T}}$$L_{s+2}^{\mathrm{T}}$$G_{s}$$R_{s-1}^{\mathrm{B}}$$L_{s+1}^{\mathrm{B}}$$R_{s}^{\mathrm{B}}$$R_{s+1}^{\mathrm{B}}$$H_{s}$$\ell$$x_{3}$$t$$x_{5}$$x_{4}$$x_{s}$$x_{s-1}$$x_{s+2}$$x_{s+1}$$x_{m-3}$$x_{m-4}$$b$$x_{m-2}$$r$
Figure 13: _(left)_ A sketch of parts of $S(P,X)$. Here, $s$ is odd and $5\leq
s\leq m-5$. The dashed lines and open rectangles indicate $M$ and the rest of
$S(P,X)$. _(right)_ Sketches of three not necessarily disjoint parts of $P$.
The solid lines illustrate tallness.

####  4.4.2 $\phi(t)$, $\phi(b)$ in the middle and far from each other

The following lemma is central to this subsection.

######  Lemma 4.18.

For each odd $s$ with $5\leq s\leq m-5$, if $\phi(t)\in G_{s}$ and $\phi(b)$
is to the right of $R_{s+1}$, then $\phi(x_{s})$ is below the expandable row.

###### Proof.

We consider the following cases:

  1.  _Case_ 1:

$\phi(t)\notin L_{s}\cup L_{s+1}\cup R_{s}$. Then $\phi(t)\in R_{s-1}$, so
$\phi(t)$ is below the expandable row, implying the same for $\phi(x_{s})$.

  2.  _Case_ 2:

$\phi(\ell)\notin L_{s}\cup L_{s+1}\cup R_{s}$. Then $\phi(\ell)$ is below
$L_{s}^{\mathrm{T}}\cup R_{s}^{\mathrm{T}}$. Since $x_{4}$ is to the right of
$t$ and below $\ell$, this implies that $x_{4}\in M\cup B$, and thus
$\phi(x_{s})$ is below the expandable row.

  3.  _Case_ 3:

$\phi(t),\phi(\ell)\in L_{s}\cup R_{s}$. Since $\phi$ does not map any 1-entry
to a position below $L_{s}^{\mathrm{T}}\cup R_{s}^{\mathrm{T}}$ and above $M$,
we have $0pt_{\phi}(L_{s}^{\mathrm{T}}\cup L_{s}^{\mathrm{M}}\cup
R_{s}^{\mathrm{T}}\cup
R_{s}^{\mathrm{M}})\leq\mathrm{d}^{\mathrm{v}}(t,x_{s})$. Thus, $\phi(x_{s})$
is either below $M$ or in the bottom row of $M$, so $\phi(x_{s})$ is below the
expandable row.

  4.  _Case_ 4:

$\phi(t)\in L_{s+1}$ and $\phi(\ell)\in L_{s}$. Since $x_{4}$ is below $\ell$
and to the right of $t$, we have $\phi(x_{4})\in M\cup B$ or $\phi(x_{4})\in
R_{s}^{\mathrm{T}}$. In the former case, we are done, as above. Otherwise,
note that $\phi$ does not map any 1-entry of $P$ into a row below
$R_{s}^{\mathrm{T}}$ and above $M$, thus $0pt_{\phi}(R_{s}^{\mathrm{T}}\cup
R_{s}^{\mathrm{M}})=\mathrm{d}^{\mathrm{v}}(x_{s-1},x_{s})\leq\mathrm{d}^{\mathrm{v}}(x_{4},x_{s})$.
This implies that $\phi(x_{s})$ is below the expandable row.

  5.  _Case_ 5:

$\phi(t),\phi(\ell)\in L_{s+1}$ and $\phi(x_{s})\notin L_{s+1}$. Since $x_{s}$
is to the right of $t$, this means that $\phi(x_{s})$ is to the right of
$L_{s+1}$. Suppose $x_{s}$ is above the expandable row. Tallness of $X$
implies that there are no 1-entries in $P$ that are below and to the left of
$x_{s}$, so $\phi$ maps no 1-entry to $L_{s+1}^{\mathrm{M}}\cup
L_{s+1}^{\mathrm{B}}$. But then $\phi$ maps every 1-entry of $P$ either to
$L_{s+1}^{\mathrm{T}}$ or to the left and below $L_{s+1}^{\mathrm{T}}$, and
both possibilities occur (e.g., with $t$ resp. $b$). This means that $P$ is
decomposable, a contradiction.

  6.  _Case_ 6:

$\phi(t),\phi(\ell),\phi(x_{s})\in L_{s+1}$. Suppose $\phi(x_{s})$ is above
the expandable row. Since
$0pt(L_{s+1}^{\mathrm{T}})<\mathrm{d}^{\mathrm{v}}(t,x_{s})$, we know that
$\phi(x_{s})$ is below $L_{s+1}^{\mathrm{T}}$, so $\phi(x_{s})\in
L_{s+1}^{\mathrm{M}}$.

$x_{s+1}$ is above and to the right of $x_{s}$, implying that
$\phi(x_{s+1})\in L_{s+1}^{\mathrm{T}}\cup R_{s}^{\mathrm{T}}$. Further,
$x_{s+2}$ is below $x_{s}$, so $\phi(x_{s+2})\in M\cup B$, and
$x_{s}<_{\mathrm{h}}x_{s+2}<_{\mathrm{h}}x_{s+1}$, so $\phi(x_{s+2})\in
L_{s+1}\cup R_{s}$. Since $\phi(b)$ is to the right of $R_{s+1}$, we know that
$\phi$ maps no 1-entry to $L_{s+1}^{\mathrm{B}}\cup R_{s}^{\mathrm{B}}$. Thus,
$\phi(x_{s+2})\in L_{s+1}^{\mathrm{M}}\cup R_{s}^{\mathrm{M}}$.

But now $\phi(x_{s}),\phi(x_{s+2})\in M$, so $\phi$ maps no further 1-entries
to $M$. Therefore, $\phi$ maps every 1-entry either to
$A=L_{s+1}^{\mathrm{T}}\cup L_{s+1}^{\mathrm{M}}\cup R_{s}^{\mathrm{T}}\cup
R_{s}^{\mathrm{M}}$, or below and to the right of $A$ (and $\phi(t)\in A$,
$\phi(b)\notin A$). This means $P$ is decomposable, a contradiction.∎

We first consider a simple special case.

######  Lemma 4.19.

If $\phi(t)\in G_{s}$ for some odd $s$ with $5\leq s\leq m-5$, then
$\phi(b)\notin L_{m-2}$.

Moreover, if $\phi(b)\in H_{s}$ for some odd $s$ with $5\leq s\leq m-5$, then
$\phi(t)\notin R_{3}$.

###### Proof.

By symmetry, it suffices to show the first statement. Suppose $\phi(b)\in
L_{m-2}$. Then, $\phi(b)$ is to the right of $R_{m-4}$, and thus to the right
of $R_{s+1}$, so Lemma 4.18 implies that $\phi(x_{s})$ is below the expandable
row. Since $x_{s}$ is to the left and above $b$, we have $\phi(x_{s})\in
L_{m-2}$. Since $x_{s}<_{\mathrm{h}}x_{s+1}<_{\mathrm{h}}b$, and $x_{s+1}$ is
below $t$, we have $\phi(x_{s+1})\in L_{m-2}^{\mathrm{M}}\cup
L_{m-2}^{\mathrm{B}}$. But $0pt_{\phi}(L_{m-2}^{\mathrm{M}}\cup
L_{m-2}^{\mathrm{B}})\leq\mathrm{d}^{\mathrm{v}}(x_{m-2},b)<\mathrm{d}^{\mathrm{v}}(x_{m-4},b)\leq\mathrm{d}^{\mathrm{v}}(x_{s+1},b)$,
a contradiction. ∎

We proceed with the case that $\phi(t)\in G_{s}$ and $\phi(b)\in H_{u}$ for
some $5\leq s<u\leq m-5$.

######  Lemma 4.20.

Let $s,u$ be odd such that $5\leq s<u\leq m-5$. If $\phi(t)\in G_{s}$, then
$\phi(b)\notin H_{u}$.

###### Proof.

Suppose $\phi(b)\in H_{u}$. Note that this means that $\phi$ maps no 1-entry
to $G_{s}\cap B$ or $H_{u}\cap T$. We start by establishing a few facts about
$\phi(x_{s})$, $\phi(r)$, and $\phi(x_{u+1})$.

Lemma 4.18 implies that $\phi(x_{s})$ is below the expandable row. Since
$x_{u}$ is below $x_{s}$, we have $\phi(x_{u})\in B$.

We claim that $\phi(r)\in H_{u}$. Suppose not, then $\phi(r)$ must be to the
right of $H_{u}$, and thus above $L_{u+1}^{\mathrm{B}}\cup
R_{u+1}^{\mathrm{B}}$. Since $x_{u}$ is above $r$ and to the left of $b$, we
have that $\phi(x_{u})$ is above $L_{u+1}^{\mathrm{B}}\cup
R_{u+1}^{\mathrm{B}}$ and not to the right of $H_{u}$. But then
$\phi(x_{u})\in T\cup M$, contradicting our previous observation.

Further, $\phi(x_{u})\in B$ and $\phi(b),\phi(r)\in H_{u}$ imply
$\phi(x_{u})\in H_{u}$, and thus $\phi(x_{u-1})\in H_{u}$. This means that
$\phi(x_{u-1})\in M\cup B$ (as $\phi$ maps nothing to $H_{u}\cap T$), and thus
$\phi(x_{u+1})$ is below the expandable row.

We distinguish between the following cases:

  1.  _Case_ 1:

$\phi(b),\phi(r)\in L_{u+1}\cup R_{u+1}$. Note that $\phi$ does not map any
1-entries to the rows between $M$ and $L_{u+1}^{\mathrm{B}}\cup
R_{u+1}^{\mathrm{B}}$. Thus, $0pt_{\phi}(L_{u+1}^{\mathrm{M}}\cup
L_{u+1}^{\mathrm{B}}\cup R_{u+1}^{\mathrm{M}}\cup
R_{u+1}^{\mathrm{B}})\leq\mathrm{d}^{\mathrm{v}}(x_{u+1},b)$, contradicting
the fact that $\phi(x_{u+1})$ is below the expandable row.

  2.  _Case_ 2:

$\phi(b),\phi(r)\in R_{u}$. Since
$0pt(R_{u}^{\mathrm{B}})<\mathrm{d}^{\mathrm{v}}(x_{u},b)<\mathrm{d}^{\mathrm{v}}(x_{u+1},b)$,
we have $\phi(x_{u+1})$ above $R_{u}^{\mathrm{B}}$.

Suppose first that $\phi(x_{u+1})\in L_{u+1}^{\mathrm{B}}\cup
L_{u+1}^{\mathrm{M}}$. Note that no 1-entry in $M$ is below $\phi(x_{u+1})$.
Thus, tallness of $X$ implies that $\phi$ maps no 1-entry to
$R_{u}^{\mathrm{M}}$. But then $\phi$ maps all 1-entries to
$R_{u}^{\mathrm{B}}$ or above and to the left of $R_{u}^{\mathrm{B}}$ (and
$\phi(b)\in R_{u}^{\mathrm{B}}$, $\phi(t)\notin R_{u}^{\mathrm{B}}$), so $P$
is decomposable, a contradiction.

Second, suppose that $\phi(x_{u+1})\in R_{u}^{\mathrm{M}}$. Since $x_{u-1}$ is
above $x_{u+1}$, this also implies that $\phi(x_{u-1})\in
L_{u+1}^{\mathrm{M}}\cup R_{u}^{\mathrm{M}}$. Note that $\phi$ maps no further
1-entries to $M$, and $\phi(x_{u-1}),\phi(x_{u+1})\in L_{u+1}\cup R_{u}$. But
this means that $\phi$ maps all 1-entries either to $L_{u+1}^{\mathrm{B}}\cup
L_{u+1}^{\mathrm{M}}\cup R_{u}^{\mathrm{B}}\cup R_{u}^{\mathrm{M}}$ or above
and to the left of that entry set, again contradicting that $P$ is
indecomposable.

  3.  _Case_ 3:

$\phi(b)\in R_{u}$ and $\phi(r)\in R_{u+1}$. Since $x_{u+2}$ is above $r$ and
to the left of $b$, we know that $\phi(x_{u+2})$ is above and not to the right
of $R_{u}^{\mathrm{B}}$. Since $\phi(x_{s})$ is below the expandable row and
$x_{u+2}$ is below $x_{s}$, we have $\phi(x_{u+2})\in B$, implying
$\phi(x_{u+2})\in L_{u+1}^{\mathrm{B}}$. Since $\phi(r)\in R_{u+1}$, we know
that $\phi$ maps no 1-entries into the rows between $M$ and
$L_{u+1}^{\mathrm{B}}\cup R_{u+1}^{\mathrm{B}}$. This implies that
$0pt_{\phi}(L_{u+1}^{\mathrm{M}}\cup
L_{u+1}^{\mathrm{B}})\leq\mathrm{d}^{\mathrm{v}}(x_{u+1},x_{u+2})$. But
$\phi(x_{u+1})$ is below the expandable row, a contradiction.∎

Lemmas 4.19 and 4.20 together with Corollaries 4.16 and 4.17 imply:

######  Corollary 4.21.

There is some odd $s$ with $5\leq s\leq m-5$ such that $\phi(t)\in G_{s}$ and
$\phi(b)\in H_{s}$.

###### Proof.

Suppose first that $\phi(t)\in R_{3}$. Then Corollaries 4.16 and 4.17 imply
that $\phi(b)\in H_{s}$ for some odd $s$ with $5\leq s\leq m-5$. But then
Lemma 4.19 implies that $\phi(t)\notin R_{3}$, a contradiction. A similar
argument shows that $\phi(b)\notin L_{m-2}$.

As such, there are odd $s,u$ with $5\leq s,u\leq m-5$ such that $\phi(t)\in
G_{s}$ and $\phi(b)\in H_{u}$. Clearly, $s\leq u$, and Lemma 4.20 implies that
$s\geq u$, so $s=u$. ∎

####  4.4.3 $\phi(t)$, $\phi(b)$ in the middle and close to each other

In this subsection, we show that Corollary 4.21 also leads to a contradiction,
which shows that our assumption that $S(P,X)$ contains $P$ must have been
false. Figure 13 will be useful throughout this subsection. The next two
lemmas treat the case that $\phi(t)\in L_{s}$ (or, symmetrically, $\phi(b)\in
R_{s+1}$).

######  Lemma 4.22.

Let $s$ be odd and $5\leq s\leq m-5$. If $\phi(t)\in L_{s}$, then
$\phi(\ell)\in L_{s}^{\mathrm{T}}$. Moreover, if $\phi(b)\in R_{s+1}$, then
$\phi(r)\in R_{s+1}$.

###### Proof.

By symmetry, it suffices to prove the first statement. Suppose $\phi(t)\in
L_{s}$ and $\phi(\ell)\notin L_{s}^{\mathrm{T}}$. Then $\phi(\ell)$ lies below
$L_{s}^{\mathrm{T}}$, and not to the right of $L_{s}$. Since $x_{4}$ is to the
right of $t$ and below $\ell$, we have $\phi(x_{4})\in M\cup B$. This directly
implies that $\phi(x_{3})\in M\cup B$, since $x_{3}$ is below $x_{4}$.
Further, $x_{3}$ is to the left of $t$, and $\phi(b)$ is not to the left of
$\phi(t)\in L_{s}$. This implies $\phi(x_{3})\in M$, and thus $x_{4}\in M$.
Note that, since $0pt_{\phi}(M)\leq 1$, no other 1-entries are mapped to $M$.

Clearly, $\phi(b)\in B$, and by Corollary 4.21, $\phi(b)\in H_{s}$. We now
consider the possible locations of $\phi(b)$.

  1.  _Case_ 1:

$\phi(b)\in L_{s+1}^{\mathrm{B}}\cup R_{s+1}^{\mathrm{B}}$. Then
$\phi(x_{s+1})$ is above $R_{s+1}^{\mathrm{B}}$ (because
$0pt(L_{s+1}^{\mathrm{B}}\cup
R_{s+1}^{\mathrm{B}})=\mathrm{d}^{\mathrm{v}}(x_{s+1},b)-2$) and not to the
right of $R_{s+1}$ (since $x_{s+1}$ is to the left of $b$). Thus,
$\phi(x_{s+1})\in T\cup M$. But $x_{s+1}$ is below $x_{4}$, so $x_{s+1}\in B$,
a contradiction.

  2.  _Case_ 2:

$\phi(b)\in R_{s}^{\mathrm{B}}$. First, suppose that $\phi(x_{4})$ is to the
left of $R_{s}$. Then tallness of $X$ implies that $\phi$ maps no 1-entry to
$R_{s}^{\mathrm{T}}$. But then $\phi$ maps all 1-entries either to
$R_{s}^{\mathrm{B}}$ or to the left and above $R_{s}^{\mathrm{B}}$, and
$\phi(b)\in R_{s}^{\mathrm{B}}$, $\phi(t)\notin R_{s}^{\mathrm{B}}$,
contradicting the fact that $P$ is indecomposable.

Second, suppose that $\phi(x_{4})$ is not to the left of $R_{s}$. Since
$\phi(b)\in R_{s}$, and $x_{4}$ is to the left of $b$, we have $\phi(x_{4})\in
R_{s}$. Moreover, since $x_{4}<_{\mathrm{h}}x_{6}<_{\mathrm{h}}b$ and
$x_{4}<_{\mathrm{v}}x_{6}<_{\mathrm{v}}b$, we have $\phi(x_{6})\in
R_{s}^{\mathrm{B}}$. But
$0pt(R_{s}^{\mathrm{B}})\leq\mathrm{d}^{\mathrm{v}}(x_{s},b)\leq\mathrm{d}^{\mathrm{v}}(x_{5},b)<\mathrm{d}^{\mathrm{v}}(x_{6},b)$,
a contradiction.∎

######  Lemma 4.23.

$\phi(t)\notin L_{s}$ and $\phi(b)\notin R_{s+1}$ for each odd $s$ with $5\leq
s\leq m-5$.

###### Proof.

By symmetry, it suffices to prove the first statement. Suppose $\phi(t)\in
L_{s}$. Then Lemma 4.22 implies that $\phi(\ell)\in L_{s}^{\mathrm{T}}$. This
means that $\phi$ does not map any 1-entry below $L_{s}^{\mathrm{T}}$ and
above $M$, so $0pt_{\phi}(L_{s}^{\mathrm{T}}\cup
L_{s}^{\mathrm{M}})\leq\mathrm{d}^{\mathrm{v}}(t,x_{s})$, implying that
$\phi(x_{s})$ is below the expandable row and thus to the right of $L_{s}$.

We consider several possibilities for the location of $\phi(b)$ and $\phi(r)$.
Corollary 4.21 implies that $\phi(b)\in H_{s}$. Since $\phi(x_{s})$ is below
the expandable row, $\phi(x_{s+2}),\phi(b)\in B$, and thus
$\phi(x_{s+2}),\phi(b)\in H_{s}\cup B=L_{s+1}^{\mathrm{B}}\cup
R_{s}^{\mathrm{B}}\cup R_{s+1}^{\mathrm{B}}$. Since
$x_{s+2}\leq_{\mathrm{v}}x_{m-3}<_{\mathrm{v}}r$, this also implies
$\phi(r)\in H_{s}\cup B$. This means that $\phi$ does not map any 1-entry to
the rows between $M$ and $L_{s+1}^{\mathrm{B}}\cup R_{s+1}^{\mathrm{B}}$, so
$0pt_{\phi}(L_{s+1}^{\mathrm{M}}\cup
L_{s+1}^{\mathrm{B}})\leq\mathrm{d}^{\mathrm{v}}(x_{s+1},x_{s+2})$ and
$0pt_{\phi}(R_{s+1}^{\mathrm{M}}\cup
R_{s+1}^{\mathrm{B}})\leq\mathrm{d}^{\mathrm{v}}(x_{s+1},b)$.

  1.  _Case_ 1:

$\phi(b)\in L_{s+1}^{\mathrm{B}}$. Then $\phi(r)\in L_{s+1}^{\mathrm{B}}\cup
R_{s+1}^{\mathrm{B}}$. Since $0pt_{\phi}(L_{s+1}^{\mathrm{M}}\cup
L_{s+1}^{\mathrm{B}})\leq\mathrm{d}^{\mathrm{v}}(x_{s+1},x_{s+2})<\mathrm{d}^{\mathrm{v}}(x_{s+1},b)$,
we have $\phi(x_{s+1})\in T$. Since $x_{s+1}$ is to the left of $b$, we have
$\phi(x_{s+1})\in L_{s}^{\mathrm{T}}$. But
$0pt(L_{s}^{\mathrm{T}})=\mathrm{d}^{\mathrm{h}}(\ell,x_{s})-1<\mathrm{d}^{\mathrm{h}}(\ell,x_{s+1})$,
a contradiction.

  2.  _Case_ 2:

$\phi(b)\in R_{s+1}^{\mathrm{B}}$. Then $\phi(r)\in R_{s+1}^{\mathrm{B}}$.
Since $0pt_{\phi}(R_{s+1}^{\mathrm{M}}\cup
R_{s+1}^{\mathrm{B}})\leq\mathrm{d}^{\mathrm{v}}(x_{s+1},b)$, we know that
$\phi(x_{s+1})$ is above the expandable row, and therefore to the left of
$R_{s+1}$.

Since $x_{s-1}$ is above $x_{s+1}$, we have $\phi(x_{s-1})\in T$, implying
$\phi(x_{s-1})\in L_{s}^{\mathrm{T}}\cup R_{s}^{\mathrm{T}}$. Further,
$0pt(L_{s}^{\mathrm{T}})<\mathrm{d}^{\mathrm{h}}(\ell,x_{s-1})$, so
$\phi(x_{s-1})\in R_{s}^{\mathrm{T}}$.

Finally, since $\phi(x_{s+2})\in B$ and $x_{s+2}$ is to the left of $x_{s+1}$,
we have $\phi(x_{s+2})\in L_{s+1}^{\mathrm{B}}$. But then $\phi(x_{s+2})$ is
to the left of $\phi(x_{s-1})\in R_{s}^{\mathrm{T}}$, while $x_{s+2}$ is to
the right of $x_{s-1}$, a contradiction.

  3.  _Case_ 3:

$\phi(b),\phi(r)\in R_{s}^{\mathrm{B}}$. We consider the location of
$\phi(x_{s-1})$.

First suppose that $\phi(x_{s-1})\in R_{s}$. Let $q_{s}$ be the 1-entry of $P$
in the row below $x_{s}$. We have $\phi(q_{s})\in B$. Since $X$ is tall,
$q_{s}$ is to the right of $x_{s-1}$, thus $\phi(q_{s})\in
R_{s}^{\mathrm{B}}$. But
$0pt(R_{s}^{\mathrm{B}})\leq\mathrm{d}^{\mathrm{v}}(x_{s},b)-2=\mathrm{d}^{\mathrm{v}}(q_{s},b)-1$,
a contradiction.

Second, suppose $\phi(x_{s-1})\in L_{s+1}$, and $\phi(x_{s-1})$ is below the
expandable row. By tallness of $X$, there are no 1-entries in $P$ that are
above and to the right of $x_{s-1}$, so $\phi$ does not map any 1-entry to
$R_{s}^{\mathrm{T}}\cup R_{s}^{\mathrm{M}}$. But then $\phi$ maps all
1-entries to $R_{s}^{\mathrm{B}}$ or above and to the left of
$R_{s}^{\mathrm{B}}$ (and $\phi(b)\in R_{s}^{\mathrm{B}}$, $\phi(t)\notin
R_{s}^{\mathrm{B}}$). Thus, $P$ is decomposable, a contradiction.

Third, suppose $\phi(x_{s-1})\in L_{s+1}$, and $\phi(x_{s-1})$ is above the
expandable row. Since $\phi(t)$ is below $L_{s+1}^{\mathrm{T}}$, we know that
$\phi(x_{s-1})$ must be mapped to the row directly above the expandable row.
Since $X$ is tall, $\phi$ does not map any 1-entry to $R_{s}^{\mathrm{T}}$.
Note that $L_{s}^{\mathrm{M}}$ consists of only one row, which is already
occupied by $\phi(x_{s-1})$, so $\phi$ also maps no 1-entry to
$L_{s}^{\mathrm{M}}$. But then $\phi$ maps all 1-entries either to
$L_{s}^{\mathrm{T}}$ or below and to the right of $L_{s}^{\mathrm{T}}$ (and
$\phi(t)\in L_{s}^{\mathrm{T}}$, $\phi(b)\notin L_{s}^{\mathrm{T}}$), so $P$
is decomposable, a contradiction.

Fourth, suppose $\phi(x_{s-1})\in R_{s-1}^{\mathrm{M}}$. Then $\phi(x_{s})\in
B$, because $x_{s}$ is below $x_{s-1}$. But $\phi(x_{s})$ also lies to the
left of $\phi(x_{s-1})$ and above $\phi(b)\in R_{s}$, a contradiction.

Finally, suppose $\phi(x_{s-1})\in L_{s}$. Since
$0pt(L_{s})<\mathrm{d}^{\mathrm{h}}(\ell,x_{s-1})$, this is impossible.

  4.  _Case_ 4:

$\phi(b)\in R_{s}^{\mathrm{B}}$ and $\phi(r)\in R_{s+1}^{\mathrm{B}}$. Then
$\phi(x_{s+2})$ is above and not to the right of $R_{s}^{\mathrm{B}}$.
Together with the fact that $\phi(x_{s+2})\in B$, this implies
$\phi(x_{s+2})\in L_{s+1}^{\mathrm{B}}$. Since
$0pt_{\phi}(L_{s+1}^{\mathrm{B}}\cup
L_{s+1}^{\mathrm{M}})\leq\mathrm{d}^{\mathrm{v}}(x_{s+1},x_{s+2})$, we know
that $\phi(x_{s+1})$ is above the expandable row, and thus $\phi(x_{s-1})\in
T$, implying $\phi(x_{s-1})\in L_{s}^{\mathrm{T}}\cup R_{s}^{\mathrm{T}}$.
Since $0pt(L_{s}^{\mathrm{T}})<\mathrm{d}^{\mathrm{h}}(\ell,x_{s-1})$, we have
$\phi(x_{s-1})\in R_{s}^{\mathrm{T}}$. Now $\phi(x_{s-1})\in
R_{s}^{\mathrm{T}}$ is to the right of $\phi(x_{s+2})\in
L_{s+1}^{\mathrm{B}}$, but $x_{s-1}$ is to the left of $x_{s+2}$, a
contradiction.∎

The next three lemmas deal with the case that $\phi(t)\in L_{s+1}$.

######  Lemma 4.24.

Let $5\leq s\leq m-5$. If $\phi(t)\in L_{s+1}$, then $\phi(b)\notin L_{s+1}$.

###### Proof.

Suppose $\phi(t),\phi(b)\in L_{s+1}$. First note that, since
$t<_{\mathrm{h}}x_{s+1}<_{\mathrm{h}}b$, we have $\phi(x_{s+1})\in L_{s+1}$.
Further, $0pt(L_{s+1}^{\mathrm{T}})<\mathrm{d}^{\mathrm{v}}(t,x_{s+1})$ and
$0pt(L_{s+1}^{\mathrm{B}})<\mathrm{d}^{\mathrm{v}}(x_{s+1})$ implies that
$\phi(x_{s+1})\in L_{s+1}^{\mathrm{M}}$.

Let $y\in E(P)$ be the 1-entry in the column directly left of $x_{s+1}$. Note
that $y^{s+1}$ is the rightmost 1-entry in $L_{s+1}$, and that
$\mathrm{d}^{\mathrm{h}}(t^{s+1},y^{s+1})=\mathrm{d}^{\mathrm{h}}(t,y)<\mathrm{d}^{\mathrm{h}}(t,b)$.
Since $\phi(b)$ is not to the right of $y^{s+1}$, this implies that $\phi(t)$
is to the left of $t^{s+1}$. By a similar argument, $\phi(x_{3})$ is to the
left of $x_{3}^{s+1}$.

Since $t^{s+1}$ is the topmost 1-entry in $L_{s+1}$, this also means that
$\phi(t)$ is below $t^{s+1}$. Further,
$\mathrm{d}^{\mathrm{v}}(t^{s+1},x_{3}^{s+1})=\mathrm{d}^{\mathrm{v}}(t,x_{3})\leq\mathrm{d}^{\mathrm{v}}(\phi(t),\phi(x_{3}))$,
so $\phi(x_{3})$ is below $x_{3}^{s+1}$.

Tallness of $X$ implies that $L_{s+1}$ contains no 1-entries to the left and
below $x_{3}^{s+1}$, so $\phi(x_{3})$ is to the left of $L_{s+1}$. Since
$\phi(b)\in L_{s+1}$, this means that $\phi(x_{3})\in T\cup M$.

Since $\phi(x_{3})$ is to the left of $L_{s+1}$, we also know that
$\phi(\ell)$ is to the left of $L_{s+1}$, implying that $\phi(\ell)$ is below
$L_{s+1}^{\mathrm{T}}$. Since $t<_{\mathrm{h}}x_{4}<_{\mathrm{h}}b$ and
$\ell<_{\mathrm{v}}x_{4}<_{\mathrm{v}}x_{3}$, we have $\phi(x_{4})\in
L_{s+1}^{\mathrm{M}}$. Since $x_{3}$ is below $x_{4}$, this also means that
$\phi(x_{3})\in M$. But now $\phi(x_{3}),\phi(x_{4}),\phi(x_{s+1})\in M$,
while $M$ consists of only two nonempty rows, a contradiction. ∎

######  Lemma 4.25.

Let $s$ be odd with $5\leq s\leq m-5$. If $\phi(t)\in L_{s+1}$ and $\phi(b)\in
R_{s}$, then $\phi(x_{s-1})\in L_{s+1}$ and $\phi(x_{s+2})\in R_{s}$.

###### Proof.

By symmetry, it suffices to show that $\phi(x_{s-1})\in L_{s+1}$. Suppose not.
Since $t<_{\mathrm{h}}x_{s-1}<_{\mathrm{h}}b$, this means that
$\phi(x_{s-1})\in R_{s}$. Let $q_{s}\in E(P)$ be the 1-entry of $P$ in the row
directly below $x_{s}$.

We claim that $\phi(x_{s})$ is below the expandable row, and thus
$\phi(q_{s})\in B$. If $\phi(x_{s-1})\in M\cup B$, then $\phi(x_{s})$ is below
the expandable row, since $x_{s}$ is below $x_{s-1}$. Otherwise,
$\phi(x_{s-1})\in R_{s}^{\mathrm{T}}$, which implies that $\phi(\ell)\in
L_{s}\cup L_{s+1}$, so $\phi$ maps no 1-entry into the rows between
$L_{s}^{\mathrm{T}}\cup R_{s}^{\mathrm{T}}$ and $M$. Thus,
$0pt_{\phi}(R_{s}^{\mathrm{T}}\cup
R_{s}^{\mathrm{M}})\leq\mathrm{d}^{\mathrm{v}}(x_{s-1},x_{s})$, implying that
$\phi(x_{s})$ is below the expandable row. This proves the claim.

$0pt(R_{s}^{\mathrm{B}})\leq\mathrm{d}^{\mathrm{v}}(x_{s},b)-2=\mathrm{d}^{\mathrm{v}}(q_{s},b)-1$
implies that $\phi(q_{s})\notin R_{s}^{\mathrm{B}}$. Since $X$ is tall,
$q_{s}$ is to the right of $x_{s-1}$ and thus $\phi(q_{s})$ is not to the left
of $R_{s}$. Since $\phi(q_{s})\in B\setminus R_{s}^{\mathrm{B}}$, this implies
that $\phi(q_{s})$ is to the right of $R_{s}$, so $\phi(r)$ is to the right of
$R_{s}$, and thus above $R_{s}^{\mathrm{B}}$.

Consider now $x_{s+2}$. First, $x_{s-1}<_{\mathrm{h}}x_{s+2}<_{\mathrm{h}}b$
implies that $\phi(x_{s+2})\in R_{s}$. Since $x_{s}$ is below the expandable
row, $\phi(x_{s+2})\in R_{s}^{\mathrm{B}}$. But then $\phi(x_{s+2})$ is below
$\phi(r)$, a contradiction. ∎

######  Lemma 4.26.

Let $s$ be odd with $5\leq s\leq m-5$. If $\phi(t)\in L_{s+1}$, then
$\phi(b)\in R_{s}$ and $\phi(E(P))\subseteq L_{s+1}\cup R_{s}$.

###### Proof.

Assume $\phi(t)\in L_{s+1}$. By Corollary 4.21, we have $\phi(b)\in H_{s}$.
Lemmas 4.23 and 4.24 imply that $\phi(b)\notin L_{s+1}\cup R_{s+1}$. If
$\phi(b)\in L_{s+2}$, then $\phi(b)$ is above the expandable row. But then
$\phi(r)$ is to the right of $R_{s}$, below $L_{s+2}^{\mathrm{T}}$ and in $T$,
which is impossible. The only remaining possibility is that $\phi(b)\in
R_{s}$.

To show $\phi(E(P))\subseteq L_{s+1}\cup R_{s}$, it is enough to prove that
$\phi(\ell)\in L_{s+1}$ and $\phi(r)\in R_{s}$, and by symmetry, we only have
to prove $\phi(\ell)\in L_{s+1}$. Suppose $\phi(\ell)\notin L_{s+1}$. Then
$\phi(\ell)$ is below $L_{s+1}^{\mathrm{T}}$. Since $x_{s-1}$ is below $\ell$
and $\phi(x_{s-1})\in L_{s+1}$ by Lemma 4.25, we have $\phi(x_{s-1})\in
L_{s+1}^{\mathrm{M}}\cup L_{s+1}^{\mathrm{B}}$.

Since
$0pt(L_{s-1}^{\mathrm{B}})<\mathrm{d}^{\mathrm{v}}(x_{s+1},x_{s+2})<\mathrm{d}^{\mathrm{v}}(x_{s-1},r)$,
we know that $\phi(r)$ is below $L_{s+1}^{\mathrm{B}}$, so $\phi(r)\in
R_{s}^{\mathrm{B}}$. Moreover, tallness of $X$ implies that $\phi$ maps no
1-entry to $R_{s}^{\mathrm{T}}\cup R_{s}^{\mathrm{M}}$. But then $\phi$ maps
all 1-entries either to $R_{s}^{\mathrm{B}}$ or above and to the left of
$R_{s}^{\mathrm{B}}$ (and $\phi(b)\in R_{s}^{\mathrm{B}}$, $\phi(t)\notin
R_{s}^{\mathrm{B}}$), so $P$ is decomposable, a contradiction. ∎

######  Lemma 4.27.

$\phi(t)\notin L_{s+1}$ and $\phi(b)\notin R_{s}$ for each odd $s$ with $5\leq
s\leq m-5$.

###### Proof.

By symmetry, it suffices to show the first statement. Suppose $\phi(t)\in
L_{s+1}$. By Lemmas 4.25 and 4.26, we have $\phi(x_{s-1})\in L_{s+1}$ as well
as $\phi(x_{s+2}),\phi(b)\in R_{s}$ and $\phi(P)\subseteq L_{s+1}\cup R_{s}$.

Since $t<_{\mathrm{h}}x_{s}<_{\mathrm{h}}x_{s-1}$, we have $\phi(x_{s})\in
L_{s+1}$. Symmetrically, $\phi(x_{s+1})\in R_{s}$. Let $p_{s+1}\in E(P)$ be
the 1-entry of $P$ in the row directly above $x_{s+1}$, and let $q_{s}\in
E(P)$ be the 1-entry in the row directly below $x_{s}$. Since
$0pt(L_{s+1}^{\mathrm{T}})=\mathrm{d}^{\mathrm{v}}(t,p_{s+1})-1$, we know that
$\phi(p_{s+1}),\phi(x_{s+1})$ are below $L_{s+1}^{\mathrm{T}}$, and,
symmetrically, $\phi(q_{s}),\phi(x_{s})$ are above $R_{s}^{\mathrm{B}}$. All
in all, we have $\phi(x_{s}),\phi(x_{s+1}),\phi(q_{s}),\phi(p_{s+1})\in
L_{s+1}^{\mathrm{M}}\cup L_{s+1}^{\mathrm{B}}\cup R_{s}^{\mathrm{T}}\cup
R_{s}^{\mathrm{M}}$.

Our strategy for the remainder of the proof is to find two 1-entries
$y_{1},y_{2}\in E(P)$ such that the sequence
$Y=x_{1},x_{2},\dots,x_{s},y_{1},y_{2},x_{s+1},\dots,x_{m}$ is a traversal of
$P$. For, this, we have to show that
$x_{s-1}<_{\mathrm{h}}y_{2}<_{\mathrm{h}}y_{1}<_{\mathrm{h}}x_{s+2}$, as well
as $y_{1}<_{\mathrm{v}}x_{s+1}$, and $x_{s}<_{\mathrm{v}}y_{2}$ (note that
$x_{s-1}<_{\mathrm{v}}y_{1}$ and $y_{2}<_{\mathrm{v}}x_{s+2}$ then follow from
tallness of $X$). The existence of such a traversal implies that $X$ is
extendable, contradicting Lemma 4.1.

We consider two cases. First, assume that $q_{s}$ is to the left of $p_{s+1}$.
Then we simply choose $y_{1}=p_{s+1}$ and $y_{2}=q_{s}$. By definition,
$p_{s+1}$ is above $x_{s+1}$ and $q_{s}$ is below $x_{s}$. By assumption,
$q_{s}<_{\mathrm{h}}p_{s+1}$, and tallness implies that
$x_{s-1}<_{\mathrm{h}}q_{s}$ and $p_{s+1}<_{\mathrm{h}}x_{s+2}$.

Otherwise, $p_{s+1}$ is to the left of $q_{s}$. Then either $\phi(p_{s+1})\in
L_{s+1}$ or $\phi(q_{s})\in R_{s}$. By symmetry, we can assume the former,
which implies $\phi(p_{s+1})\in L_{s+1}^{\mathrm{M}}\cup
L_{s+1}^{\mathrm{B}}$. Since $\phi(x_{s+1})\in R_{s}^{\mathrm{T}}\cup
R_{s}^{\mathrm{M}}$ and $x_{s+1}$ is below $p_{s+1}$, we have
$\phi(p_{s+1}),\phi(x_{s+1})\in M$. More precisely,
$\phi(p_{s+1})=p_{s+1}^{s+1}\in L_{s+1}^{\mathrm{M}}$ and
$\phi(x_{s+1})=q_{s}^{s}\in R_{s}^{\mathrm{M}}$.

Since $\phi(\ell)\in L_{s+1}$, we know that $\phi$ maps no 1-entry into the
rows between $M$ and $L_{s+1}^{\mathrm{B}}$. Since $\phi$ also maps no 1-entry
into the expandable row, we have
$\mathrm{d}^{\mathrm{v}}_{\phi}(p_{s+1}^{s+1},x_{s}^{s+1})\leq\mathrm{d}^{\mathrm{v}}(p_{s+1},x_{s})-1$.
This implies that $\phi(x_{s})$ is below $x_{s}^{s+1}$.

Since $X$ is tall, all 1-entries in $L_{s+1}$ below $x_{s}^{s+1}$, including
$\phi(x_{s})$, must be to the right of $x_{s-1}^{s+1}$ (note that
$x_{s-1}^{s+1}\in L_{s+1}$). Since $x_{s-1}$ is above $x_{s+1}$ and
$\phi(x_{s+1})=q_{s}^{s}$, we have $\phi(x_{s-1})\in
L^{\mathrm{T}}_{s+1}\cup\\{p_{s+1}^{s+1}\\}$ (note that $x_{s-1}=p_{s+1}$ is
possible). Tallness of $X$ implies that
$0pt(L_{s+1}^{\mathrm{T}}\cup\\{p_{s+1}^{s+1}\\})<\mathrm{d}^{\mathrm{h}}(\ell,x_{s+2})$,
so $\phi(x_{s-1})$ is to the left of $x_{s+2}^{s+1}$.

Putting everything together, we have
$x_{s-1}^{s+1}<_{\mathrm{h}}\phi(x_{s})<_{\mathrm{h}}\phi(x_{s-1})<_{\mathrm{h}}x_{s+2}^{s+1}$,
and $\phi(x_{s-1})\in L_{s+1}$ is above the expandable row, and $\phi(x_{s})$
is below $x_{s}^{s+1}$. Now choose $y_{1},y_{2}\in E(P)$ such that
$y_{1}^{s+1}=\phi(x_{s-1})$ and $y_{2}^{s+1}=\phi(x_{s})$. Then
$x_{s-1}<_{\mathrm{h}}y_{2}<_{\mathrm{h}}y_{1}<_{\mathrm{h}}x_{s+2}$, as well
as $y_{1}<_{\mathrm{v}}x_{s+1}$, and $x_{s}<_{\mathrm{v}}y_{2}$. This implies
that $Y$ is a traversal of $P$. ∎

The last remaining cases are now easy:

######  Lemma 4.28.

$\phi(t)\notin R_{s-1}\cup R_{s}$ and $\phi(b)\notin L_{s+1}\cup L_{s+2}$ for
each odd $s$ with $5\leq s\leq m-5$.

###### Proof.

By symmetry, it suffices to show the first statement. Suppose $\phi(t)\in
R_{s-1}\cup R_{s}$. By Corollaries 4.21, 4.23, and 4.27, we have
$\phi(b)=L_{s+1}\cup L_{s+2}$.

Suppose first that $\phi(t)\in R_{s-1}$. Then $\phi(t)$ is below the
expandable row, meaning that $\phi(\ell)$ is below $M$, but not to the right
of $R_{s-1}$. But $\phi(b)$ is above $R_{s-1}^{\mathrm{B}}$, implying that
$\phi(\ell)$ is also above $R_{s-1}^{\mathrm{B}}$, a contradiction.

Second, if $\phi(t)\in R_{s}$, then $\phi(b)\in L_{s+2}$, since $b$ is to the
right of $t$. A symmetric argument shows that $\phi(r)$ is above $M$ and below
$L_{s+2}^{\mathrm{T}}$, a contradiction. ∎

Lemmas 4.23, 4.27, and 4.28 imply that $\phi(t)\notin G_{s}$, contradicting
Corollary 4.21. As such, our assumption that $\phi$ is an embedding of $P$
into $S(P,X)$ must be false. This concludes the proof of Lemma 4.7.

##  5 Conclusion and open problems

We showed that each decomposable permutation matrix has bounded saturation
function, thereby completing the classification of saturation functions of
permutation matrices. Our proofs imply the upper bound $\mathrm{sat}(P,n)\leq
9k^{4}$ for an indecomposable $k\times k$ permutation matrix $P$ (note that
the largest witness $S(P,X)$ is not larger than $2k^{2}\times k^{2}$, and
Lemma 1.5 combines it with its 90-degree rotation, resulting in a
$3k^{2}\times 3k^{2}$ matrix). It would be interesting to improve this bound,
especially if a simpler construction for patterns satisfying the conditions of
Lemma 4.7 can be found. Note that for general patterns with bounded saturation
functions, no upper bound for $\mathrm{sat}(P,n)$ in terms of $P$ is known, as
noted by Fulek and Keszegh [FK20].

We also characterized a large class of non-permutation patterns with bounded
saturation function, including very dense matrices (Theorem 1.1). Still, a
full characterization of the saturation functions of all matrices remains out
of reach. Note that there are indecomposable patterns without spanning
oscillations, see, e.g., Figure 14. Thus, new techniques are likely required
to fully resolve this problem.

$\displaystyle\left(\begin{smallmatrix}\bullet&&&&\\\ \bullet&&&&\\\
\bullet&&&&\\\ \bullet&&&&\\\
\bullet&\bullet&\bullet&\bullet&\bullet\end{smallmatrix}\right)$ Figure 14: An
indecomposable non-permutation matrix without a spanning oscillation.

Our results trivially imply that every permutation matrix with a vertical
witness also has a horizontal witness. It would be interesting to determine
whether this is true for arbitrary patterns.

It is also possible consider the saturation functions of _sets_ of patterns.
If $\mathcal{P}$ is a set of patterns, let a matrix $M$ be
$\mathcal{P}$-saturating if $M$ avoids each $P\in\mathcal{P}$, and adding a
single 1-entry in $M$ creates an occurrence of some $P\in\mathcal{P}$ in $M$.
Let $\mathrm{sat}(\mathcal{P},n)$ be the minimum weight of
$\mathcal{P}$-saturating matrices. Since our witnesses for $k\times k$
permutation matrices have size at most $3k^{2}\times 3k^{2}$, and thus avoid
all patterns with one side of side length more than $3k^{2}$. Thus, if
$\mathcal{P}$ contains one permutation matrix, and arbitrarily many much
larger patterns, our results imply that
$\mathrm{sat}(\mathcal{P},n)\in\mathcal{O}(1)$.

It would be interesting to determine the saturation functions for, say, all
pairs of two permutation matrices of the same size. Gerbner, Nagy, Patkós, and
Vizer [GNPV21] observed that certain saturation problems for two-dimensional
posets can be reduced to saturation problems for sets of matrix patterns.
However, these sets usually contain both permutation matrices and non-
permutation matrices (of similar size).

##### Acknowledgments.

The author would like to thank Jesse Geneson and László Kozma for helpful
discussions and feedback.

## References

  * [ARSz99] Noga Alon, Lajos Rónyai, and Tibor Szabó.  Norm-graphs: Variations and applications.  Journal of Combinatorial Theory, Series B, 76(2):280–290, 1999\.  10.1006/jctb.1999.1906.
  * [BC20] Richard A. Brualdi and Lei Cao.  Pattern-avoiding (0,1)-matrices.  arXiv e-prints, 2020, 2005.00379v2.
  * [Ber20] Benjamin Aram Berendsohn.  Matrix patterns with bounded saturation function.  arXiv e-prints, 2020, 2012.14717v1.
  * [BG91] Dan Bienstock and Ervin Györi.  An extremal problem on sparse 0-1 matrices.  SIAM Journal on Discrete Mathematics, 4(1):17–27, 1991.  10.1137/0404002.
  * [BRV08] Robert Brignall, Nik Ruškuc, and Vincent Vatter.  Simple permutations: Decidability and unavoidable substructures.  Theoretical Computer Science, 391(1):150–163, 2008.  10.1016/j.tcs.2007.10.037.
  * [CGK+15] Parinya Chalermsook, Mayank Goswami, Laszlo Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak.  Pattern-avoiding access in binary search trees.  2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 410–423, 2015.  10.1109/FOCS.2015.32.
  * [FH92] Zoltán Füredi and Péter Hajnal.  Davenport-schinzel theory of matrices.  Discrete Mathematics, 103(3):233–251, 1992.  10.1016/0012-365X(92)90316-8.
  * [FK20] Radoslav Fulek and Balázs Keszegh.  Saturation problems about forbidden $0$-$1$ submatrices.  arXiv e-prints, 2020, 2010.08256.
  * [Ful09] Radoslav Fulek.  Linear bound on extremal functions of some forbidden patterns in 0–1 matrices.  Discrete Mathematics, 309(6):1736–1739, 2009.  10.1016/j.disc.2008.02.040.
  * [Für90] Zoltán Füredi.  The maximum number of unit distances in a convex n-gon.  J. Comb. Theory, Ser. A, 55(2):316–320, 1990.  10.1016/0097-3165(90)90074-7.
  * [Gen09] Jesse T. Geneson.  Extremal functions of forbidden double permutation matrices.  Journal of Combinatorial Theory, Series A, 116(7):1235 – 1244, 2009\.  10.1016/j.jcta.2009.03.004.
  * [Gen20] Jesse T. Geneson.  Almost all permutation matrices have bounded saturation functions.  arXiv e-prints, December 2020, 2012.14150.
  * [GNPV21] Dániel Gerbner, Dániel T. Nagy, Balázs Patkós, and Máté Vizer.  Forbidden subposet problems in the grid.  arXiv e-prints, February 2021, 2102.08297.
  * [Kesz09] Balázs Keszegh.  On linear forbidden submatrices.  Journal of Combinatorial Theory, Series A, 116(1):232 – 241, 2009\.  10.1016/j.jcta.2008.05.006.
  * [Kla00] Martin Klazar.  The Füredi-Hajnal conjecture implies the stanley-wilf conjecture.  In Formal power series and algebraic combinatorics, pages 250–255. Springer, 2000.  10.1007/978-3-662-04166-6_22.
  * [Kla01] Martin Klazar.  Enumerative and extremal combinatorics of a containment relation of partitions and hypergraphs.  Habilitation thesis, 2001.
  * [Mit87] Joseph S. B. Mitchell.  Shortest rectilinear paths among obstacles.  Technical report, Cornell University Operations Research and Industrial Engineering, 1987.
  * [MT04] Adam Marcus and Gábor Tardos.  Excluded permutation matrices and the Stanley–Wilf conjecture.  Journal of Combinatorial Theory, Series A, 107(1):153–160, 2004\.  10.1016/j.jcta.2004.04.002.
  * [Pet10] Seth Pettie.  Applications of forbidden 0–1 matrices to search tree and path compression-based data structures.  In Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1457–1467, 2010.  10.1137/1.9781611973075.118.
  * [Pet11a] Seth Pettie.  Degrees of nonlinearity in forbidden 0–1 matrix problems.  Discrete Mathematics, 311(21):2396 – 2410, 2011.  10.1016/j.disc.2011.06.020.
  * [Pet11b] Seth Pettie.  Generalized davenport-schinzel sequences and their 0-1 matrix counterparts.  J. Comb. Theory Ser. A, 118(6):1863–1895, 2011.
  * [Pra73] Vaughan R. Pratt.  Computing permutations with double-ended queues, parallel stacks and parallel queues.  In Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, pages 268–277, New York, NY, USA, 1973. ACM.  10.1145/800125.804058.
  * [PT06] János Pach and Gábor Tardos.  Forbidden paths and cycles in ordered graphs and matrices.  Israel Journal of Mathematics, 155(1):359–380, 2006.
  * [Tar05] Gábor Tardos.  On 0–1 matrices and small excluded submatrices.  Journal of Combinatorial Theory, Series A, 111(2):266 – 288, 2005\.  10.1016/j.jcta.2004.11.015.
  * [Vat11] Vincent Vatter.  Small permutation classes.  Proceedings of the London Mathematical Society, 103(5):879–921, 2011.  10.1112/plms/pdr017.
  * [Vat14] Vincent Vatter.  Permutation classes.  arXiv e-prints, 2014, 1409.5159v3.

##  Appendix A Proof of Section 1.4

*

###### Proof.

Say $P$ is $q\times s$ and $M$ is $m\times n$. Suppose $P=(p_{i,j})_{i,j}$ is
contained in $M$. Then there are rows $r_{1}<r_{2}<\dots<r_{q}$ and columns
$c_{1}<c_{2}<\dots<c_{r}$ such that $p_{i,j}\leq m_{r_{i},c_{j}}$ for each
$i\in[q],j\in[r]$. Now simply define $\phi(i,j)=(r_{i},c_{j})$. Clearly,
$\phi(E(P))\subseteq E(M)$. Moreover, consider
$(i,j),(i^{\prime},j^{\prime})\in E(P)$. We have $i<i^{\prime}$ if and only if
$r_{i}<r_{i^{\prime}}$, and $j<j^{\prime}$ if and only if
$r_{j}<r_{j^{\prime}}$. Thus $\phi$ is an embedding of $P$ into $M$.

Now suppose $\phi\colon E(P)\rightarrow E(M)$ is an embedding of $P$ into $M$.
Note that $x,y\in E(P)$ are in the same row (resp. column) if and only if
$\phi(x),\phi(y)$ are in the same row (resp. column). Thus, $\phi(E(P))$
intersects exactly $q$ rows and $s$ columns. Let $r_{1}<r_{2}<\dots<r_{q}$ be
those rows and $c_{1}<c_{2}<\dots<c_{r}$ be those columns. We show that
$\phi(i,j)=(r_{i},c_{j})$ for each $(i,j)\in E(P)$. Let
$x_{1},x_{2},\dots,x_{m}\in E(P)$ such that $x_{i}$ is in the $i$-th row for
each $i\in[m]$, and let $r_{i}^{\prime}$ be the row of $M$ containing
$\phi(x_{i})$. Clearly $r_{1}^{\prime}\geq r_{1}$. By induction, we further
have $r^{\prime}_{i}\geq r_{i}$ for each $i\in[m]$. Similarly,
$r_{m}^{\prime}\leq r_{m}$, and, again by induction, $r^{\prime}_{i}\leq
r_{i}$ for each $i\in[m]$. This implies that $\phi(i,j)$ is in the $r_{i}$-th
row of $M$ for every $(i,j)\in E(P)$. An analogous argument shows that
$\phi(i,j)$ is in the $c_{j}$-th column of $M$.

Since $\phi$ is an embedding, we have $(r_{i},c_{j})=\phi(i,j)\in E(M)$ for
each $(i,j)\in E(P)$. Thus, $p_{i,j}\leq m_{r_{i},c_{j}}$ for each
$(i,j)\in[q]\times[s]$, so $P$ is contained in $M$. ∎