Bipartite Determinantal Ideals and concurrent vertex maps

Li Li
Department of Mathematics
and Statistics,
Oakland University,
Rochester, MI 48309-4479, USA

[2010]Primary 14M12; Secondary 05E40,05E45,13C40,13F55,13H10

Bipartite determinantal ideals are introduced in [13] as a vast generalization of the classical determinantal ideals intensively studied in commutative algebra, algebraic geometry, representation theory and combinatorics.  We introduce a combinatorial model called concurrent vertex maps to describe the Stanley-Reisner complex of the initial ideal of any bipartite determinantal ideal, and study properties and applications of this model.

§ INTRODUCTION

The primary objective of this paper is to present a novel combinatorial model called “concurrent vertex maps". This model is introduced to effectively describe the Stanley-Reisner complex of a bipartite determinantal ideal. Additionally, we use this combinatorial model to study properties of those Stanley-Reisner complex.

We begin by reviewing the classical determinantal ideals. Let ${\bf k}$ be a field, $A$ be an $m\times n$ matrix consisting of independent variables $x_{ij}$,  $r$ be a positive integer. The ideal $I$ of ${\bf k}[x_{ij}]$generated by all $r\times r$ minors in $A$ is referred as a determinantal ideal. The quotient ring ${\bf k}[x_{ij}]/I$ is known as a determinantal ring.
Geometrically, a determinantal ideal defines an affine variety called determinantal variety. The variety consists of all $m\times n$ matrices with entries in ${\bf k}$ and rank at most $r-1$.
For example, take the case where $m=2, n=3, r=2$. The matrix $A$ and the determinantal ideal $I$ are:

$$A=\begin{bmatrix}x_{11}&x_{12}&x_{13}\\ x_{21}&x_{22}&x_{33}\end{bmatrix},
\quad
\begin{vmatrix}x_{11}&x_{12}\\ x_{21}&x_{22}\end{vmatrix},
\begin{vmatrix}x_{11}&x_{13}\\ x_{21}&x_{23}\end{vmatrix},
\begin{vmatrix}x_{12}&x_{13}\\ x_{22}&x_{23}\end{vmatrix}
\rangle

The corresponding determinantal variety consisits of all $2\times 3$ matrices that do nothave full rank. This variety is irreducible, singular, and $4$-dimensional.

Determinantal ideals have been a central topic, a test field, and a source of inspiration in various areas such as commutative algebra, algebraic geometry, representation theory, and combinatorics.

Researchers have extensively investigated determinantal ideals/rings, exploring topics such as minimal free resolution and syzygies (both algebraically and geometrically in terms of vector bundles), (Arithmetic) Cohen-Macaulayness, multiplicities, powers and products, Hilbert series, $a$-invariant, $F$-regularity and $F$-rationality, and local cohomology. The tools employed in these investigations include the Gröbner basis theory, simplicial complexes, the straightening law, the Knuth-Robinson-Schensted (KRS) correspondence, non-intersecting paths from algebraic combinatorics, and liaison theory from commutative algebra. Determinantal ideals/rings are closely connected to the study of Grassmannian and Schubert varieties, and there exist interesting specializations, generalizations, and variations, such as Segre varieties, linear determinantal varieties, rational normal scrolls, symmetric and skew-symmetric determinantal varieties, as well as classical, two-sided, or mixed ladder determinantal varieties. For further reading on these topics, interested readers can refer to [1, 4, 10, 16, 17, 18, 21] and the references therein.

In our previous work [13], we introduced a generalization of determinantal ideals called the bipartite determinantal ideals, and showed that the natural generators form a Gröbner basis under suitable monomial order. Let us recall the definition and the main result therein.

(Bipartite determinantal ideal)
Let $\mathcal{Q}$ be a bipartite quiver with $d$ vertices and the vertex set ${\rm V}_\mathcal{Q}={\rm V}_{\rm source}\sqcup {\rm V}_{\rm target}$, and with $r$ arrows $h_i: \source(h_i)\to \target(h_i)$ (for $i=1,\dots,r$) such that $\source(h_i)\in {\rm V}_{\rm source}$ and $\target(h_i)\in {\rm V}_{\rm target}$.
Let $\mm=(m_1,\dots,m_d)$, $\uu=(u_1,\dots,u_d)$  be two $d$-tuples of nonnegative integers.
Let $X= \{ X^{(k)}=[x^{(k)}_{ij}]\}_{k=1}^r $ where  $X^{(k)}$ is an $m_{\target(h_k)}\times m_{\source(h_k)}$ matrix consisting of independent variables.
For $\alpha\in {\rm V}_{\rm target}$, let $r_1<\cdots<r_s$ be all the indices such that $h_{r_1},\dots,h_{r_s}$ are all the arrows with target $\alpha$, and define a block matrix

$$ A_\alpha= [ X^{(r_1)}|X^{(r_2)}|\hdots|X^{(r_s)} ].$$

For $\beta\in {\rm V}_{\rm source}$, let $r'_1<\cdots<r'_t$ be all the indices such that $h_{r'_1},\dots,h_{r'_t}$ are all the arrows with source $\beta$, and define a block matrix

\begin{array}{c}
X^{(r'_1)}  \\ \hline
X^{(r'_2)} \\ \hline
\vdots \\ \hline
\end{array}
\right]. $$

For $\gamma\in{\rm V}_\mathcal{Q}$, let $a_\gamma\times b_\gamma$ be the size of $A_\gamma$, that is,

&(a_\alpha,b_\alpha)=(m_\alpha,\sum_{h:\ \target(h)=\alpha} m_{\source(h)}) \textrm{ for } \alpha\in {\rm V}_{\rm target},\\
&(a_\beta,b_\beta)=(\sum_{h:\ \source(h)=\beta} m_\alpha,m_{\target(h)}) \textrm{ for } \beta\in {\rm V}_{\rm source}.
\endaligned

The bipartite determinantal ideal $I_{\mathcal{Q},\mm,\uu}$ is the ideal of ${\bf k}[X]$ generated by $\bigcup_{\gamma\in{\rm V}_\mathcal{Q}}D_{u_\gamma+1}(A_\gamma)$, where $D_{u_\gamma+1}(A_\gamma)$ denotes the set of all $(u_\gamma+1)$-minors of $A_\gamma$.  These generators are called the natural generators of $I_{\mathcal{Q},\mm,\uu}$.

As explained in [13], the bipartite determinantal ideal specializes to the classical determinantal ideal $I^{\rm det}_{m,n,u}$ of $(u+1)$-minors in an $m\times n$ matrix for $\mathcal{Q}:2\to 1$, ${\bf m}=(m_1,m_2)=(m,n)$, ${\bf u}=(u_1,u_2)=(u,u)$; more generally, they specializes to a double determinantal ideal $I^{(r)}_{m,n,u,v}$ for $\mathcal{Q}:2\stackrel{r}{\to}1$ which has $r$ arrows from $2$ to $1$ which we introduced in [13] and is defined as follows (with a slight change of notations to be consistent with the notations in the current paper):

Let $r, m, n, u, v$ be positive integers, let $X= \{ X^{(k)}=[x^{(k)}_{ij}]\}_{k=1}^r $ be a set of variable matrices of dimension $m\times n$matrices

$$ A_1= [ X^{(1)}|X^{(2)}|\hdots|X^{(r)} ],
\hspace{12pt}
A_2= \left[
\begin{array}{c}
X^{(1)}  \\ \hline
X^{(2)} \\ \hline
\vdots \\ \hline
\end{array}
\right] $$

The double determinantal ideal $I_{m,n,u,v}^{(r)}$ is the ideal of $K[X]$ generated by $(u+1)$-minors in $A_1$ and $(v+1)$-minors in $A_2$.

For a matrix of variables  $Y=(y_{ij})$, we say that an order “$>$” is consistent on $Y$ when $y_{ij}> y_{i,j+k}$ and $y_{ij}> y_{i+k,j}$ for all $i,j$.

There exists a lexicographical monomial order that is consistent on all $A_i$, for example we can take the  lex order “$>$” such that

\begin{equation}\label{eq: favorite order}
\textrm{$x_{ij}^{(r)}>x_{kl}^{(s)}$ if : ``$r<s$'', or ``$r=s,i<k$'', or ``$r=s,i=k,j<l$''.}
\end{equation}

Recall the following theorem proved in [13].

[13]
Fix ${\mathcal{Q},\mm,\uu}$ satisfying (<ref>).
Then the set of natural generators of
bipartite determinantal ideal $I_{\mathcal{Q},\mm,\uu}$,
if nonempty, forms a Gröbner basis with respect to any lexicographical monomial order that is consistent in all $A_i$.

Combining the above theorem and properties of Nakajima's affine graded quiver varieties, we easily get:

The bipartite determinantal ideals $I_{\mathcal{Q},\mm,\uu}$ are prime.

By the Gröbner bases result (Theorem <ref>), the initial ideal of $I_{Q,\mm,uu}$, denoted ${\rm init }(I_{\mathcal{Q},\mm,\uu})$,  is generated by the leading terms of its natural generators. Since each generator is the product of diagonal entries of a submatrix of $A_i$ for some $i$, the ideal ${\rm init }(I_{\mathcal{Q},\mm,\uu})$ must be a squarefree monomial, thus is radical. Therefore $I_{\mathcal{Q},\mm,\uu}$ is radical.

On the other hand, note that the zero set of $I_{\mathcal{Q},\mm,\uu}$ is Nakajima's affine graded quiver variety which is
irreducible [14], so the radical of $I_{\mathcal{Q},\mm,\uu}$, thus $I_{\mathcal{Q},\mm,\uu}$ itself, is prime.

Without loss of generality, we assume

\begin{equation}\label{eq:condition on u}
0<u_\gamma\le \min(a_\gamma,b_\gamma) \textrm{ for all vertices }\gamma.
\end{equation}

in the rest of the paper.
if $u_\gamma \ge \min(a_\gamma,b_\gamma)$, then there are no $(u_\gamma+1)$-minors of $A_\gamma$, so we can replace $\mu_\gamma$ by $\min(a_\gamma,b_\gamma)$ and  $I_{\mathcal{Q},\mm,\uu}$ remains unchanged;
if $u_\gamma=0$, then let $\gamma$ be a vertex of $\mathcal{Q}$, let $\mathcal{Q}'$ be the quiver obtained by removing the vertex $\gamma$ and all the arrows incident to $\gamma$, let $\mm'=(m_i)_{i\neq \gamma}$, $\uu'=(u_i)_{j\neq \gamma}$.
We have

$$I_{\mathcal{Q},\mm,\uu}= I_{\mathcal{Q}',\mm',\uu}'
\langle x^{(k)}_{ij}\in X^{(k)} \ | \ \textrm{ the arrow $h_k$ is incident to $\gamma$} \rangle $$

and the natural generators of $I_{\mathcal{Q},\mm,\uu}$ consists of the natural generators of $I_{\mathcal{Q}',\mm',\uu'}$ together with variables $x^{(k)}_{ij}$ where the arrow $h_k$ is incident to $\gamma$.  So no essential information is lost when we replace
$I_{\mathcal{Q},\mm,\uu}$ by $I_{\mathcal{Q}',\mm',\uu'}$.

Also note that if some inequality in (<ref>) becomes equality: $u_\gamma = \min(a_\gamma,b_\gamma)$, some of the proofs in this paper need to be modified, but they always degenerate to simpler or trivial cases, so we feel it is unnecessary and redundant to explain all the modifications, and is safe to omit.

By Stanley-Reisner correspondence (see <cit.>), there is a bijection from simplicial complexes on $n$ vertices to squarefree monomial ideals in $\mathbf{k}[x_1,\dots,x_n]$, sending $\Delta$ to

$$I_\Delta=\langle {\bf x}^\tau|\tau\notin \Delta \rangle
=\bigcap_{\sigma\in\Delta} \langle x_i\ | \ i\notin\sigma \rangle
=\bigcap_{\sigma\in{\rm facets}(\Delta)} \langle x_i\ | \ i\notin\sigma \rangle

where the last one gives a minimal prime decomposition of $I_\Delta$.

Let $\Delta_{\mathcal{Q},\mm,\uu}$ be the simplicial complex determined by $I_{\mathcal{Q},\mm,\uu}$ (so
${\rm init }(I_{\mathcal{Q},\mm,\uu})=I_{\Delta_{\mathcal{Q},\mm,\uu}}$).

We will introduce a new combinatorial model, called concurrent vertex maps, as an analogue of nonintersecting lattice paths.[A concurrent vertex map consists of each point that is in a common section of a horizontal path and a vertical path. The name is chosen due to its analogy with a concurrency in a road network, which refers to “an instance of one physical roadway bearing two or more different route numbers”.
See Wikipidea page <https://en.wikipedia.org/wiki/Concurrency_(road)>]

The precise definition is given in <ref>. Roughly speaking,

(a) a  road map is, on each rectangular array of the size of the matrix $A_\gamma$,
a family of nonintersecting paths $H^\gamma_p$ (for various $p$) from the left side to the right side (which we called horizontal paths), together with
a family of nonintersecting paths $V^\gamma_q$ (for various $q$)  from the top side to the bottom side (which we called vertical paths);

(b) a road map is called straight if each corner of a horizontal path lies in a vertical path, and each corner of a vertical path lies in a horizontal path;

(c) for a straight road map, the corresponding concurrent vertex map is the set of lattice points that are both in horizontal and vertical paths.

Below is an example of a concurrent vertex map.

Consider the bipartite determinantal ideal $I_{\mathcal{Q},\mm,\uu}$  where $\mathcal{Q}$ is

\begin{tikzpicture}
\graph[nodes={draw,circle},edges={-{Stealth[]}}] {
2 -> 1,
3 -> 1,
4 -> 1
\end{tikzpicture}

$\mm=(3,2,2,2)$, $\uu=(2,1,1,1)$. The ideal is generated by

– all 2 minors in
\end{bmatrix}
\end{bmatrix}
\end{bmatrix}

– and all 3 minors in
$A_1=[X_1 \ X_2\ X_3 ] =
\begin{bmatrix}
\end{bmatrix}

In Figure <ref> Left, we illustrate an example of a straight road map on $A_1$, which consists of two nonintersecting horizontal paths $H^1_1, H^1_2$ and three nonintersecting vertical paths $V^1_1,V^1_2,V^1_3$. It satisfies the condition that each corner of a horizontal path lies in a vertical path, and each corner of a vertical path lies in a horizontal path.  Figure <ref> Right shows the corresponding concurrent vertex map, which consists of points that lie on both a horizontal path and a vertical path.

[gray] (0,0) grid (1,2);
[gray] (2,0) grid (3,2);
[gray] (4,0) grid (5,2);

[blue,densely dotted,very thick](-.2,1)–(3,1)–(3,2)–(5,2);
[blue,densely dotted,very thick](-.2,0)–(4,0)–(4,1)–(5,1);
(-.2,1) node [left] $H^1_1$;
(-.2,0) node [left] $H^1_2$;

[red,densely dotted,very thick](1,2)–(1,1)–(0,1)–(0,0);
[red,densely dotted,very thick](3,2)–(3,0)–(2,0);
[red,densely dotted,very thick](5,2)–(5,1)–(4,1)–(4,0);
(1,2) node [above] $V^1_1$;
(3,2) node [above] $V^1_2$;
(5,2) node [above] $V^1_3$;

[draw=gray] (-.5,-.5) rectangle ++(2,3);
[draw=gray] (1.5,-.5) rectangle ++(2,3);
[draw=gray] (3.5,-.5) rectangle ++(2,3);
at (0,0) .;
at (1,0) +;
at (2,0) .;
at (3,0) .;
at (4,0) .;
at (5,0) +;
at (0,1) .;
at (1,1) .;
at (2,1) +;
at (3,1) .;
at (4,1) .;
at (5,1) .;
at (0,2) +;
at (1,2) +;
at (2,2) +;
at (3,2) .;
at (4,2) +;
at (5,2) .;

An example of concurrent vertex map. Left: a straight road map; Right: the corresponding concurrent vertex map.

As we shall see, a concurrent vertex map uniquely determines a straight road map; that is to say, there is a unique way to “connect the dots” in a concurrent vertex map to obtain the corresponding horizontal and vertical paths.  Indeed, we give several equivalent conditions for concurrent vertex maps  in Proposition <ref>.

A main result of the paper is to give the following combinatorial description of ${\rm init }(I_{\mathcal{Q},\mm,\uu})$.  The definitions of “${\bf u}$-compatible” and “concurrent vertex map” are given in Definition <ref>.
The proof is given at the end of <ref>.
(Prime decomposition)
The faces and facets of the Stanley-Reisner simplicial complex $\Delta_{\mathcal{Q},\mm,\uu}$ are determined as follows:

$C\subseteq L$ is a face of $\Delta_{\mathcal{Q},\mm,\uu}$ if and only if $C$ is ${\bf u}$-compatible.

$C\subseteq L$ is a facet of $\Delta_{\mathcal{Q},\mm,\uu}$ if and only if $C$ is a concurrent vertex map.

$${\rm init }(I_{\mathcal{Q},\mm,\uu})=\bigcap_C \; \big\langle x_{ij}^{(k)} \ | \  (i,j,k)\notin C \big\rangle$$

where $C$ runs over all concurrent vertex maps.

Using the above combinatorial description, we prove the following properties of  the Stanley-Reisner simplicial complexes $\Delta_{\mathcal{Q},\mm,\uu}$ and the ideal $I_{\mathcal{Q},\mm,\uu}$: shellability is proved in Corollary <ref>, vertex decomposability is proved in Proposition <ref>, and homeomorphism to balls is proved in  Proposition <ref>.

The Stanley-Reisner simplicial complexes $\Delta_{\mathcal{Q},\mm,\uu}$ are shellable, vertex decomposable, and homeomorphic to balls.

There are some interesting and immediate consequences of Theorems <ref> and  <ref>:

– the bipartite determinantal ideals $I_{\mathcal{Q},\mm,\uu}$ are Cohen-Macaulay;

– we obtain combinatorial formulas for the Hilbert series and multiplicity of the quotient ring ${\bf k}[X]/I_{\mathcal{Q},\mm,\uu}$ (see Corollary <ref>);

– we recover some results on $t$-secant varieties by Conca, De Negri, and Stojanac [5] (see <ref>).

Due to their close relation with classical determinantal varieties, Nakajima's graded quiver varieties, cluster algebras, and nonintersecting paths, we strongly believe that the bipartite determinantal ideals and the corresponding combinatorial model will garner increased attention for further study.

We would like to point out some of the results are obtained in [6] and their unpublished preprint.

The paper is organized as follows.

In 2 we introduce the notion of road maps and concurrent vertex maps.

In 3 we study the combinatorial property of the simplicial complex $\Delta _{\mathcal {Q},{\mathbf {m}},{\mathbf {u}}}$.

In 4 we provide a formula for the Hilbert series and multiplicity of the quotient ring ${\bf k}[X]/I_{\mathcal{Q},\mm,\uu}$.

We conclude the paper with examples, algorithms, and discussions in 5.

Acknowledgments. The author gained valuable insights from the collaborated work with Alex Yong on Kazhdan-Lusztig ideals and Schubert varieties,  upon which the current work is based; the author also expresses gratitude for discussions with Patricia Klein and Allen Knutson.
Computer calculations were performed using Macaulay2 [9] and SageMath [19].

§ CONCURRENT VERTEX MAPS

§.§ Notations

First we introduce some notations:

* For $i,j\in\mathbb{Z}$, let $[i,j]\subset \mathbb{R}$ be the closed interval between $i,j$, and let $[i,j]_\mathbb{Z}=[i,j]\cap\mathbb{Z}$; we also use similar notations for open intervals and half-open half-closed intervals.

* Informally, we think the $r$ matrices $X^{(1)},\dots, X^{(r)}$ as “pages” in a “book". The $k$-th page contains $X^{(k)}$, and we sometimes view it as a rectangle region ${\rm Page}_k:=[1,m_{\target(h_k)}]\times[1,m_{\source(h_k)}]$; a lattice point $(i,j)$ on ${\rm Page}_k$ corresponds to the variable $x_{ij}^{(k)}$.

(Warning!) In this paper, we use the following (unusual) coordinate system to be consistent with the labelling of entries in a matrix:

[<->,thick] (0,-1) node (yaxis) [right] $x$
|- (1,0) node (xaxis) [below] $y$;

* We frequently need to convert from to the position in $A_\gamma$ to the corresponding position in $X$. For that purpose,
$$L:=\{(i,j,k)\in\mathbb{Z}^3 \ | \  1\le k\le r, (i,j)\in [1,m_{\target(h_k)}]_\mathbb{Z}\times [1,m_{\source(h_k)}]_\mathbb{Z}\}; $$

for $\gamma\in {\rm V}_\mathcal{Q}$,
define a map

$$\phi_{\gamma}: [1,a_\gamma]_\mathbb{Z}\times[1,b_\gamma]_\mathbb{Z}\to L, \quad
(p,q)\mapsto (i,j,k) \textrm{ if the $(p,q)$-entry of $A_\gamma$ is $x_{ij}^{(k)}$}.$$

Note that the following two induced maps are both bijective:

$$\phi_{\rm target}:
\bigcup_{\alpha\in {\rm V}_{\rm target}}
\Big(\alpha,[1,a_\alpha]_\mathbb{Z}\times[1,b_\alpha]_\mathbb{Z}\Big)\to L,
\quad
(\alpha,i,j)\mapsto \phi_{\alpha}(i,j)

$$\phi_{\rm source}:
\bigcup_{\beta\in {\rm V}_{\rm source}}
\Big(\beta, [1,a_\beta]_\mathbb{Z}\times[1,b_\beta]_\mathbb{Z}\Big)\to L,
\quad

So if $h_k$ is an arrow $\beta\to \alpha$, then both $\phi^{-1}_\alpha(i,j,k)$ and $\phi^{-1}_\beta(i,j,k)$ are uniquely defined.

§.§ Straight road maps

In a rectangular array $L$ of lattice points (which are called vertices),  we define a SW-NE path $P\rightsquigarrow Q$ to be a lattice path from its SW endpoint $P$ to its NE endpoint $Q$, with steps either to east along vector $(0,1)$ or to north along vector $(-1,0)$. If we reverse the orientation then we get a NE-SW path $Q\rightsquigarrow P$. By a  path we mean either a SW-NE path or a NE-SW path. The length of a path refers to the number of length 1 edges in the path; the length is 0 if its two endpoints coincide.

A corner of a path $H$ is a vertex $R$ in the path that is adjacent to both a horizontal and a vertical edge of $H$.
A corner $R$ is called a NW corner of $H$ if both points $R+(1,0)$ and $R+(0,1)$ are in $H$; otherwise both $R-(1,0)$ and $R-(0,1)$ must be in $H$, in which case $R$ is called a SE corner of $H$.

A collection $\{H_i\}_{i=1}^u$ of $u$ paths is said to be nonintersecting if no vertex is contained in two paths; it is said to be connecting $(X_i)_{i=1}^u$ and $(Y_i)_{i=1}^u$ if $H_i$ has endpoints $X_i$ and $Y_i$ for each $i$.

The restriction of a path $H$ to ${\rm Page}_k$ is denoted $H|_k$. The restriction of a point $P$ to ${\rm Page}_k$ is denoted $P|_k$.  Analogously, for $C\subseteq L$, denote $C|_k$ the restriction of $C$ to ${\rm Page}_k$.

Give a lattice point $P$, we say that a point $Q=P+(i,j)$ is

– east of $P$ if $i=0, j>0$ (and similarly for west, south, north);

– weakly east of $P$ if $i=0, j\ge 0$ (and similarly for weakly west, weakly south, weakly north);

– NE of $P$ if $i<0, j>0$ (and similarly for NW, SE, SW);

– weakly NE of $P$ if $i\le 0, j\ge 0$ (and similarly for  weakly NW, weakly SE, weakly SW).

A road map $(\{H^\alpha_{p}\}, \{V^\beta_{q}\})=\big(\{H^\alpha_{p}\}_{\alpha\in {\rm V}_{\rm target},  1\le p\le u_\alpha}, \{V^\beta_{q}\}_{\beta \in {\rm V}_{\rm source}, 1\le q\le u_\beta}\big)$ of rank $\uu$ consists of:

– a collection of $u_\alpha$ nonintersecting paths $\{H^\alpha_{p}\}_{p=1}^{u_\alpha}$ (called horizontal paths) of $A_\alpha$ connecting $\big((a_\alpha-u_\alpha+p,1)\big)_{p=1}^{u_\alpha}$ and $\big((p,b_\alpha)\big)_{p=1}^{u_\alpha}$ for $\alpha\in {\rm V}_{\rm target}$, and

– a collection of $u_\beta$ nonintersecting paths $\{V^\beta_{q}\}_{q=1}^{u_\beta}$ (called vertical paths) of $A_\beta$ connecting $\big((1,b_\beta-u_\beta+q)\big)_{q=1}^{u_\beta}$ and $\big((a_\beta,q)\big)_{q=1}^{u_\beta}$ for $\beta\in {\rm V}_{\rm source}$.

A road map is straight  if each corner of a horizontal path lies in a vertical path, and each corner of a vertical path lies in a horizontal path. More precisely: for each $1\le k\le r$,
if a point $P$ in is a corner of $H^{\target(h_k)}_p$, then $P|_k\in \bigcup_q V^{\source(h_k)}_q|_k$;
if $Q$ is a corner of $V^{\source(h_k)}_q$, then $Q|_k\in \bigcup_p H^{\target(h_k)}_p|_k$.

Since the terminologies “horizontal” and “vertical” are used in the above definition, we will say that a path is “straight horizontal” if it contains not vertical edge; similarly, a path is “straight vertical” if it contains no horizontal edge.

Note that if for some $\alpha\in V_{\rm target}$, $u_\alpha=a_\alpha$, then the horizontal paths $H^\alpha_p$ are straight horizontal; if for some $\beta\in V_{\rm source}$,   $u_\beta=b_\beta$, then the vertical paths $V^\beta_q$ are straight vertical. Those paths have no corners.

We have the following useful characterization of straight road maps.

A road map $(\big(\{H^\alpha_{p}\}, \{V^\beta_{q}\})$ is straight if and only if all of the following conditions hold:

(a) For an edge $h_k$ in $Q$, let $\alpha=\target(h_k)$ and $\beta=\source(h_k)$. The intersection $H^\alpha_{p}|_k \cap V^\beta_q|_k$ is a connected path $P^k_{pq}\rightsquigarrow Q^k_{pq}$ where $P^k_{pq}$ (resp. $Q^k_{pq}$) is its SW (resp. NE) endpoint.

Let $r_1<\cdots<r_s$ be all the indices such that $h_{r_1},\dots,h_{r_s}$ are all the arrows with target $\alpha$.

Then the path $H^\alpha_{p}$ is determined as follows:
(see Figure <ref>)

$ $

start at the SW endpoint $(a_\alpha-u_\alpha+p,1)$;

for $i$ from $1$ to $s$ do:

for $j$ from $1$ to $u_{\source(h_{r_i})}$ do:

go east to $P^{r_i}_{pj}$;

go along the path $P^{r_i}_{pj} \rightsquigarrow Q^{r_i}_{pj}$;

go east to the NE endpoint $(p,b_i)$.

Let $r'_1<\cdots<r'_t$ be all the indices such that $h_{r'_1},\dots,h_{r'_t}$ are all the arrows with source $\beta$.

Then the path $V^\beta_{q}$ is determined as follows:

$ $

start at the NE endpoint  $(1,b_\beta-u_\beta+q)$;

for $i$ from $1$ to $t$ do:

for $j$ from $1$ to $u_{\target(h_{r'_i})}$ do:

go south to $Q^{r'_i}_{jq}$;

go along the path $Q^{r'_i}_{jq} \rightsquigarrow P^{r'_i}_{jq}$;

go south to the SW endpoint $(a_i,q)$.

[gray] (0,0.5) rectangle (5.5,5.5);
[gray] (6,0.5) rectangle (11.5,5.5);
[gray] (12,0.5) rectangle (17.5,5.5);

[blue,densely dotted,thick](1.5,0.5) node[scale=.1] (v6)  – (0,0.5);
[blue,densely dotted,thick](2,1) node[scale=.1]  (v4)  – (0,1);
[blue,densely dotted,thick](3,1.5) node[scale=.1]  (v2)  – (0,1.5);
[blue,densely dotted,thick](2,0.5) node[scale=.1]  (v5)  – (3.5,0.5) node[scale=.1]  (v12) ;
[blue,densely dotted,thick](3,1) node[scale=.1]  (v3)  – (4.5,1) node[scale=.1]  (v10) ;
[blue,densely dotted,thick](4,2.5) node[scale=.1]  (v1)  – (5,2.5) node[scale=.1]  (v8) ;
[blue,densely dotted,thick](5,2) node[scale=.1]  (v9)  – (7,2) node[scale=.1]  (v16) ;
[blue,densely dotted,thick](5.5,3.5) node[scale=.1]  (v7)  – (8,3.5) node[scale=.1]  (v14)   (4.5,0.5) node[scale=.1]  (v11)  – (6.5,0.5) node [scale=.1] (v18) ;
[blue,densely dotted,thick](7,1.5) node[scale=.1]  (v17)  – (8.5,1.5) node[scale=.1]  (v24) ;
[blue,densely dotted,thick](9,4.5) node[scale=.1]  (v13)  – (10.5,4.5) node [scale=.1] (v20) ;
[blue,densely dotted,thick](11,5.5) node[scale=.1]  (v19)  – (13.5,5.5) node[scale=.1]  (v26) ;
[blue,densely dotted,thick](14.5,5.5) node[scale=.1]  (v25)  – (15,5.5) node[scale=.1]  (v32) ;
[blue,densely dotted,thick](17,5.5) node[scale=.1]  (v31)  – (17.5,5.5);
[blue,densely dotted,thick](8,3) node [scale=.1] (v15)  – (9.5,3) node[scale=.1]  (v22)   (10.5,4) node[scale=.1]  (v21)  – (13,4) node[scale=.1]  (v28) ;
[blue,densely dotted,thick](13.5,5) node [scale=.1] (v27)  – (14.5,5) node [scale=.1] (v34) ;
[blue,densely dotted,thick](15,5) node[scale=.1]  (v33)  – (17.5,5);
[blue,densely dotted,thick](9.5,2) node[scale=.1]  (v23)  – (12.5,2) node [scale=.1] (v30)   (13,3) node[scale=.1]  (v29)  – (13.5,3) node[scale=.1]  (v36) ;
[blue,densely dotted,thick](14.5,4.5) node[scale=.1]  (v35)  – (17.5, 4.5);
[red,densely dotted,thick](4, 6) – (v1)  (v2) – (v3)  (v4) – (v5)  (v6) – (1.5,0);
[red,densely dotted,thick](5.5, 6) – (v7)  (v8) – (v9)  (v10) – (v11)  (v12) – (3.5,0);
[red,densely dotted,thick](9, 6) – (v13)  (v14) – (v15)  (v16) – (v17)  (v18) – (6.5,0);
[red,densely dotted,thick](11,6) – (v19)  (v20) – (v21)  (v22) – (v23)  (v24) – (8.5,0);
[red,densely dotted,thick](14.5, 6) – (v25)  (v26) – (v27)  (v28) – (v29)  (v30) – (12.5,0);
[red,densely dotted,thick](17, 6) – (v31)  (v32) – (v33)  (v34) – (v35)  (v36) – (13.5,0);
[thick] (v6) – (v5);
[thick] (v4) – (v3);
[thick] (v12) – (v11);

[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v2) – (v1);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v10) – (v9);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v8) – (v7);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v14) – (v13);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm](v20) – (v19);
[thick] (v26) – (14.5,5.5);
[thick] (v32) – (v31);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v16) – (v15);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v22) – (v21);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v28) – (v27);
[thick] (v34) – (v33);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v18) – (v17);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v24) – (v23);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v30) – (v29);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm]  (v36) – (v35);

(v2) node [above left] $P^{r_1}_{11}$;
(v1) node [above left] $Q^{r_1}_{11}$;

(v7) node [above left] $Q^{r_1}_{12}$;
(v8) node [above left] $P^{r_1}_{12}$;

(2,0.9) node [above] $P^{r_1}_{21}$;
(3,1.1) node [below] $Q^{r_1}_{21}$;

(1.5,.4) node [above] $P^{r_1}_{31}$;
(v5) node [below] $Q^{r_1}_{31}$;

(v9) node [left] $Q^{r_1}_{22}$;
(v10) node [above left] $P^{r_1}_{22}$;

(v11) node [below] $Q^{r_1}_{32}$;
(3.5,.4) node [above] $P^{r_1}_{32}$;

(v13) node [above left] $Q^{r_2}_{11}$;
(v14) node [above left] $P^{r_2}_{11}$;

(v15) node [left] $Q^{r_2}_{21}$;
(v16) node [above left] $P^{r_2}_{21}$;

(v17) node [left] $Q^{r_2}_{31}$;
(v18) node [right] $P^{r_2}_{31}$;

(v19) node [left] $Q^{r_2}_{12}$;
(v20) node [right] $P^{r_2}_{12}$;

(v21) node [left] $Q^{r_2}_{22}$;
(v22) node [right] $P^{r_2}_{22}$;

(v23) node [above left] $Q^{r_2}_{32}$;
(v24) node [above left] $P^{r_2}_{32}$;

(v25) node [above left] $Q^{r_3}_{11}$;
(v26) node [above left] $P^{r_3}_{11}$;

(v27) node [left] $Q^{r_3}_{21}$;
(v28) node [right] $P^{r_3}_{21}$;

(v29) node [left] $Q^{r_3}_{31}$;
(v30) node [right] $P^{r_3}_{31}$;

(v31) node [below] $Q^{r_3}_{12}$;
(v32) node [above ] $P^{r_3}_{12}$;

(v33) node [below] $Q^{r_3}_{22}$;
(v34) node [below left] $P^{r_3}_{22}$;

(v35) node [below right] $Q^{r_3}_{32}$;
(v36) node [right] $P^{r_3}_{32}$;

(0,1.5) node [left] $H^\alpha_1$;
(0,1) node [left] $H^\alpha_2$;
(0,0.5) node [left] $H^\alpha_3$;

(4,6) node [above] $V^{\mathrm{s}(h_{r_1})}_1$;
(5.5,6) node [above] $V^{\mathrm{s}(h_{r_1})}_2$;

(9,6) node [above] $V^{\mathrm{s}(h_{r_2})}_1$;
(11,6) node [above] $V^{\mathrm{s}(h_{r_2})}_2$;

(14.5,6) node [above] $V^{\mathrm{s}(h_{r_3})}_1$;
(17,6) node [above] $V^{\mathrm{s}(h_{r_3})}_2$;

An example of $H^\alpha_p$'s in a straight road map

(0,0) rectangle (10,6);
(3,2) node (v1)  – (2.5,2) – (2.5,1.5) – (1.5,1.5)  ;
(6.5,4) node (v2)  – (6.5,4.5) – (8,4.5) – (8,5) – (8.5,5) – (8.5,5.5) – (9,5.5);
[red,dotted, thick] (v1) – (4.5,2) – (4.5,2.5) – (6,2.5) – (6,3.5) – (6.5,3.5) – (v2);
[blue, dotted, thick] (v1) – (3,3) – (4,3) – (4,3.5) – (5,3.5) – (5,4) – (v2);
(1.5,1.5) node [below] $P$;
(v1) node [below] $Q$;
(v2) node [right] $P'$;
(9,5.5) node [below] $Q'$;
(3,3) node [below right] $R$;
[red, dotted, thick] (3.5,5) – (3.5,3.5) – (3,3.5) – (3,3) – (2,3) – (2,2.5) – (0.5,2.5)  ;
(3.5,4.5) node [red,left] $V^\beta_{q'}|_k$;
(7,3) node [red, below] $P'\stackrel{V}{\rightsquigarrow} Q$;
(5,4) node [blue,above] $Q\stackrel{H}{\rightsquigarrow} P'$;

(0,0) rectangle (10,6);
(3,2) node (v1)  – (2.5,2) – (2.5,1.5) – (1.5,1.5)  ;
(6.5,4) node (v2)  – (6.5,4.5) – (8,4.5) – (8,5) – (8.5,5) – (8.5,5.5) – (9,5.5);
[blue,dotted, thick] (v1) – (4.5,2) – (4.5,2.5) – (6,2.5) – (6,3.5) – (6.5,3.5) – (v2);
[red, dotted, thick] (v1) – (3,3) – (4,3) – (4,3.5) – (5,3.5) – (5,4) – (v2);
(1.5,1.5) node [below] $P$;
(v1) node [below] $Q$;
(v2) node [right] $P'$;
(9,5.5) node [below] $Q'$;
(3,3) node [below right] $R$;
[blue, dotted, thick] (3.5,5) – (3.5,3.5) – (3,3.5) – (3,3) – (2,3) – (2,2.5) – (0.5,2.5)  ;
(3.5,4.5) node [red,left] $H^\alpha_{q}|_k$;
(5,4) node [red,above] $P'\stackrel{V}{\rightsquigarrow} Q$;
(7,3) node [blue, below] $Q\stackrel{H}{\rightsquigarrow} P'$;

Proof of Lemma <ref>. Left: Case 1; Right: Case 2.

Assume (a)(b)(c) are satisfied. By (b), any corner of $H^\alpha_p$ lies in $P^{r_k}_{p\ell} \rightsquigarrow Q^{r_k}_{p\ell}$ for some $k,\ell$, therefore lies in a vertical path. Similarly by (c), any corner of $V^\beta_q$ lies in a horizontal path. So the road map is straight.

Next we assume the road map is straight.

We first show that (a) holds. Let $(p,q)$ be the minimum pair in the dictionary order such that $H^\alpha_{p}|_k \cap V^\beta_q|_k$ is not connected.
Let $P\rightsquigarrow Q$ and $P'\rightsquigarrow Q'$ be the first two SW-most connected components of  this  intersection.
Denote by $Q\stackrel{H}{\rightsquigarrow} P'$ the subpath of $H^\alpha_p|_k$ from $Q$ to $P'$; by $P'\stackrel{V}{\rightsquigarrow} Q$ the subpath of $V^\beta_q|_k$ from $P'$ to $Q$.
We consider two cases:

Case 1. $P'\stackrel{V}{\rightsquigarrow} Q$ lies to the SE of $Q\stackrel{H}{\rightsquigarrow} P'$ (see Figure <ref> Left).
Let $R$ be the NW corner of $H^\alpha_p|_k$ in the interior of $Q\stackrel{H}{\rightsquigarrow} P'$ that is closest to $Q$. By definition of straightness, $R$ lies in some $V^{\beta}_{q'}|_k$. Moreover, $q'<q$ since $R$ is to the north of $Q$, and $Q$ lies in $V^\beta_q|_k$.
This implies $(p,q')<(p,q)$ in the dictionary order, and the intersection $H^\alpha_p|_k\cap V^\beta_{q'}|_k$ is not connected; indeed,  the intersection contains $R$ and also a point that is weakly SW of $P$ (because $H^\alpha_p|_k$ reaches the left boundary and $V^\beta_{q'}|_k$ reaches the bottom boundary), but not $P$. This contradicts the choice of $(p,q)$.

Case 2.  $P'\stackrel{V}{\rightsquigarrow} Q$ lies to the NW of $Q\stackrel{H}{\rightsquigarrow} P'$ (see Figure <ref> Right). The proof is similar to Case 1.
Let $R$ be the NW corner of $V^\beta_q|_k$ in the interior of $P'\stackrel{V}{\rightsquigarrow} Q$ that is closest to $Q$. Then $R$ lies in some $H^{\alpha}_{p'}|_k$ with $p'<p$, and $H^\alpha_{p'}|_k\cap V^\beta_{q}|_k$ is not connected, contradicting the choice of $(p,q)$.

This proves (a).

Next we show (b).

The path $H^\alpha_p$ starts at $(a_\alpha-u_\alpha+p,1)$. It cannot make a turn before arriving at $P^{r_1}_{p,1}$ by the definition of straight road map. So the subpath from $(a_\alpha-u_\alpha+p,1)$ to  $P^{r_1}_{p,1}$ is either straight horizontal or straight vertical. The former case is what we expected. In the latter case,  $V^{\source(h_{r_1})}_1|_k$ passes through $P^{r_1}_{p,1}$, so it stays in the left-most column after it going below $P^{r_1}_{p,1}$, therefore passes the point $(a_\alpha-u_\alpha+p,1)$. This forces $P^{r_1}_{p,1}=(a_\alpha-u_\alpha+p,1)$, so it is still what we expected.

The path $H^\alpha_p$ then goes along the path $P^{r_1}_{p,1} \rightsquigarrow Q^{r_1}_{p,1}$ and arrives at  $Q^{r_1}_{p,1}$.

After that, consider $Q^{r_1}_{p,1}\stackrel{H}{\rightsquigarrow} P^{r_1}_{p,2}$. It cannot make any turns, so is either straight horizontal or straight vertical. The former case is what we expected. So we assume the latter case, that is, $P^{r_1}_{p,2}$ is to the north of  $Q^{r_1}_{p,1}$.  Denote $\beta=\source(h_{r_1})$; then $P^{r_1}_{p,2}$ lies in $V^\beta_2|_k$, $Q^{r_1}_{p,1}$ lies in $V^\beta_1|_k$.  The path  $V^\beta_2|_k$ must pass through a point weakly left of $Q^{r_1}_{p,1}$, contradicting the fact that  $V^\beta_2|_k$ is on the right side of $V^\beta_1|_k$.

The rest of (b) is proved in the same way.

(c) is proved similarly to (b), so we skip.

§.§ Concurrent vertex maps and $\uu$-Compatible sets

A subset $C\subseteq L$   is called a concurrent vertex map if there exists a straight road map  $(\{H^i_{p}\}, \{V^j_{q}\})$ such that

\begin{equation}\label{eq:Ck}
C|_k= \Big( \bigcup_{p=1}^{u_{\target(h_k)}} H^{\target(h_k)}_p|_k\Big)\
\bigcap\
\Big( \bigcup_{q=1}^{u_{\source(h_k)}} V^{\source(h_k)}_q|_k\Big)
\bigcap\mathbb{Z}^2, \quad \text{ for } k=1,\dots,r.
\end{equation}

We say that a finite subset $S\subset\mathbb{Z}\times\mathbb{Z}$ is a diagonal chain of size $s$ if $S=\{(i_1,j_1),\dots,(i_s,j_s)\}$ satisfies $i_1<i_2<\cdots<i_s$ and $j_1<j_2<\cdots<j_s$.

Fix $C \subseteq L$.

For each $\alpha\in {\rm V}_{\rm target}$, define a subset $C^\alpha = \phi_\alpha^{-1}(C) \subseteq [1,a_\alpha]_\mathbb{Z}\times [1,b_\alpha]_\mathbb{Z}$.
For $(i,j,k)\in\mathbb{Z}^3$, let $\alpha={\rm t}(h_k)$, $(i,j')=\phi_\alpha^{-1}(i,j,k)$, and define the following constants $r_{ijk}$, $\bar{r}_{ijk}$, ... (later we may
use $r_{ijk}(C)$, $\bar{r}_{ijk}(C)$, $\dots$ in place of  $r_{ijk}$, $\bar{r}_{ijk}$, $\dots$ to indicate their dependence on $C$; we also use $r_P$ to denote $r_{ijk}$ if $P=(i,j,k)$, and similar for others.)

$r_{ijk}=$ max size of diagonal chains in $C^\alpha$ contained in $(-\infty,i-1]_\mathbb{Z}\times (-\infty,j'-1]_\mathbb{Z}$;

$\bar{r}_{ijk}=\max(r_{ijk},\min(i-1,u_{\alpha}-1-\min(a_\alpha-i,b_\alpha-j')))=$ max size of diagonal chains of $\bar{C}^\alpha:=C^\alpha\cup \{(a_\alpha-u_\alpha+t,-u_\alpha+t) | 1\le t\le u_\alpha\}\cup\{(t,b_\alpha-u_\alpha+t)|1\le t\le u_\alpha\}$ contained in $(-\infty,i-1]_\mathbb{Z}\times(-\infty,j'-1]_\mathbb{Z}$;

$s_{ijk}=$ max size of diagonal chains of $C^\alpha$ contained in $[i+1,\infty)_\mathbb{Z}\times [j'+1,\infty)_\mathbb{Z}$;

$\bar{s}_{ijk}=\max(s_{ijk},\min(a_\alpha-i,u_{\alpha}-\min(i,j')))=$   max size of diagonal chains of $C^\alpha\cup \{(a_\alpha-u_\alpha+t,t) | 1\le t\le u_\alpha\}\cup\{(t,b_\alpha+t)|1\le t\le u_\alpha\}$ contained in $[i+1,\infty)_\mathbb{Z}\times [j'+1,\infty)_\mathbb{Z}$;

Similarly, for $\beta\in {\rm V}_{\rm source}$,  define a subset $C^\beta = \phi_\beta^{-1}(C) \subseteq [1,a_\beta]_\mathbb{Z}\times [1,b_\beta]_\mathbb{Z}$.
For $(i,j,k)\in\mathbb{Z}^3$, let $\beta={\rm s}(h_k)$, $(i,j')=\phi_\beta^{-1}(i,j,k)$, and

$r'_{ijk}=$ max size of diagonal chains in $C^\beta$ contained in $(-\infty,i'-1]_\mathbb{Z}\times (-\infty,j-1]_\mathbb{Z}$;

$\bar{r}'_{ijk}=\max(r'_{ijk},\min(j-1,u_{\beta}-1-\min(b_\beta-j,a_\beta-i')))=$max size of diagonal chains of $C^\beta\cup \{(-u_\beta+t,b_\beta-u_\beta+t) | 1\le t\le u_\beta\}\cup\{(a_\beta-u_\beta+t,t)|1\le t\le u_\beta\}$ contained in $(-\infty,i'-1]_\mathbb{Z}\times(-\infty,j-1]_\mathbb{Z}$;

$s'_{ijk}=$ max size of diagonal chains of $C^\beta$ contained in $[i'+1,\infty)_\mathbb{Z}\times [j+1,\infty)_\mathbb{Z}$.

$\bar{s}'_{ijk}=\max(s'_{ijk},\min(b_\beta-j,u_{\beta}-\min(i',j)))=$ max size of diagonal chains of $C^\beta\cup \{(t,b_\beta-u_\beta+t) | 1\le t\le u_\beta\}\cup\{(a_\beta+t,t)|1\le t\le u_\beta\}$ contained in $[i'+1,\infty)_\mathbb{Z}\times [j+1,\infty)_\mathbb{Z}$.

We say that a subset $C\subseteq L$ is $\uu$-compatible if for each $\gamma\in {\rm V}_\mathcal{Q}$, $C^\gamma$ does not contain any diagonal chain of size $(u_\gamma+1)$.

We say that $C\subseteq L$ is maximal $\uu$-compatible if $C$ is $\uu$-compatible and there is no $\uu$-compatible $C'$ satisfying $C\subsetneq C'\subseteq L$.

For $C\subseteq L$, the following are equivalent:

(i) $C$ is a concurrent vertex map;

(ii) $C$ is maximal $\uu$-compatible;

(iii) $C$ is $\uu$-compatible and

\begin{equation}\label{eq:cardinality of max C}
|C|= N_{\mathcal{Q},\mm,\uu}:= \sum_k u_{\source(h_k)}u_{\target(h_k)}+\sum_{\alpha\in {\rm V}_{\rm target}}u_\alpha(a_\alpha-u_\alpha)+\sum_{\beta\in {\rm V}_{\rm source}}u_\beta(b_\beta-u_\beta)
\end{equation}

(iv) $C$ satisfies the condition that a point $(i,j,k)\in L$ is in $C$ if and only if $r_{ijk}+s_{ijk}<u_{\target(h_k)}$ and $r'_{ijk}+s'_{ijk}<u_{\source(h_k)}$).

(v) $C$ satisfies the condition that $\bar{r}_{ijk}+\bar{s}_{ijk}\in\{u_{\target(h_k)}-1,u_{\target(h_k)}\}$ and $\bar{r}'_{ijk}+\bar{s}'_{ijk}\in\{u_{\source(h_k)}-1,u_{\source(h_k)}\}$, and $(i,j,k)\in L$ is in $C$ if and only if $\bar{r}_{ijk}+\bar{s}_{ijk}=u_{\target(h_k)}-1$ and $\bar{r}'_{ijk}+\bar{s}'_{ijk}=u_{\source(h_k)}-1$.

Moreover, if $C$ is a concurrent vertex map, then the corresponding road map is uniquely determined by the following conditions:

$(i,j)\in H^{\target(h_k)}_p|_k$ if and only if $\bar{r}_{ijk}=p-1$ and $\bar{s}_{ijk}=u_{\target(h_k)}-p$;

$(i,j) \in V^{\source(h_k)}_q|_k$ if and only if $\bar{r}'_{ijk}=q-1$ and  $\bar{s}'_{ijk}=u_{\source(h_k)}-q$.

We first prove several lemmas (Lemmas <ref>, <ref>, <ref>), and then prove of the above proposition at the end of this section.

Let $a,b,u$ be positive integers.

(i)  Assume $u\le \min(a,b)$.
Let $X_p=(a-u+p,p)$ to $Y_p=(p,b-u+p)$ for $1\le p\le u$.
Let $R_{\rm hex}\subseteq\mathbb{R}^2$ be the closed hexagon region with vertices
$(1,1)$, $X_1$, $X_u$, $(a,b)$, $Y_u$, $Y_1$, and let $C\subseteq R_{\rm hex}\cap\mathbb{Z}^2$ be a set of lattice points. Then
“there exits a collection of $u$ nonintersecting paths connecting $(X_p)_{p=1}^u$ and $(Y_p)_{p=1}^u$ whose union contains $C$”
if and only if
“all diagonal chains of $C$ have sizes $\le u$”.

(1,9) node[]$R$;
(0,10) node[left]$(1,1)$;
(12,0) node[right]$(a,b)$;
(0,0) rectangle (12,10);
[fill] (0,3) circle(3pt); (0,3) node[left]$X_1=(a-u+1,1)$;
[fill] (1,2) circle(3pt); (1,2) node[left]$X_2=(a-u+2,2)$;
[fill] (1.7,1.3) circle(2pt);
[fill] (2,1) circle(2pt);
[fill] (2.3,0.7) circle(2pt);
[fill] (3,0) circle(3pt); (3,0) node[below ]$X_u=(a,u)$;

[fill] (9,10) circle(3pt); (9,10) node[above]$Y_1=(1,b-u+1)$;
[fill] (10,9) circle(3pt); (10,9) node[right]$Y_2=(2,b-u+2)$;
[fill] (10.7,8.3) circle(2pt);
[fill] (11,8) circle(2pt);
[fill] (11.3,7.7) circle(2pt);
[fill] (12,7) circle(3pt); (12,7) node[right]$Y_u=(u,b)$;

[red,thick] (0,3)– (1,3)–(1,5) – (2,5)–(2,7)–(6,7)–(6,10)–(9,10)  ;
[red,thick] (1,2)– (3,2) – (3,4)–(5,4)–(5,5)–(8,5)–(8,8)–(10,8)–(10,9)  ;
[red,thick] (3,0)– (6,0) – (6,2)–(10,2)–(10,6)–(11,6)–(11,7)–(12,7)  ;

(0,10) node[left]$(1,1)$;
(12,0) node[right]$(a,b)$;
(0,0) rectangle (12,10);
[fill] (0,3) circle(3pt);
[fill] (0,2) circle(3pt);
[fill] (0,1.3) circle(2pt);
[fill] (0,1) circle(2pt);
[fill] (0,0.7) circle(2pt);
[fill] (0,0) circle(3pt);

[fill] (12,10) circle(3pt);
[fill] (12,9) circle(3pt);
[fill] (12,8.3) circle(2pt);
[fill] (12,8) circle(2pt);
[fill] (12,7.7) circle(2pt);
[fill] (12,7) circle(3pt);

[fill] (0,3) circle(3pt);
[fill] (1,2) circle(3pt);
[fill] (1.7,1.3) circle(2pt);
[fill] (2,1) circle(2pt);
[fill] (2.3,0.7) circle(2pt);
[fill] (3,0) circle(3pt);=

[fill] (9,10) circle(3pt);
[fill] (10,9) circle(3pt);
[fill] (10.7,8.3) circle(2pt);
[fill] (11,8) circle(2pt);
[fill] (11.3,7.7) circle(2pt);
[fill] (12,7) circle(3pt);

[red,thick] (0,3)– (1,3)–(1,5) – (2,5)–(2,7)–(6,7)–(6,10)–(12,10)  ;
[red,thick] (0,2)– (3,2) – (3,4)–(5,4)–(5,5)–(8,5)–(8,8)–(10,8)–(10,9)–(12,9)  ;
[red,thick] (0,0)– (6,0) – (6,2)–(10,2)–(10,6)–(11,6)–(11,7)–(12,7)  ;

Left: Lemma <ref> (i), the shaded hexagon region is $R_{\rm hex}$; Right: Lemma <ref> (ii)

(ii) Let $C\subseteq [1,a]_\mathbb{Z}\times[1,b]_\mathbb{Z}$.

If $u < a$, then “there exists a collection of $u$ nonintersecting paths connecting $\big((a-u+p,1)\big)_{p=1}^u$ and $\big((p,b)\big)_{p=1}^u$ whose union contains $C$” if and only if “ $u\le b$ and all diagonal chains of $C$ have sizes $\le u$”.

If $u=a$, then (regardless of $b$) there exists a unique collection of $u$ nonintersecting paths connecting $\big((a-u+p,1)\big)_{p=1}^u$ and $\big((p,b)\big)_{p=1}^u$ whose union contains $C$, where each path is straight horizontal.

(ii')  Let $C\subseteq \; [1,a]_\mathbb{Z}\times[1,b]_\mathbb{Z}$.

If $u<b$, then “there exists a collection of $u$ nonintersecting paths connecting $\big((1,b-u+q,1)\big)_{q=1}^u$ and $\big((a,q)\big)_{q=1}^u$ whose union contains $C$” if and only if “ $u\le a$ and all diagonal chains of $C$ have sizes $\le u$”.

If $u=b$, then (regardless of $a$) there exists a unique collection of $u$ nonintersecting paths connecting $\big((1,b-u+q)\big)_{q=1}^u$ and $\big((a,q)\big)_{q=1}^u$ whose union contains $C$, where each path is straight vertical.

(i) “$\Rightarrow$”: assume that there exits a collection of $u$ nonintersecting paths connecting $(X_p)_{p=1}^u$ and $(Y_p)_{p=1}^u$ whose union contains $C$.
For any diagonal chain $D\subseteq C$, each point in $D$ lies in such a path and different points lie in different paths, thus $|D|\le  u$.

“$\Leftarrow$”: assume $C\subseteq R_{\rm hex}$ such that all diagonal chains of $C$ have sizes $\le u$.

$$\textrm{ $r_{ij}=$ max size of diagonal chains in $C\cap \big([1,i-1]\times [1,j-1]\big)$ for $i,j\in\mathbb{Z}$.}$$

Observe that

1) $0\le r_{ij}\le u$;

2) $r_{i1}=0$, $r_{1j}=0$;

3) $r_{X_i}=r_{Y_i}=i-1$ for $1\le i\le u$;

4) $r_{ij}\le r_{i+1,j}\le r_{ij}+1$, $r_{ij}\le r_{i,j+1}\le r_{ij}+1$;

5) $r_{i+1,j+1}\le r_{ij}+1$. and the equality holds if $(i,j)\in C$.

Indeed, 1)–4) are obvious. To show 5): let $D\subseteq C\cap\big([1,i]\times [1,j]\big)$ be a diagonal chain of size $r_{i+1,j+1}$. Let $D'$ be obtained from $D$ by removing the SE-most point. Then $D'$ is a  diagonal chain in $C\cap \big([1,i-1]\times [1,j-1]\big)$ of length $r_{i+1,j+1}-1$, which implies $r_{i+1,j+1}\le r_{ij}+1$.
Moreover, if $(i,j)\in C$, then for a diagonal chain $D'\in C\cap\big( [1,i-1]\times[1,j-1]\big)$ of length $r_{ij}$ we can define a diagonal chain $D=D'\cup\{(i,j)\} \subseteq C\cap\big( [1,i]\times[1,j] \big)$ of length $r_{ij}+1$, thus $r_{i+1,j+1}\ge r_{ij}+1$ which implies the desired equality.

Now we can construct nonintersecting paths by the following

The SE-most construction.
For $p=1,\dots,u$, define the path $H_p$ to be the SE boundary of the set $\{(i,j)\in R_{\rm hex} : r_{ij}=p-1\}$, that is, a point $(i,j)\in R_{\rm hex}$ is in $H_p$ if and only if “$r_{ij}=p-1$ and $r_{i+1,j+1}=p$”.

It follows from 1)–5) that $(H_p)_{p=1}^u$ is a collection of $u$ nonintersecting paths connecting $(X_p)_{p=1}^u$ and $(Y_p)_{p=1}^u$ whose union contains $C$.

(ii) The case $u=a$ is trivial, so we assume $u<a$.

let $(H_p)_{p=1}^u$ be a collection of $u$ nonintersecting paths connecting $\big((a-u+p,1)\big)_{p=1}^u$ and $\big((p,b)\big)_{p=1}^u$ whose union contains $C$.
Then each $H_p$ is the join of three subpaths $(a-u+p,1)\rightsquigarrow X_p\rightsquigarrow Y_p\rightsquigarrow (p,b)$, where the first and third subpaths are straight horizontal (see Figure <ref> Right). In particular we have $u\le b$,  otherwise $Y_1$ will be on the left of $X_1$, making it impossible to connect $X_1$ and $Y_1$ by a SW-NE path.

Then the statement follows from (i) and the simple observation that any diagonal chain in $[1,a]_\mathbb{Z}\times[1,b]_\mathbb{Z}$ that is not completely inside $R_{\rm hex}$ must have length $<u$.

“$\Leftarrow$”: Use (i) to construct nonintersecting paths connecting $(X_p)_{p=1}^u$ and $(Y_p)_{i=1}^u$, then extend them to the paths $H_p: (a-u+p,1)\rightsquigarrow (p,b)$ as described in the above proof of “$\Rightarrow$”.

The proof (ii') is similar to (ii) so we skip.

(a) The SE-most construction can be equivalently described as follows:

First construct $H_1$: starting from $X_1$ and always walk east unless there is a point of $C$ in the north, in which case walk to that point; keep walking like this until it reaches $Y_1$;

Then construct $H_2$: starting from $X_2$ and always walk east unless there is a point of $C\setminus H_1$ in the north, in which case walk to that point; keep walking like this until it reaches $Y_2$;

Finally construct $H_u$: starting from $X_u$ and always walk east unless there is a point of $C\setminus (H_1\cup \cdots\cup H_{u-1})$ in the north, in which case walk to that point; keep walking like this until it reaches $Y_u$.

(b) Although we will only use the SE-most construction in the paper, there is also a NW-most construction described as follows.

The NW-most construction.
Let $s_{ij}=$ max size of diagonal chains in $C\cap [i+1,a] \times [j+1,b]$ for $i,j\in\mathbb{Z}$.
For $p=1,\dots,u$, define the path $H_p$ to the NW boundary of $\{(i,j)\in R_{\rm hex} : s_{ij}=p-1\}$, that is, a point $(i,j)\in R_{\rm hex} $ is in $H_p$ if and only if “$s_{ij}=p-1$ and $s_{i-1,j-1}=p$”.

For a subset $C \subseteq L$, the following are equivalent:

(i) $C$ is $\uu$-compatible;

(ii) there exists a (not necessarily straight) road map $(\{H^\alpha_{p}\}, \{V^\beta_{q}\})$ such that

\begin{equation}\label{eq:C in HV}
C|_k\subseteq\Big( \bigcup_{p=1}^{u_{\target(h_k)}} H^{\target(h_k)}_p|_k\Big)\
\bigcap\
\Big( \bigcup_{q=1}^{u_{\source(h_k)}} V^{\source(h_k)}_q|_k\Big), \quad \textrm{ for all } k.
\end{equation}

(ii)$\Rightarrow$(i): assume such a road map $(\{H^\alpha_{p}\}, \{V^\beta_{q}\})$ exists. Then for $\alpha\in {\rm V}_{\rm target}$, $C^\alpha$ is contained in a collection of nonintersecting paths $\{H^\alpha_p\}_{p=1}^{u_\alpha}$, so Lemma <ref> (ii) implies that $C^\alpha$ does not contain any diagonal chain of size $(u_\alpha+1)$; similarly,  for $\beta\in {\rm V}_{\rm source}$, Lemma <ref> (ii') implies that $C^\beta$ does not contain any diagonal chain of size $(u_\beta+1)$. Thus $C$ is ${\bf u}$-compatible.

assume $C$ is  ${\bf u}$-compatible.
By Lemma <ref>,
for $\alpha\in {\rm V}_{\rm target}$,  $C^\alpha$ is contained in a collection of nonintersecting paths $\{H^\alpha_p\}_{p=1}^{u_\alpha}$;
for $\beta\in {\rm V}_{\rm source}$,  $C^\beta$ is contained in a collection of nonintersecting paths $\{V^\beta_q\}_{q=1}^{u_\beta}$.
This gives a desired road map $(\{H^\alpha_{p}\}, \{V^\beta_{q}\})$.

Let $u,a,b$ be positive integers, $u\le \min(a-1,b)$. Assume  $c_{pq}, d_{pq}\in [1,a]_\mathbb{Z}$  (for $1\le p\le u$ and $1\le q\le b$) satisfy the following inequalities for all $p,q$ (whenever the inequalities make sense):

$$d_{pq}\ge c_{pq}, \quad c_{pq}\ge d_{p,q+1}, \quad c_{pq}>d_{p-1,q}.$$

Then there exist integers $c'_{pq}$, $d'_{pq}$  ($1\le p\le u$ and $1\le q\le b$) satisfying

(i) $d'_{pq}\ge c'_{pq}, \quad c'_{pq}>d'_{p-1,q}$ for all $p,q$ (whenever the inequalities make sense);

(ii) $c'_{pq}=d'_{p,q+1}$ for
$1\le p\le u$ and $1\le q\le b-1$;

(iii) $d'_{p1}=a-u+p$ and $c'_{pb}=p$ for $1\le p\le u$;

$\bigcup_p[c_{pq},d_{pq}]_\mathbb{Z} \subseteq \bigcup_p[c'_{pq},d'_{pq}]_\mathbb{Z}$
for $q=1,\dots,b$;
moreover, if the “ $\subseteq$” is actually “ $=$” for all $q$, then $c_{pq}=c'_{pq}$, $d_{pq}=d'_{pq}$ for all $p,q$.

$$C=\bigcup_{p=1}^a\bigcup_{q=1}^b  \{(i,q) : i\in [c_{pq},d_{pq}]_\mathbb{Z} \}\subseteq [1,a]_\mathbb{Z}\times[1,b]_\mathbb{Z}.$$

We claim that there exists a collection of $u$ nonintersecting paths $\{H_p\}_{p=1}^u$ connecting $\big((a-u+p,1)\big)_{p=1}^u$ and $\big((p,b)\big)_{p=1}^u$ whose union contains $C$.
Indeed,  Let $D$ be a diagonal chain of $C$. For every $p\in[1,u]$, let $L_p$ be the broken line connecting $(d_{p1},1)\to (c_{p1},1) \to
(d_{p2},2)\to (c_{p2},2)\to \cdots \to (d_{pb},b)\to (c_{pb},b)$.
(See Figure <ref> for an example with $u=2, b=3$.)

[gray] (0,0) grid (3,6);

[blue, very thick] (0,1)–(1,1)–(1,2)–(2,3)–(3,4)–(3,5);
[blue, very thick] (0,2)–(0,3)–(1,4)–(1,5)–(2,5)–(3,6);

(0,1) node [left] $c_{21}=d_{21}$; (0,1)[fill, gray] circle (.1);

(0,2) node [left] $d_{11}$;(0,2)[fill, gray]  circle (.1);
(0,3) node [left] $c_{11}$;(0,3)[fill, gray]  circle (.1);

(1,1) node [right] $d_{22}$;(1,1)[fill, gray] circle (.1);
(1,2) node [right] $c_{22}$;(1,2)[fill, gray] circle (.1);
(1,4) node [right] $d_{12}$;(1,4)[fill, gray]  circle (.1);
(1,5) node [left] $c_{12}$;(1,5)[fill, gray]  circle (.1);

(2,3) node [right] $c_{23}=d_{23}$;(2,3)[fill, gray]  circle (.1);
(2,5) node [above] $c_{13}=d_{13}$;(2,5)[fill, gray]  circle (.1);

(3,4) node [right] $d_{24}$;(3,4)[fill, gray]  circle (.1);
(3,5) node [right] $c_{24}$;(3,5)[fill, gray]  circle (.1);
(3,6) node [above] $c_{14}=d_{14}$;(3,6)[fill, gray]  circle (.1);

(.4,3.5) node [above] $L_1$;
(.4,1) node [above] $L_2$;

[gray] (0,0) grid (3,6);

[blue, very thick] (0,0)–(1,0)–(1,2)–(2,2)–(2,3)–(3,3)–(3,5);
[blue, very thick] (0,1)–(0,3)–(1,3)–(1,5)–(2,5)–(2,6)–(3,6);

(0,1) node [left] $d'_{21}$; (0,1)[fill, gray] circle (.1);
(0,0) node [left] $c'_{21}=d'_{21}$;(0,0) circle (.1);
(0,2)[fill, gray]  circle (.1);
(0,3) node [left] $c'_{11}$;(0,3)[fill, gray]  circle (.1);

(1,0) node [right] $d'_{22}$;(1,0) circle (.1);
(1,1) node [right] ;(1,1)[fill, gray] circle (.1);
(1,2) node [above right] $c'_{22}$;(1,2)[fill, gray] circle (.1);
(1,3) node [right] $d'_{12}$;(1,3)  circle (.1);
(1,4) node [right] ;(1,4)[fill, gray]  circle (.1);
(1,5) node [left] $c'_{12}$;(1,5)[fill, gray]  circle (.1);

(2,2) node [right] $d'_{23}$;(2,2)  circle (.1);
(2,3) node [above right] $c'_{23}$;(2,3)[fill, gray]  circle (.1);
(2,5) node [right] $d'_{13}$;(2,5)[fill, gray]  circle (.1);
(2,6) node [above] $c'_{13}$;(2,6)  circle (.1);

(3,3) node [right] $d'_{24}$;(3,3)  circle (.1);
(3,4) node [right] ;(3,4)[fill, gray]  circle (.1);
(3,5) node [right] $c'_{24}$;(3,5)[fill, gray]  circle (.1);
(3,6) node [above] $c'_{14}=d'_{14}$;(3,6)[fill, gray]  circle (.1);

Lemma <ref>, an example with $u=2,a=7,b=4$; Left: $L_1, L_2$ are the red broken lines;
etc.; Right:

Note that the line segment from $(c_{pq},q)$ to $(d_{p,q+1},q+1)$ has positive slope; so each $L_p$ contains at most one point in $D$. Therefore $D$ has at most $u$ points. Then the claim follows from Lemma <ref> (ii).

Now let $[c'_{pq},d'_{pq}]$ be the closed interval (possibly degenerated to a point) that is the intersection of $H_p$ and the vertical line $y=q$. Then obviously $c'_{pq},d'_{pq}$ satisfy (i)–(iv).

Next, we prove the “moreover” statement in (iv). Consider the sum:

\sum_{p,q}(d_{pq}-c_{pq})
\le\sum_p\Big(d_{p1}-c_{pb}\Big)\\
\le \Big((a-u+1)+\cdots+a\Big)-\Big(1+\cdots+u)\big)=(a-u)u,
\endaligned

where the two equalities hold if and only if $(\{c_{pq}\},\{d_{pq}\})$ satisfies conditions (ii) and (iii), that is, for all $p,q$ the following is true:

$$c_{pq}=d_{p,q+1}, \;  d_{p1}=a-u+p, \; c_{pb}=p. $$

As a consequence,

\sum_{p,q}(d'_{pq}-c'_{pq})

Suppose “ $\subseteq$” in (iv)  is actually “ $=$” for all $q$, that is,

\begin{equation}\label{eq:subset is equal}
S_q:= \bigcup_p[c_{pq},d_{pq}]_\mathbb{Z} = \bigcup_p[c'_{pq},d'_{pq}]_\mathbb{Z}.
\end{equation}

Compare the cardinality of the two sides of (<ref>), we have

$$\sum_{p=1}^u(d_{pq}-c_{pq}+1)=\sum_{p=1}^u(d'_{pq}-c'_{pq}+1), \text{ for every }q, $$

$$\sum_{p=1}^u(d_{pq}-c_{pq})=\sum_{p=1}^u(d'_{pq}-c'_{pq}),  \text{ for every }q.$$

By the previous paragraph, $(\{c_{pq}\},\{d_{pq}\})$ also satisfies (ii) and (iii).

We prove “$c_{pq}=c'_{pq}$ and $c_{pq}=d'_{pq}$” by induction on $q$:

For $q=1$, we have $d_{p1}=a-u+p=d'_{p1}$ for all $p$; $c_{p1}=c'_{p1}=a-u+p$ for $p>1$; Taking the minimum integer on the two sdies of (<ref>) for $q=1$ gives $c_{11}=c'_{11}$.

Next, for a given $q\ge2$, assume $c_{pq'}=c'_{pq'}$ and $d_{pq'}=d'_{pq'}$ for $q'< q$ and all $p$, we want to show that
$c_{pq}=c'_{pq}$ and $d_{pq}=d'_{pq}$ for all $p$. Indeed, $d_{pq}=c_{p,q-1}=c'_{p,q-1}=d'_{pq}$;
taking the minimum integer on the two sdies of (<ref>) gives $c_{1q}=c'_{1q}$; for $p>1$,
This completes the induction.

Now we are ready to prove the main proposition in this section.

We shall prove the statements in the following order: (i)$\Rightarrow$ (v) and “Moreover part",  (v) $\Rightarrow$ (iv) $\Rightarrow$ (ii) $\Rightarrow$(i)$\Rightarrow$(iii)$\Rightarrow$(ii).

(i)$\Rightarrow$(v) and “Moreover part":
let $C$ be a concurrent vertex map.
By definition, there exists a straight road map $(\{H^\alpha_{p}\}, \{V^\beta_{q}\})$ satisfying (<ref>).

Fix $\alpha\in {\rm V}_{\rm target}$. For convenience, denote

\begin{equation}\label{eq:convenient notation for H and V}
\begin{aligned}
&\textrm{$V^{\source(h_{r_1})}_1$, $V^{\source(h_{r_1})}_2$,$\dots$, $V^{\source(h_{r_1})}_{u_{\source(h_{r_i})}}$, $V^{\source(h_{r_2})}_1$, $V^{\source(h_{r_2})}_2$, $\dots$,$V^{\source(h_{r_2})}_{u_{\source(h_{r_2})}}$,
$V^{\source(h_{r_s})}_1$, $V^{\source(h_{r_s})}_2$, $\dots$,$V^{\source(h_{r_s})}_{u_{\source(h_{r_s})}}$}\\
$V^\alpha_1,V^\alpha_2,\dots,V^\alpha_{v_\alpha}$ \quad (where $v_\alpha=\sum_{i=1}^s u_{\source(h_{r_i})}$)}
\end{aligned}
\end{equation}

in that order, where  $r_1<\cdots<r_s$ are all indices such that $h_{r_1},\dots,h_{r_s}$ are all arrows with target $\alpha$.
We also denote $V^\alpha_q$ to be the vertical line $y=q$ for $q\le0$.

\begin{equation}\label{eq:P to Q}
\textrm{Denote $P_{pq}\rightsquigarrow Q_{pq}$ to be the subpath $H^\alpha_p\cap V^\alpha_q$.}
\end{equation}

(See Figure <ref> and compare the labeling therein with the original labeling in Figure <ref>.) Note that the region $[1,a_\alpha]_\mathbb{R}\times(-\infty,b_\alpha]_\mathbb{R}$ has been divided into regions $R_{pq}$ bouded by $H^\alpha_p$, $H^\alpha_{p+1}$, $V^\alpha_q$, $V^\alpha_{q+1}$ for $0\le p\le u_\alpha$ and $q\le v_\alpha$. So in general $R_{pq}$ has a “curly hexagon” shape with boundary $P_{pq}Q_{pq}P_{p,q+1}Q_{p+1,q+1}P_{p+1,q+1}Q_{p+1,q}$, and has degenerate shape in the obvious sense for $p=0$ or $p=u_\alpha$,  for $q\le 0$ or $q=v_\alpha$.

[gray] (0,0.5) rectangle (5.5,5.5);
[gray] (6,0.5) rectangle (11.5,5.5);
[gray] (12,0.5) rectangle (17.5,5.5);

[blue,densely dotted,thick](1.5,0.5) node[scale=.1] (v6)  – (-1.6,0.5);
[blue,densely dotted,thick](2,1) node[scale=.1]  (v4)  – (-1.6,1);
[blue,densely dotted,thick](3,1.5) node[scale=.1]  (v2)  – (-1.6,1.5);
[blue,densely dotted,thick](2,0.5) node[scale=.1]  (v5)  – (3.5,0.5) node[scale=.1]  (v12) ;
[blue,densely dotted,thick](3,1) node[scale=.1]  (v3)  – (4.5,1) node[scale=.1]  (v10) ;
[blue,densely dotted,thick](4,2.5) node[scale=.1]  (v1)  – (5,2.5) node[scale=.1]  (v8) ;
[blue,densely dotted,thick](5,2) node[scale=.1]  (v9)  – (7,2) node[scale=.1]  (v16) ;
[blue,densely dotted,thick](5.5,3.5) node[scale=.1]  (v7)  – (8,3.5) node[scale=.1]  (v14)   (4.5,0.5) node[scale=.1]  (v11)  – (6.5,0.5) node [scale=.1] (v18) ;
[blue,densely dotted,thick](7,1.5) node[scale=.1]  (v17)  – (8.5,1.5) node[scale=.1]  (v24) ;
[blue,densely dotted,thick](9,4.5) node[scale=.1]  (v13)  – (10.5,4.5) node [scale=.1] (v20) ;
[blue,densely dotted,thick](11,5.5) node[scale=.1]  (v19)  – (13.5,5.5) node[scale=.1]  (v26) ;
[blue,densely dotted,thick](14.5,5.5) node[scale=.1]  (v25)  – (15,5.5) node[scale=.1]  (v32) ;
[blue,densely dotted,thick](17,5.5) node[scale=.1]  (v31)  – (17.5,5.5);
[blue,densely dotted,thick](8,3) node [scale=.1] (v15)  – (9.5,3) node[scale=.1]  (v22)   (10.5,4) node[scale=.1]  (v21)  – (13,4) node[scale=.1]  (v28) ;
[blue,densely dotted,thick](13.5,5) node [scale=.1] (v27)  – (14.5,5) node [scale=.1] (v34) ;
[blue,densely dotted,thick](15,5) node[scale=.1]  (v33)  – (17.5,5);
[blue,densely dotted,thick](9.5,2) node[scale=.1]  (v23)  – (12.5,2) node [scale=.1] (v30)   (13,3) node[scale=.1]  (v29)  – (13.5,3) node[scale=.1]  (v36) ;
[blue,densely dotted,thick](14.5,4.5) node[scale=.1]  (v35)  – (17.5, 4.5);
[red,densely dotted,thick](4, 6) – (v1)  (v2) – (v3)  (v4) – (v5)  (v6) – (1.5,0);
[red,densely dotted,thick](5.5, 6) – (v7)  (v8) – (v9)  (v10) – (v11)  (v12) – (3.5,0);
[red,densely dotted,thick](9, 6) – (v13)  (v14) – (v15)  (v16) – (v17)  (v18) – (6.5,0);
[red,densely dotted,thick](11,6) – (v19)  (v20) – (v21)  (v22) – (v23)  (v24) – (8.5,0);
[red,densely dotted,thick](14.5, 6) – (v25)  (v26) – (v27)  (v28) – (v29)  (v30) – (12.5,0);
[red,densely dotted,thick](17, 6) – (v31)  (v32) – (v33)  (v34) – (v35)  (v36) – (13.5,0);
[thick] (v6) – (v5);
[thick] (v4) – (v3);
[thick] (v12) – (v11);

[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v2) – (v1);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v10) – (v9);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v8) – (v7);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v14) – (v13);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm](v20) – (v19);
[thick] (v26) – (14.5,5.5);
[thick] (v32) – (v31);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v16) – (v15);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v22) – (v21);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v28) – (v27);
[thick] (v34) – (v33);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v18) – (v17);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v24) – (v23);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v30) – (v29);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm]  (v36) – (v35);

(v2) node [above left] $P_{11}$;
(v1) node [above left] $Q_{11}$;

(v7) node [above left] $Q_{12}$;
(v8) node [above left] $P_{12}$;

(2,0.9) node [above] $P_{21}$;
(3,1.1) node [below] $Q_{21}$;

(1.5,.4) node [above] $P_{31}$;
(v5) node [below] $Q_{31}$;

(v9) node [left] $Q_{22}$;
(v10) node [above left] $P_{22}$;

(v11) node [below] $Q_{32}$;
(3.5,.6) node [below] $P_{32}$;

(v13) node [above left] $Q_{13}$;
(v14) node [above left] $P_{13}$;

(v15) node [left] $Q_{23}$;
(v16) node [above left] $P_{23}$;

(v17) node [left] $Q_{33}$;
(v18) node [right] $P_{33}$;

(v19) node [left] $Q_{14}$;
(v20) node [right] $P_{14}$;

(v21) node [left] $Q_{24}$;
(v22) node [right] $P_{24}$;

(v23) node [above left] $Q_{34}$;
(v24) node [above left] $P_{34}$;

(v25) node [above left] $Q_{15}$;
(v26) node [above left] $P_{15}$;

(v27) node [left] $Q_{25}$;
(v28) node [right] $P_{25}$;

(v29) node [left] $Q_{35}$;
(v30) node [right] $P_{35}$;

(v31) node [below] $Q_{16}$;
(v32) node [above ] $P_{16}$;

(v33) node [below] $Q_{26}$;
(v34) node [below left] $P_{26}$;

(v35) node [below right] $Q_{36}$;
(v36) node [right] $P_{36}$;

(-1.5,1.5) node [left] $H^\alpha_1$;
(-1.5,1) node [left] $H^\alpha_2$;
(-1.5,0.5) node [left] $H^\alpha_3$;

(4,6) node [above] $V^\alpha_1$;
(5.5,6) node [above] $V^\alpha_2$;

(9,6) node [above] $V^\alpha_3$;
(11,6) node [above] $V^\alpha_4$;

(14.5,6) node [above] $V^\alpha_5$;
(17,6) node [above] $V^\alpha_6$;

(.7,4.5) node [above] $R_{00}$;
(.7,1) node [above] $R_{10}$;
(.7,0.5) node [above] $R_{20}$;

(4.5,4.5) node [above] $R_{01}$;
(4,1.5) node [above] $R_{11}$;
(3.7,0.5) node [above] $R_{21}$;

(7,4.5) node [above] $R_{02}$;
(6.5,2.6) node [above] $R_{12}$;
(5.5,1) node [above] $R_{22}$;

(10,4.7) node [above] $R_{03}$;
(9.2,3.6) node [above] $R_{13}$;
(8.2,2) node [above] $R_{23}$;
(7.5,0.8) node [above] $R_{33}$;

(12,4.5) node [above] $R_{14}$;
(11,2.5) node [above] $R_{24}$;
(10,0.8) node [above] $R_{34}$;

(14,5) node [above] $R_{15}$;
(13.7,4) node [above] $R_{25}$;
(13,0.8) node [above] $R_{35}$;

(16,5) node [above] $R_{16}$;
(16,4.5) node [above] $R_{26}$;
(16,0.8) node [above] $R_{36}$;

[red,densely dotted,thick](-0.5,0)–(-0.5,6) (-1,0)–(-1,6) (-1.5,0)–(-1.5,6);
(-.3,6) node [above] $V^\alpha_0$;
(-1,6) node [above] $V^\alpha_{-1}$;
(-1.7,6) node [above] $V^\alpha_{-2}$;
(0.3,3) node [above right] $P_{10}(=Q_{10})$;[-stealth](0.3,3) – (-0.5,1.5);
(0.3,2.5) node [above right] $P_{20}(=Q_{20})$;[-stealth](0.3,2.5) – (-0.5,1);
(0.3,2) node [above right] $P_{30}(=Q_{30})$;[-stealth](0.3,2) – (-0.5,0.5);

(-.2,5.7) node [red, right] $R_{0,-1}$;[-stealth](-.15,5.7) – (-0.75,5.7);

An example of the notation in (<ref>).

Any point $(i,j')\in [1,a_\alpha]_\mathbb{Z}\times[1,b_\alpha]_\mathbb{Z}$ must fall into one of the following cases:

Case 1. $(i,j')$ lies strictly between $H^\alpha_p$ and $H^\alpha_{p+1}$ for some $p$. Assume it lies in the closed region $R_{pq}$ for some $q$. Recall the definition of $\bar{C}$ in Definition <ref>.
It is clear (see Figure <ref>) that $\bar{r}_{ij'}= p$ because we can find a diagonal chain in
$\bar{C}^\alpha \cap \big( (-\infty,i-1]_\mathbb{Z}\times(-\infty,j'-1]_\mathbb{Z}\big)$
of size $p$ (by choosing a suitable point from each $P_{p-t,q-t}\rightsquigarrow Q_{p-t,q-t}$ for $t=1,\dots,p$), and there does not exist longer diagonal chains in $\bar{C}$, because any such a chain contains at most one point in each of $H^\alpha_1,\dots,H^\alpha_p$. Similarly, $\bar{s}_{ij'}=u_\alpha-p$. Thus $\bar{r}_{ij'}+\bar{s}_{ij'}=u_\alpha$.

Case 2. If $(i,j')$ lies on $H^\alpha_p$ for some $p$. Similar as in Case 1, we get $\bar{r}_{ij'}= p-1$, $\bar{s}_{ij'}=u_\alpha-p$. Thus $\bar{r}_{ij'}+\bar{s}_{ij'}=u_\alpha-1$.

This proves $\bar{r}_{ijk}+\bar{s}_{ijk}=u_{\target(h_k)}-1$ or $u_{\target(h_k)}$, and the former equality holds if and only if $(i,j')$ (determined by $\phi_\alpha(i,j')=(i,j,k)$) is on a horizontal path, that is, $(i,j)$ is in $\bigcup_p H^{\target(h_k)}_p|_k$.

The condition for $V^{\source(h_k)}_q|_k$ can be proved similarly. Therefore (i) implies (v) and “Moreover part".

(v)$\Rightarrow$(iv): Assume (v) holds.

If $(i,j,k)\in C$, then
$r_{ijk}+s_{ijk}\le \bar{r}_{ijk}+\bar{s}_{ijk} =u_{\target(h_k)}-1<u_{\target(h_k)}$; similarly, $r'_{ijk}+s'_{ijk}<u_{\source(h_k)}$.

If $(i,j,k)\notin C$, we need to show that it is impossible to have both $r_{ijk}+s_{ijk}<u_{\target(h_k)}$ and $r'_{ijk}+s'_{ijk}<u_{\source(h_k)}$. Suppose both inequalities hold.
By (v), we can assume $\bar{r}_{ijk}+\bar{s}_{ijk}=u_\alpha$ (where $\alpha=\target(h_k)$) without loss of generality. Then either $r_{ijk}\neq \bar{r}_{ijk}$, or $s_{ijk}\neq \bar{s}_{ijk}$.

Case 1. If $r_{ijk}\neq \bar{r}_{ijk}$ and $s_{ijk}=\bar{s}_{ijk}$. Then
$\bar{r}_{ijk}=\min(i-1,u_{\alpha}-1-\min(a_\alpha-i,b_\alpha-j'))\le u_{\alpha}-1-\min(a_\alpha-i,b_\alpha-j')$. On the other hand, the distance from $(i,j')$ to the bottom (resp. right)  side of the rectangle $[1,a_\alpha]_\mathbb{Z}\times[1,b_\alpha]_\mathbb{Z}$ is $a_\alpha-i$ (resp. $b_\alpha-j'$), so $s_{ijk}\le\min(a_\alpha-i,b_\alpha-j')$. Then

$$\bar{r}_{ijk}+\bar{s}_{ijk}=\bar{r}_{ijk}+s_{ijk}\le u_{\alpha}-1$$

which contradicts our assumption.

Case 2. If $r_{ijk}=\bar{r}_{ijk}$ and $s_{ijk}\neq\bar{s}_{ijk}$. Similar to Case 1, so we skip.

Case 3. If $r_{ijk}\neq \bar{r}_{ijk}$ and $s_{ijk}\neq\bar{s}_{ijk}$. Then
$\bar{r}_{ijk}=\min(i-1,u_{\alpha}-1-\min(a_\alpha-i,b_\alpha-j'))$ and

\begin{equation}\label{eq:bar r+s}
\bar{r}_{ijk}+\bar{s}_{ijk}=\min(i-1,u_{\alpha}-1-\min(a_\alpha-i,b_\alpha-j'))+\min(a_\alpha-i,u_{\alpha}-\min(i,j'))
\end{equation}

We claim that (<ref>) is $\le u_\alpha-1$. This can be proved by consider three cases separately:

If $i\le j'$, then $\bar{r}_{ijk}+\bar{s}_{ijk}\le (i-1)+(u_{\alpha}-\min(i,j'))=(i-1)+(u_{\alpha}-i)=u_\alpha-1$;

If $a_\alpha-i\le b_\alpha-j'$, then $\bar{r}_{ijk}+\bar{s}_{ijk}\le (u_\alpha-1-(a_\alpha-i))+(a_\alpha-i)=u_\alpha-1$;

If $i>j'$ and $a_\alpha-i> b_\alpha-j'$, then
$\bar{r}_{ijk}+\bar{s}_{ijk}\le (u_\alpha-1-(b_\alpha-j'))+(u_\alpha-j')=2u_\alpha-1-b_\alpha=u_\alpha-1-(b_\alpha-u_\alpha)\le u_\alpha-1$, where the last inequality uses the assumption (<ref>).

This contradicts our assumption. So (v)$\Rightarrow$(iv).

(iv)$\Rightarrow$(ii): Assume (iv) holds.
Then $C$ is $\uu$-compatible. Indeed, assume for some $\gamma\in {\rm V}_\mathcal{Q}$ that $C^\gamma$ contains a diagonal chain $D$ of size $\ge u_\gamma+1$, let $(i',j')$ be the SE-most point in $D$ and denote $(i,j,k)=\phi_\gamma(i',j')$. Thus $(i,j,k)\in C$. On the other hand, $r_{ijk}+s_{ijk}\ge r_{ijk}\ge u_\gamma$, which implies $(i,j,k)\notin C$, a contradiction.

If $C$ is not maximal $\uu$-compatible, then there exists a $\uu$-compatible $C'$ satisfying $C\subsetneq C'\subseteq L$. Let $(i,j,k)\in C'\setminus C$. Note that $r_{ijk}$ (resp. $s_{ijk},r'_{ijk},s'_{ijk}$) are the same for $C$ and $C'$. But then $r_{ijk}+s_{ijk}<u_{\target(h_k)}$ and $r'_{ijk}+s'_{ijk}<u_{\source(h_k)}$, contradicting (iv).

(ii)$\Rightarrow$(i): Assume $C$ is maximal $\uu$-compatible. Then there exists a road map $(\{H^\alpha_{p}\}, \{V^\beta_{q}\})$ such that (<ref>) holds by Lemma <ref>. Furthermore we can assume that the road map is obtained by SE-most construction.
By the maximality of $C$, (<ref>) becomes an equality:

\begin{equation}\label{eq:C = HV}
C|_k = \Big( \bigcup_{p=1}^{u_{\target(h_k)}} H^{\target(h_k)}_p|_k\Big)\
\bigcap\
\Big( \bigcup_{q=1}^{u_{\source(h_k)}} V^{\source(h_k)}_q|_k\Big), \quad \textrm{ for all } k.
\end{equation}

It suffices to prove that $(\{H^\alpha_{p}\}, \{V^\beta_{q}\})$ is straight; or equivalently, to prove the conditions (a)–(c) in Lemma <ref>.

To prove condition (a): assume it does not hold. Similar to the proof of Lemma <ref> (a), assume $(p,q)$ is the minimal pair in the dictionary order such that $H^\alpha_{p}|_k \cap V^\beta_q|_k$ is not connected. Let $P\rightsquigarrow Q$ and $P'\rightsquigarrow Q'$ be the SW-most two connected subpaths of  $H^\alpha_{p}|_k \cap V^\beta_q|_k$. Without loss of generality we assume $P'\stackrel{V}{\rightsquigarrow} Q$ lies to the SE of $Q\stackrel{H}{\rightsquigarrow} P'$ (this is Case 1 in the Proof of Lemma <ref>).

First, observe that no interior lattice point of $Q\stackrel{H}{\rightsquigarrow} P'$ is in $C|_k$. The proof is similar to the one in Case 1 of the Proof of Lemma <ref>: assume the contrary that $R\in C|_k$ is an interior lattice point of  $Q\stackrel{H}{\rightsquigarrow} P'$. Then $R$ lies in some $V_{q'}$. Since $R$ is on the left side of $V_q$, we have $q'<q$.
Note that $(p,q')<(p,q)$ and the intersection $H^\alpha_p|_k\cap V^\beta_{q'}|_k$ is not connected; indeed,  the intersection contains $R$ as well as at least one point that is weakly SW of $P$. This contradicts the choice of $(p,q)$.

Now focus on $A_\alpha$. Let $Y$ be the highest NW corner (the one with smallest $x$-coordinate) of  $Q\stackrel{H}{\rightsquigarrow} P'$. In the previous paragraph we see that $Y\notin \phi_\alpha^{-1}(C)$. Since we create $H^\alpha_p$ by SE-most construction, we must have $Y=Y_p=(p,b_\alpha-u_\alpha+p)$, whose distance to the right side of $A_\alpha$ is $u_\alpha-p$. So there are at most $u_\alpha-p$ vertical paths on the right side of $Y$. On the other hand, the vertical paths
$V^\alpha_q,V^\alpha_{q+1},\dots,V^\alpha_{v_\alpha}$ are on the right side of $Y$. So

\begin{equation}\label{eq:sq1<=up}
v_\alpha-q+1\le u_\alpha-p
\end{equation}

If $q=1$, then (<ref>) implies $v_\alpha \le u_\alpha-p$, contradicting the assumption that $v_\alpha \ge u_\alpha$.

If $q>1$, then for each $1\le p'\le p$, let $Z_{p'}$ be the rightmost point in the intersection of the horizontal line $x=p'$ with $V^\alpha_{p'+q-p-1}$. (See Figure <ref>.) Observe that there exists $1\le p_0\le p$ such that $Z_{p_0}$ is not in $\phi_\alpha^{-1}(C)$, or equivalently, not in any of the $p-1$ horizontal paths $H^\alpha_1,\dots,H^\alpha_{p-1}$ (here we use the obvious fact that $H^\alpha_p, H^\alpha_{p+1},\dots$ are below those $Z_{p'}$'s). Ineed, this follows immediately from the fact that any horizontal path contains at most one of $Z_{p'}$'s, because any two $Z_{p'}$'s are in SE-NW position.

(3,2) node (v1)  – (2.5,2) – (2.5,1.5) – (1.5,1.5)  ;
(6.5,4) node (v2) ;
[red,dotted, thick] (v1) – (4.5,2) – (4.5,2.5) – (6,2.5) – (6,3.5) – (6.5,3.5) – (v2);
[blue, dotted, thick] (v1) – (3,3) – (4,3) – (4,3.5) – (5,3.5) – (5,4) – (v2);
(1.5,1.5) node [below] $P$;
(v1) node [below] $Q$;
(6.5,3.8) node [right] $P'$; [fill]  (v2) circle(2pt);
(7,5) node [above] $Y=(p,b_\alpha-u_\alpha+p)$; [fill]  (5,4) circle(2pt);[-stealth](6,5) – (5.2,4.2);

(6,2.5) node [red, below] $V^\alpha_q$;
(3.5,3) node [blue,above] $H^\alpha_p$;

(2.4,4) node [right] $Z_p$; [fill]  (2.5,4) circle(2pt);
[red, dotted, thick] (2.5,5.5) – (2.5,4) – (2,4) – (2,3) – (1,3) – (1,2.5) – (0.5,2.5)  ;
(3.5,5.8) node [red,left] $V^\alpha_{q-1}$;

(0.4,4.5) node [right] $Z_{p-1}$; [fill]  (0.5,4.5) circle(2pt);
[red, dotted, thick] (0.5,5.5) – (0.5,4.5) – (0,4.5) – (0,3.5) – (-1,3.5) – (-1,3)  ;
(1.5,5.8) node [red,left] $V^\alpha_{q-2}$;

(-0.6,5) node [right] $Z_{p-2}$; [fill]  (-0.5,5) circle(2pt);
[red, dotted, thick] (-.5,5.5) – (-.5,5) – (-1,5) – (-1,4) – (-2,4) – (-2,3)  ;
(0,5.8) node [red,left] $V^\alpha_{q-3}$;

Proof of (ii)$\Rightarrow$(i), condition (a)

The above observation implies $\phi_\alpha(Z_{p_0})\notin C$.
We claim that $C':=C\cup\{\phi_\alpha(Z_{p_0})\}$ is ${\bf u}$-compatible thus contradicting the maximality of $C$. Indeed:

for $\beta\in {\rm V}_{\rm source}$: because ${C'}^\beta$ is contained in $\bigcup_{q=1}^{u_\beta} V^\beta_q$, it does not contain any diagonal chain of size $(u_\beta+1)$;

for $\alpha\in {\rm V}_{\rm target}$: it suffices to show that if $D$ is a diagonal chain in ${C'}^{\alpha}$ containing
$\phi_\alpha(Z_{p_0})$, then the size of $D$ is $\le u_\alpha$.
Since $\phi_\alpha(Z_{p_0})$ has $x$-coordinate $p_0$, there are at most $p_0-1$ points of $D$ that are NW of $\phi_\alpha(Z_{p_0})$.
Meanwhile, since  $\phi_\alpha(Z_{p_0})$ is on $V^\alpha_{p_0+q-p-1	}$,  any point of $D$ that is weakly SE of $\phi_\alpha(Z_{p_0})$ must be in $\bigcup_{q'=p_0+q-p-1}^{v_\alpha} V^\alpha_{q'}$, and no two points of $D$ lie in the same $V^\alpha_{q'}$, so there are at most $v_\alpha-p_0-q+p+2$ points of $D$ that are weakly SE of $\phi_\alpha(Z_{p_0})$. Thus the size of $D$ is $\le (p_0-1)+(v_\alpha-p_0-q+p+2)=v_\alpha-q+p+1\le u_\alpha$, where the last inequality uses (<ref>).

This proves (a).

To prove condition (b): we apply the straightening process to be described as follows. Denote the $x$-coordinate of $P_{pq}$ by $d_{pq}$, the $x$-coordinate of $Q_{pq}$ by $c_{pq}$.
Let $c'_{pq}, d'_{pq}$ be obtained from the Straightening Lemma <ref>. Let $P'_{pq}$ be the leftmost point on $V^\alpha_q$ whose $x$-coordinate is $d'_{pq}$, let $Q'_{pq}$ be the rightmost point on $V^\alpha_q$ whose $x$-coordinate is $c'_{pq}$. Construct ${H'_p}^\alpha$ to be the path

$$(a_\alpha-u_\alpha+p,1)\to P'_{p1}\stackrel{V}{\rightsquigarrow} Q'_{p1}\to P'_{p2}\stackrel{V}{\rightsquigarrow} Q'_{p2}\to\cdots\to P'_{p,v_\alpha}\stackrel{V}{\rightsquigarrow} Q'_{p,v_\alpha}\to (p,b)$$

where “$\to$” denote straight horizontal paths. Define $C'$ to be the right side of (<ref>) with $H^\alpha_p$ replaced by ${H'_p}^\alpha$ for each $\alpha$. Then $C'$ is also ${\bf u}$-compatible and $C\subseteq C'$; moreover, if $C=C'$, then Lemma <ref> implies  $c_{pq}=c'_{pq}, d_{pq}=d'_{pq}$ for all $p,q$. In particular, $c_{pq}=d_{p,q+1}$ for all $p,q$ whenever the equality makes sense. Then $Q_{pq}$ and $P_{p,q+1}$ have the same $x$-coordinate.

This proves (b). (See Figure <ref> for an example.)

[gray!20] (0,0) grid (13,6);
[red,  thick] (2,0)–(2,2)–(3,2)–(3,5)–(4,5)–(4,6);
[red,  thick] (4,0)–(4,1)–(5,1)–(5,3)–(6,3)–(6,5)–(7,5)–(7,6);
[red,  thick] (6,0)–(6,1)–(8,1)–(8,4)–(9,4)–(9,5)–(10,5)–(10,6);
[red,  thick] (9,0)–(9,2)–(11,2)–(11,4)–(12,4)–(12,6);
[blue, densely dotted, very thick] (0,0)–(1,0)–(1,1)–(5,1)–(5,2)–(7,2)–(7,3)–(10,3)–(10,4)–(12,4)–(12,5)–(13,5);
[blue, densely dotted, very thick] (0,1)–(0,2)–(3,2)–(3,3)–(4,3)–(4,4)–(6,4)–(6,5)–(11,5)–(11,6)–(13,6);

in (2,1),(4,1),(5,1),(2,2),(3,2),(5,2),(3,3),(8,3),(6,4),(11,4),(12,4),(6,5),(7,5),(9,5),(10,5),(12,5),(12,6)
[gray, fill] circle (4pt);

[gray!20] (0,0) grid (13,6);
[red,  thick] (2,0)–(2,2)–(3,2)–(3,5)–(4,5)–(4,6);
[red,  thick] (4,0)–(4,1)–(5,1)–(5,3)–(6,3)–(6,5)–(7,5)–(7,6);
[red,  thick] (6,0)–(6,1)–(8,1)–(8,4)–(9,4)–(9,5)–(10,5)–(10,6);
[red,  thick] (9,0)–(9,2)–(11,2)–(11,4)–(12,4)–(12,6);
[blue, densely dotted, very thick] (0,0)–(4,0)–(4,1)–(5,1)–(5,2)–(8,2)–(8,3)–(11,3)–(11,4)–(12,4)–(12,5)–(13,5);
[blue, densely dotted, very thick] (0,1)–(2,1)–(2,2)–(3,2)–(3,3)–(6,3)–(6,5)–(10,5)–(10,6)–(13,6);

in (2,1),(4,1),(5,1),(2,2),(3,2),(5,2),(3,3),(8,3),(6,4),(11,4),(12,4),(6,5),(7,5),(9,5),(10,5),(12,5),(12,6)
[gray, fill] circle (4pt);
in (2,0),(4,0),(8,2),(5,3),(6,3),(11,3),(10,6)
circle (5pt);

Proof of (ii)$\Rightarrow$(i), condition (b). Here is an example of the straightening process where the constants $c_{pq}, d_{pq}, c'_{pq},d'_{pq}$ are equal to those in Figure <ref>. Left: $C$ is the set of full circles; Right: $C'\setminus C$ is the set of empty circles, $C'$ is the set of full and empty circles.

The proof of condition (c) is similar, so we skip.
(i)$\Rightarrow$(iii). Given a concurrent vertex map $C$ induced from a straight road map $(\{H^\alpha_p\},\{V^\beta_q\})$, the number of lattice points in $P^k_{pq}\rightsquigarrow Q^k_{pq}$ is equal to 1 plus the number of edges therein:

\begin{equation}\label{eq:1+diff+diff}
1+\big| (P^k_{pq})_x - (Q^k_{pq})_x \big|
+\big| (P^k_{pq})_y - (Q^k_{pq})_y \big|
\end{equation}

To compute $|C|$, we compute the sum of each of the above three terms for all $(p,q)$.

The sum of first terms (which are $1$s) in (<ref>) for all $(p,q)$ is equal to the number of $(p,q)$'s. On ${\rm Page}_k$, there are $u_{\target(h_k)}$ horizontal paths and $u_{\source(h_k)}$ horizontal paths, so the number of subpaths $P^k_{pq}\rightsquigarrow Q^k_{pq}$ on${\rm Page}_k$ is $u_{\source(h_k)}u_{\target(h_k)}$.
The the total sum is
$\sum_k u_{\source(h_k)}u_{\target(h_k)}$.

The sum of the second terms in (<ref>) is:

&\sum_{p,q}| (P^k_{pq})_x - (Q^k_{pq})_x | \quad \textrm{ ( note that $k$ is determined by $p,q$ )}\\
&=\sum_{\alpha\in {\rm V}_{\rm target}}\sum_{p=1}^{u_\alpha}|\text{difference of $x$-coordinates of the two endpoints of $H^\alpha_p$}|\\
&=\sum_{\alpha\in {\rm V}_{\rm target}}\sum_{p=1}^{u_\alpha}(a_\alpha-u_\alpha+p-p)\\
&=\sum_{\alpha\in {\rm V}_{\rm target}} u_\alpha(a_\alpha-u_\alpha)\\
\endaligned

Similarly, the sum of the third terms in (<ref>) is $\sum_{\beta\in {\rm V}_{\rm source}} u_\beta(b_\beta-u_\beta).$

Add the above three sums, we get the expected formula (<ref>). The fact that $C$ is $\uu$-compatible follows from Lemma <ref>.

(iii)$\Rightarrow$(ii).  Assume $C$ is ${\bf u}$-compatible and $|C|=N_{\mathcal{Q},\mm,\uu}$. Let $C'$ be maximal ${\bf u}$-compatible set that contains $C$. Since it is already proved that (ii)$\Rightarrow$(i)$\Rightarrow$(iii),  we must have $|C'|=N_{\mathcal{Q},\mm,\uu}=|C|$, which implies $C'=C$ and thus $C$ is maximal.

The natural generators of ${\rm init }(I_{\mathcal{Q},\mm,\uu})$ are $(u_\gamma+1)$-diagonal chains in $A_\gamma$ for all $\gamma$. So $C\subseteq L$ is in $\Delta_{\mathcal{Q},\mm,\uu}$ exactly when $C$ does not contain any
$(u_\gamma+1)$-diagonal chain in $A_\gamma$ for any $\gamma$, or in other words, when $C$ is ${\bf u}$-compatible. Then $C$ is a facet of  $\Delta_{\mathcal{Q},\mm,\uu}$ if and only if $C$ is maximal ${\bf u}$-compatible. So the theorem follows from the statement (i)$\Leftrightarrow$(ii) of Proposition <ref>.

§ PROPERTIES OF THE SIMPLICIAL COMPLEX $\DELTA_{\MATHCAL{Q},\MM,\UU}$

§.§ Shellability

In this subsection we will show that $\Delta_{\mathcal{Q},\mm,\uu}$ is shellable.
In (a) of the definition below, we use notation $H^\alpha_p, V^\alpha_q, P_{pq},Q_{pq}$ introduced in (<ref>) and (<ref>).
In (b), we use the mirrored version of  (<ref>) and (<ref>), in particular, for $\beta\in {\rm V}_{\rm source}$ we define

$$v_\beta=\sum_{i=1}^{t} u_{\target(h_{r'_i})}$$

where $r'_1<\cdots<r'_t$ are all the indices such that $h_{r'_1},\dots,h_{r'_t}$ are all the arrows with source $\beta$.

Let $C$ be a concurrent vertex map.

(a) A point $(i,j,k)\in C$ is called a horizontal NW corner if $(i,j,k)=\phi_\alpha(P)$ where $P$ is a NW corner of a path $H^\alpha_p$ for some $\alpha\in {\rm V}_{\rm target}$ and $1\le p\le u_\alpha$.

Such a corner is said to be non-essential  if  the corresponding $P$ satisfies $P=Q_{p,p+v_\alpha-u_\alpha}$ for some $1\le p\le u_\alpha$; otherwise the corner is said to be essential.

(b) A point $(i,j,k)\in C$ is called a vertical NW corner if
$(i,j,k)=\phi_\beta(P)$ where $P$ is a NW corner of a path $V^\beta_q$ for some $\beta\in {\rm V}_{\rm source}$ and $1\le q\le u_\beta$.

Such a corner is said to be non-essential  if  the corresponding $P$ satisfies $P=P_{q+v_\beta-u_\beta,q}$ for some $1\le q\le u_\beta$; otherwise the corner is said to be essential.

Note that if $(i,j,k)$ is both a horizontal and a vertical NW corner, then it is essential both as a horizontal and as a vertical NW corner. Indeed, assume the statement is false, then without loss of generality we assume it is a non-essential horizontal NW corner, and denote
$(i,j,k)=\phi_\alpha(P)=\phi_\beta(P')$ where $\alpha,\beta$ are the target and source of $h_k$, respectively.
Then $P=Q_{p,p+v_\alpha-u_\alpha}$ which is on the vertical path $V^\alpha_{p+v_\alpha-u_\alpha}$ but is not a NW corner of that path. This contradicts our assumption.

For convenience, given a matrix $A$ and a point $P=(i,j)$ in the lattice of integer points corresponding to $A$, we denote the $x$ and $y$ coordinates of $P$ as $(P)^A_x=i$, $(P)^A_y=j$.

(a) Assume $\alpha \in{\rm V}_{\rm target}$, $1\le p\le u_\alpha$. Then $(P_{pq'})^{A_\alpha}_x=p$ for $q'\ge p+1+v_\alpha-u_\alpha$,
$(Q_{pq'})^{A_\alpha}_x=p$ for $q'\ge p+v_\alpha-u_\alpha$.

– the subpath $P_{pq'}{\rightsquigarrow}Q_{pq'}$ (for $q'\ge p+1+v_\alpha-u_\alpha$) contains no horizontal NW corner;

– the straight vertical subpath $P_{pq'}\to Q_{p+1,q'}$ has length 1 if $q'\ge p+1+v_\alpha-u_\alpha$.

(b)  Assume $\beta \in{\rm V}_{\rm source}$, $1\le q\le u_\beta$. Then
$(Q_{p'q})^{A_\beta}_y=q$ for $p'\ge q+1+v_\beta-u_\beta$,
$(P_{p'q})^{A_\beta}_y=q$ for $p'\ge q+v_\beta-u_\beta$.

– the subpath $Q_{p'q}{\rightsquigarrow}P_{p'q}$ (for $p'\ge q+1+v_\beta-u_\beta$) contains no vertical NW corner;

– the straight horizontal subpath $Q_{p'q}\to P_{p',q+1}$ has length 1 if $p'\ge q+1+v_\beta-u_\beta$.

(a) We prove the first statement by backward induction on $p$. For the base case $p=u_\alpha$, the assertion
$(Q_{u_\alpha,v_\alpha})^{A_\alpha}_x= u_\alpha$ follows from Lemma <ref> (b).

Now assume the statement is true for $p+1$. Then for $q'\ge p+1+v_\alpha-u_\alpha$,  $(Q_{p+1,q'})^{A_\alpha}_x=p+1$, thus $(P_{pq'})^{A_\alpha}_x\le (Q_{p+1,q'})^{A_\alpha}_x-1= p$. On the other hand, $(P_{pq'})^{A_\alpha}_x\ge p$ because it is on the path $H^\alpha_p$. So $(P_{pq'})^{A_\alpha}_x=p$ for $q'\ge p+1+v_\alpha-u_\alpha$.

Next, $(Q_{pq'})^{A_\alpha}_x = (P_{p,q'+1})^{A_\alpha}_x=p$ for $q'+1\ge p+1+v_\alpha-u_\alpha$, that is, for $q'\ge p+v_\alpha-u_\alpha$.

Consequently for $q'\ge p+1+v_\alpha-u_\alpha$, $(P_{pq'})^{A_\alpha}_x = (Q_{p,q'-1})^{A_\alpha}_x=p$, thus the subpath of $H^\alpha_p$ from $Q_{p,q'-1}$ to the right endpoint $(p,v_\alpha)$ must be contained in the horizontal line $x=p$, therefore the subpath $P_{pq'}{\rightsquigarrow}Q_{pq'}$ contains no horizontal NW corner; meanwhile, since $(P_{pq'})^{A_\alpha}_x=p$ and $(Q_{p+1,q'})^{A_\alpha}_x=p+1$,  the straight vertical subpath $P_{pq'}\to Q_{p+1,q'}$ has length 1.

(b) is just the transpose of (a) thus can be proved similarly.

Define a total ordering $<_T$ on $L$ as follows: $(i,j,k)<_T (i',j',k')$ if and only if

$$\textrm{($k<k'$), or  ($k=k'$ and $i<i'$), or ($k=k'$ and $i=i'$ and $j<j'$).}$$

Given two concurrent vertex maps $C=(P_1,\dots,P_N)$ and $C'=(P'_1,\dots,P'_N)$, where $P_1<_T P_2<_T\cdots<_T P_N$ and  $P'_1<_T P'_2<_T\cdots<_T P'_N$, define $C<_TC'$ if there is an integer $1\le t\le N$ such that $P_t<_T P'_t$ and $P_s=P'_s$ for all $s>t$.

For any $\uu$-compatible subset $S\subseteq L$, define $C_{\max}(S)$, the concurrent vertex map induced from $S$, as follows:
first initialize $S'=S$,
then for $P$ running from the largest vertex in $L$ to the smallest, redefine $S'=S'\cup\{P\}$ if $S'\cup \{P\}$ is $\uu$-compatible.
The end result $S'$ is $C_{\max}(S)$.

We define $C_{\min}(S)$ similarly: first initialize $S'=S$,
then for $P$ running from the smallest vertex in $L$ to the largest, redefine $S'=S'\cup\{P\}$ if $S'\cup \{P\}$ is $\uu$-compatible.
The end result $S'$ is $C_{\min}(S)$.

Note that the order $<_T$ is related to the order defined in (<ref>) as follows:

$$\textrm{$x^{(k)}_{ij}>x^{(k')}_{i'j'}$ if and only if $(i,j,k)<_T (i',j',k')$.}$$

Also note that $C_{\max}(S)$ is maximal $\uu$-compatible, therefore a concurrent vertex map. Indeed, if $C_{\max}(S)\cup\{P\}$ is $\uu$-compatible, then $P$ should be added to $S'$ in the construction of $C_{\max}(S)$.

In most part of the paper we only discuss properties of $C_{\max}(S)$. The properties of $C_{\min}(S)$ are similar so we omit.

Let $(i,j,k)\in C$ be an essential horizontal or vertical NW corner.
Then there is a unique triple $(i',j',k')\notin C$, such that $(i,j,k)<_T (i',j',k')$, and $C'=(C\setminus\{(i,j,k)\})\cup\{(i',j',k')\}$ is also a concurrent vertex map satisfying $C <_T C'$.

As a consequence, for a $\uu$-compatible subset $S\subseteq L$,  all essential horizontal or vertical NW corners of $C_{\max}(S)$ are contained in $S$.

Without loss of generality, assume $(i,j,k)$ is an essential horizontal NW corner. Let $\alpha=\target(h_k)$. We consider two cases.

Case 1: if $(i,j,k)$ is also a vertical NW corner. Let $t$ be the smallest nonnegative integer such that $(i+t+1,j+t+1,k)$ is either not a horizontal NW corner or not a vertical NW corner. Here we used the fact that $(i+t+1,j+t+1)$ is a valid point in ${\rm Page}_k$ (that is, $i+t+1\le m_{\target(h_k)}$ and  $j+t+1\le m_{\source(h_k)}$) because a point in the bottom row of ${\rm Page}_k$ cannot be a horizontal NW corner, and a point in the rightmost column of  ${\rm Page}_k$ cannot be a vertical NW corner.

Define $(i',j',k')=(i+t+1,j+t+1,k)$, (see Fig <ref> left). We claim that $(i',j',k')\notin C$. Indeed, let $p,q$ be the integers determined by the condition that $\phi_\alpha^{-1}(i,j,k) \in H^\alpha_p\cap V^\alpha_q$. Note note that for each $0\le t'\le t$, $(i+t',j+t',k)$ is both a horizontal and a vertical NW corner; thus the three points $\phi_\alpha^{-1}(i+t'+1,j+t',k)$, $\phi_\alpha^{-1}(i+t',j+t',k)$, $\phi_\alpha^{-1}(i+t',j+t'+1,k)$ must lie in the same horizontal path $H^\alpha_{p+t'}$ and the same vertical path $V^\alpha_{q+t'}$. If $(i',j',k')\in C$, then $\phi_\alpha^{-1}(i',j',k')$ must lie in both $H^\alpha_{p+t'+1}$ and $V^\alpha_{q+t'+1}$, but then it must be a NW corner of both, contradicting the choice of $t$.

Now, define $C'=(C\setminus\{(i,j,k)\})\cup\{(i',j',k')\}$, and modify each $H^\alpha_{p+t'+1}$ into $H'_{p+t'+1}$ (resp., modify each $V^\alpha_{q+t'+1}$ into $V'_{q+t'+1}$) by replacing its NW corner $\phi_\alpha^{-1}(i+t',j+t',k)$  by a SE corner $\phi_\alpha^{-1}(i+t'+1,j+t'+1,k)$, as indicated in Figure <ref> right.  Since $C'$ is contained in the road map obtained from the above modification,  $C'$ must be $\uu$-compatible. Furthermore $C'$ is maximal $\uu$-compatible since $|C'|=|C|$. So $C'$ is a concurrent vertex map. It is obvious that  $(i,j,k)<_T (i',j',k')$ and $C<_T C'$.

at (0,0)$\bullet$;
at (1,0) $\bullet$;
at (0,1) $\bullet$; at (-.1,1.5)[anchor=east]$\phi_\alpha^{-1}(i,j,k)$;
at (1,1) $\bullet$;
(0, 0) – (0,1) (0,1)–(1,1);
[decorate, decoration=  zigzag]  (0,0) – (-2,-2);
[decorate, decoration=  zigzag]  (3,3) – (1,1);
at (-2,-2)[anchor=east]$H^\alpha_p\cap V^\alpha_q$;
at (0,0)$\bullet$;
at (1,0) $\ddots$;
at (1,1) $\bullet$;
(0, 0) – (0,1) (0,1)–(1,1);
[decorate, decoration=  zigzag]  (0,0) – (-2,-2);
[decorate, decoration=  zigzag]  (3,3) – (1,1);
at (-2,-2)[anchor=east]$H^\alpha_{p+1}\cap V^\alpha_{q+1}$;

at (0,0)$\bullet$;
at (1,0) +; at (1,0)[anchor=north west]$\phi_\alpha^{-1}(i',j',k')$;
at (0,1) $\bullet$;
at (1,1) $\bullet$;
(0, 0) – (0,1) (0,1)–(1,1);
[decorate, decoration=  zigzag]  (0,0) – (-2,-2);
[decorate, decoration=  zigzag]  (3,3) – (1,1);
at (-2,-2)[anchor=east]$H^\alpha_{p+t}\cap V^\alpha_{q+t}$;

at (8, -1) $\Longrightarrow$;
at (0,0)$\bullet$;
at (1,0) $\bullet$; at (-.1,1.5)[anchor=east]$\phi_\alpha^{-1}(i,j,k)$;
at (0,1) +;
at (1,1) $\bullet$;
(0,0) – (1,0) (1,0)–(1,1);
[decorate, decoration=  zigzag]  (0,0) – (-2,-2);
[decorate, decoration=  zigzag]  (3,3) – (1,1);
at (-2,-2)[anchor=east]$H'_{p}\cap V'_{q}$;
at (0,0)$\bullet$;
at (1,0) $\bullet$;
at (1,1) $\bullet$;
(0,0) – (1,0) (1,0)–(1,1);
[decorate, decoration=  zigzag]  (0,0) – (-2,-2);
[decorate, decoration=  zigzag]  (3,3) – (1,1);
at (-2,-2)[anchor=east]$H'_{p+1}\cap V'_{q+1}$;

at (0,0)$\bullet$;
at (1,0) $\bullet$;
at (0,1) $\ddots$; at (1,0)[anchor=north west]$\phi_\alpha^{-1}(i',j',k')$;
at (1,1) $\bullet$;
(0,0) – (1,0) (1,0)–(1,1);
[decorate, decoration=  zigzag]  (0,0) – (-2,-2);
[decorate, decoration=  zigzag]  (3,3) – (1,1);
at (-2,-2)[anchor=east]$H'_{p+t}\cap V'_{q+t}$;

Lemma <ref> Case 1. Left: before modification; Right: after modification

Next, we show the uniqueness of $(i',j',k')$. Assume $(i'',j'',k'')$ is a point in $C''$
satisfying the conditions that  $(i,j,k)<_T (i'',j'',k'')$ and $C''=(C\setminus\{(i,j,k)\})\cup\{(i'',j'',k'')\}$ is a concurrent vertex map.
The first condition implies that $\phi_\alpha^{-1}(i'',j'',k'')$ does not lie weakly NW of $\phi_\alpha^{-1}(i,j,k)$.
Let $\{H''_p\}_{p=1}^{u_\alpha}$ and $\{V''_q\}_{q=1}^{v_\alpha}$ be the horizontal and vertical paths in $A_\alpha$ corresponding to $C''$.
By the “Moreover” part of Proposition <ref>, since  $\phi_\alpha^{-1}(i+1,j,k)$ is on $H^\alpha_p$, we have $\bar{r}_{i+1,j,k}=p-1$; since $\phi_\alpha^{-1}(i'',j'',k'')$ does not lie weakly NW of $\phi_\alpha^{-1}(i,j,k)$, $C$ and $C''$ agree at every point weakly NW of $\phi_\alpha^{-1}(i,j,k)$ except the point $\phi_\alpha^{-1}(i,j,k)$ itself. So
$\bar{r}''_{i+1,j,k}=\bar{r}_{i+1,j,k}=p-1$ (where $\bar{r}''_{i+1,j,k}$ is just $\bar{r}_{i+1,j,k}$ for $C''$). Again by the “Moreover” part of Proposition <ref>, $\phi_\alpha^{-1}(i+1,j,k)$ is on $H''_p$. Similarly, $\phi_\alpha^{-1}(i,j+1,k)$ is on $H''_p$. If $\phi_\alpha^{-1}(i,j,k)$ is also on $H''_p$, then $(i,j,k)$ must be a horizontal NW corner, and therefore must be in $C''$, a contradiction.
So $\phi_\alpha^{-1}(i,j,k)$ is not on $H''_p$.
This implies $\phi_\alpha^{-1}(i+1,j+1,k)$ is on $H''_p$.

Then by induction on $t'$, we see that $\phi_\alpha^{-1}(i+t'+1,j+t',k)$, $\phi_\alpha^{-1}(i+t'+1,j+t'+1,k)$, $\phi_\alpha^{-1}(i+t',j+t'+1,k)$ are on the same horizontal path $H''_{p+t'}$ for every $0\le t'\le t$. In particular, $\phi_\alpha^{-1}(i',j',k')$ on $H''_{p+t}$. Similarly, $\phi_\alpha^{-1}(i',j',k')$ is on $V''_{q+t}$. Thus $(i',j',k')$ is in $C''$, which implies $(i'',j'',k'')=(i',j',k')$.

Case 2: if $(i,j,k)$ is not a vertical NW corner.
This is possible only when $\phi_\alpha^{-1}(i,j,k)=Q_{pq}$ for some $p,q$ and the vertical edge connecting the vertices $\phi_\alpha^{-1}(i,j,k)$ and $\phi_\alpha^{-1}(i+1,j,k)$ is in $H^\alpha_p$.
By Lemma <ref>, $q\le p+v_\alpha-u_\alpha$. If the equality holds, then $(i,j,k)$ is a non-essential horizontal NW corner, contradicting our assumption. So we have the strict inequality $q<p+v_\alpha-u_\alpha$. So for all $t\le u_\alpha-p$,  $q+t+1\le (p+v_\alpha-u_\alpha-1)+t+1\le v_\alpha$.
Let $t\le u_\alpha-p$ be the smallest nonnegative integer such that $P_{p+t,q+t+1}+(1,0)\notin \phi_\alpha^{-1}(C)$.
Then for $0\le t'<t$, we must have $P_{p+t',q+t'+1}+(1,0)=Q_{p+t'+1,q+t'+1}$.

For $0\le t'\le t$,
denote $R_{p+t',q+t'}$ to be the leftmost vertex of those on $P_{p+t'}\rightsquigarrow Q_{p+t'}$ with $x$-coordinate $p+t'$ (that is, of the same height as $Q_{p+t'}$).
The fact that $Q_{pq}$ is a horizontal NW corner forces $R_{p+t',q+t'}$ to also be a horizontal NW corner for each $0\le t'\le t$.
In particular, $R_{p+t,q+t}$ is a horizontal NW corner.
So the $x$-coordinate of $R_{p+t,q+t}$ is $<a_\alpha$.

at (0,0)$\bullet$;
at (0,1) $\bullet$;      at (0,1)[anchor=south west]$Q_{pq}=R_{pq}$;
at (4,1) $\bullet$;  at (4.2,1)[anchor=south]$P_{p,q+1}$;
(0, 0) – (0,1);
[blue, thick, dotted](0,1)–(4,1);
[red, thick, dotted](0,1)–(0,2.5);
[decorate, decoration=  zigzag]  (0,0) – (-1,-1);
at (-.5,-.7)[anchor=north]$H^\alpha_p$;
at (0,0)$\bullet$;
at (0,1)$\bullet$; at (0.4,1)[anchor=north west]$R_{p+1,q+1}$;[-stealth](0.5,0.5) – (0.2,0.8);
at (1,1)$\bullet$;
at (2,1)$\bullet$; at (3,1.8)[anchor=south west]$Q_{p+1,q+1}$;[-stealth](3,2) – (2.2,1.2);
at (4,1) $\bullet$;   at (3.9,.9)[anchor=south west]$P_{p+1,q+2}$;
(0, 0) – (0,1)–(2,1);
[blue, thick, dotted](2,1)–(4,1);
[red, thick, dotted](2,1)–(2,2);
[decorate, decoration=  zigzag]  (0,0) – (-2,-2);
at (-1.3,-1.7)[anchor=north]$H^\alpha_{p+1}$;

at (0,0)$\bullet$;
at (0,1)$\bullet$;at (0.4,1)[anchor=north west]$R_{p+2,q+2}$;[-stealth](0.5,0.5) – (0.2,0.8);
at (1,1)$\bullet$;at (1,.8)[anchor=south west]$Q_{p+2,q+2}$;
at (2.5,-.5)$\ddots$;
(0, 0) – (0,1)–(1,1);
[blue, thick, dotted](1,1)–(2,1);
[red, thick, dotted](1,1)–(1,2);
[decorate, decoration=  zigzag]  (0,0) – (-2,-2);
at (-1.3,-1.7)[anchor=north]$H^\alpha_{p+2}$;

at (0,0)$\bullet$;
at (0,1)$\bullet$;at (0.4,1)[anchor=north west]$R_{p+t,q+t}$;[-stealth](0.5,0.5) – (0.2,0.8);
at (1,1)$\bullet$;at (.75,1)[anchor=south west]$Q_{p+t,q+t}$;
at (4,1) $\bullet$;   at (3.5,1)[anchor=south west]$P_{p+t,q+t+1}$;
at (4,0)$+$; at (3.5,0)[anchor=north west]$P'=\phi_\alpha^{-1}(i',j',k')$;
(0, 0) – (0,1)–(1,1);
[blue, thick, dotted](1,1)–(4,1);
[red, thick, dotted](1,1)–(1,2);
[red, thick, dotted](4,0)–(4,1);
[decorate, decoration=  zigzag]  (0,0) – (-2,-2);
at (-1.3,-1.7)[anchor=north]$H^\alpha_{p+t}$;

at (14, -1) $\Longrightarrow$;

at (0,0)$\bullet$;  at (0,1)[anchor=south west]$Q_{pq}$;
at (0,1) $+$;
at (4,1) $\bullet$;
[blue, thick, dotted] (0,0)–(2,0);
[red, thick, dotted] (0,0)–(0,2.5);
[decorate, decoration=  zigzag]  (0,0) – (-1,-1);
at (-.5,-.7)[anchor=north]$H'_p$;
at (0,0)$\bullet$;
at (0,1)$\bullet$;
at (1,1)$\bullet$;
at (2,1)$\bullet$;
at (4,1) $\bullet$;
(0,1)–(2,1)  (2,1)–(2,2);
[blue, thick, dotted](0,0)–(3,0);
[red, thick, dotted](0,0)–(0,1);
[decorate, decoration=  zigzag]  (0,0) – (-2,-2);
at (-1.3,-1.7)[anchor=north]$H'_{p+1}$;

at (0,0)$\bullet$;
at (0,1)$\bullet$;
at (1,1)$\bullet$;
at (2.5,-.5)$\ddots$;
[blue, thick, dotted](0,0)–(2,0);
[red, thick, dotted](0, 0) – (0,1);
[decorate, decoration=  zigzag]  (0,0) – (-2,-2);
at (-1.3,-1.7)[anchor=north]$H'_{p+2}$;

at (0,0)$\bullet$;
at (0,1)$\bullet$;
at (1,1)$\bullet$;
at (4,1) $\bullet$;
at (4,0)$\bullet$; at (3.5,0)[anchor=north west]$P'$;
(0,1)–(1,1) (4,0)–(4,1);
[blue, thick, dotted](4,0)–(0,0);
[red, thick, dotted](0,0)–(0,1);
[red, thick, dotted](1,1)–(1,2);
[decorate, decoration=  zigzag]  (0,0) – (-2,-2);
at (-1.3,-1.7)[anchor=north]$H'_{p+t}$;

Lemma <ref> Case 2. Left: before modification; right: after modification.

Now, define $P'=P_{p+t,q+t+1}+(1,0)$ and $(i',j',k')=\phi_\alpha(P')$,
define $C'=(C\setminus\{(i,j,k)\})\cup\{(i',j',k')\}$, keep all vertical paths unchanged, and modify each horizontal path $H^\alpha_{p+t'+1}$ into $H'_{p+t'+1}$ by replacing its subpath
$R_{p+t',q+t'}+(1,0)\to R_{p+t',q+t'}\to P_{p+t',q+t'+1}$
by a subpath
$R_{p+t',q+t'}+(1,0)\to P_{p+t',q+t'+1}+(1,0)\to P_{p+t',q+t'+1}$, as shown in Figure <ref>.  Since $C'$ is contained in the road map obtained after above modification, we see that $C'$ is $\uu$-compatible. Furthermore $C'$ is maximal $\uu$-compatible since $|C'|=|C|$. So $C'$ is a concurrent vertex map. It is obvious that  $(i,j,k)<_T (i',j',k')$ and $C<_T C'$.

Next, we show the uniqueness of $(i',j',k')$. Assume $(i'',j'',k'')$ is a point in $C''$ satisfying the conditions $(i,j,k)<_T (i'',j'',k'')$ and $C''=(C\setminus\{(i,j,k)\})\cup\{(i'',j'',k'')\}$ is a concurrent vertex map.
Then $P''=\phi_\alpha^{-1}(i'',j'',k'')$ does not lie weakly NW to $Q_{pq}=\phi_\alpha^{-1}(i,j,k)$. Denote $P''=\phi_\alpha^{-1}(i'',j'',k'')$.

We claim that, for $0\le t'\le t$, $H''_{p+t'}$ contains the subpath
$$R_{p+t',q+t'}+(1,0)\to P_{p+t',q+t'+1}+(1,0)\to P_{p+t',q+t'+1}.$$

We prove the claim by induction.

For $t'=0$, we already noted that the vertex $R_{pq}+(1,0)$ is in $H''_{p}$. The path $H''_{p}$ goes east from $R_{pq}+(1,0)$ until it reaches a SE corner $(x_0,y_0)$.
Since the value of $\bar{r}_{\phi_\alpha(P_{p,q+1})}$ does not decrease when replacing $C$ by $C''$, $H''_p$ must pass through a point weakly west of $P_{p,q+1}$; in other words, $y_0 \le (P_{p,q+1})_y$, the $y$-coordinate of $P_{p,q+1}$. We consider three cases:

(i) if $y_0 = (P_{p,q+1})_y$: the claim for $t'=0$ is obviously true.

(ii) if $(R_{p+1,q+1})_y \le y_0 < (P_{p,q+1})_y$: then $(x_0,y_0)\in \phi_\alpha^{-1}(C\cap C'')$. When replacing $C$ by $C''$, the horizontal path that contains $(x_0,y_0)$ changes from $H_{p+1}$ to $H''_p$, thus the value of $\bar{s}_{\phi_\alpha(x_0,y_0)}$ increases by 1. This implies that $P''$ lies SE of $(x_0,y_0)$. But then $\bar{r}_{\phi_\alpha(P_{p,q+1})}$ remains unchanged (which equals $p-1$), thus $H''_p$ contains $P_{p,q+1}$. Then $(x_0-1,y_0)$ must be a NW corner of $H''_p$, which must also be in $C''\setminus C=\{P''\}$. But $P''\neq(x_0-1,y_0)$ since $P''$ lies SE of $(x_0,y_0)$, a contradiction.  See Figure <ref> Left.

(iii) if $ y_0 < (R_{p+1,q+1})_y $, then $\phi_\alpha(x_0,y_0)\in C''\setminus C$, so is $P''=(x_0,y_0)$. Meanwhile, $H''_p$ must  pass through $P_{p,q+1}$, so must have a NW corner $(x_0-1,y_0)$. But then $(x_0-1,y_0)\neq P''$ is also in $C''\setminus C$, a contradiction.

For $t'>0$,  we know that the path $H''_{p+t'}$ goes east from $R_{p+t',q+t'}+(1,0)$ until it reaches a SE corner $(x_0,y_0)$. Similar as before, we have
$y_0\le (P_{p+t',q+t'+1})_y$. We consider three cases:

(i) if $y_0 = (P_{p+t',q+t'+1})_y$: the claim for $t'$ is obviously true.

(ii) if $(R_{p+t'+1,q+t'+1})_y \le y_0 < (P_{p+t',q+t'+1})_y$: then $(x_0,y_0)\in \phi_\alpha^{-1}(C\cap C'')$. When replacing $C$ by $C''$, the horizontal path that contains $(x_0,y_0)$ changes from $H_{p+t'+1}$ to $H''_{p+t'}$, thus the value of $\bar{s}_{\phi_\alpha(x_0,y_0)}$ increases by 1. This implies that $P''$ lies SE of $(x_0,y_0)$. But then $\bar{r}_{\phi_\alpha(P_{p+t',q+t'+1})}$ remains unchanged (which equals $p+t'-1$), thus $H''_{p+t'}$ contains $P_{p+t',q+t'+1}$.
So $(x_0-1,y_0)$ is a NW corner of $H''_{p+t'}$, which must also be in $\phi_\alpha^{-1}(C'')$. But $P''\neq(x_0-1,y_0)$ since $P''$ lies SE of $(x_0,y_0)$. So $(x_0-1,y_0)\in \phi_\alpha^{-1}(C)$, thus is contained in the horizontal segment $R_{p+t',q+t'}Q_{p+t',q+t'}$, which is a subpath of $H''_{p+t'-1}$ by the inductive hypothesis. So $(x_0-1,y_0)$ has to lie in both $H''_{p+t'}$ and $H''_{p+t'-1}$, a contradiction. See Figure <ref> Right.

(iii) if $ y_0 < (R_{p+t'+1,q+t'+1})_y $, then $\phi_\alpha(x_0,y_0)\in C''\setminus C$, so $P''=(x_0,y_0)$. Then $\bar{r}_{\phi_\alpha(P_{p+t',q+t'+1})}$ remains unchanged, so $H''_{p+t'}$ contains $P_{p+t',q+t'+1}$. But then $(x_0-1,y_0)$ is a NW corner of $H''_{p+t'}$, so is in $\phi_\alpha^{-1}(C)$, and thus is contained in the horizontal segment $R{_p+t',q+t'}\to Q_{p+t',q+t'}$ which is a subpath of $H''_{p+t'-1}$ by the inductive hypothesis. So $(x_0-1,y_0)$ has to lie in both $H''_{p+t'}$ and $H''_{p+t'-1}$, a contradiction.

This proves the above claim. In particular, when $t'=t$, the claim says that $H''_{p+t}$ contains $P_{p+t,q+t+1}+(1,0)=P'$. So $(i',j',k')$ is in a horizontal path induced from $C''$. Similarly, it is in a vertical path induced from $C''$. So it is in $C''$. This implies the uniqueness.

at (0,0)$\bullet$;
at (0,1) $\bullet$;      at (0,1)[anchor=south west]$Q_{pq}=R_{pq}$;
at (5,1) $\bullet$;  at (5,1)[anchor=south west]$P_{p,q+1}$;

[blue, thick, dotted](0,0)–(3,0)–(3,1)–(5,1);

[decorate, decoration=  zigzag]  (0,0) – (-1,-1);
at (-.5,-.7)[anchor=north]$H''_p$;

at (0,1)$\bullet$;
at (-.3,1.5)[anchor=south]$R_{p+1,q+1}$;[-stealth](0,1.6) – (0,1.2);
at (1,1)$\bullet$; at (1.1,1)[anchor=north]$(x_0,y_0)$;
at (2,1)$\bullet$;   at (1.1,3)[anchor=south]$(x_0-1,y_0)$;[-stealth](1,3) – (1,2.1);
at (3,1) $\bullet$;

at (-2,1)$\bullet$;
at (4,1)$\bullet$;
at (3,1)$\bullet$;
at (2,1)$\bullet$;
at (1,1)$\bullet$;
at (0,1) $\bullet$;
at (5.5,1.7)[anchor=south]$Q_{p+t',q+t'}$;[-stealth](5,1.7) – (4.2,1.2);
at (0,1.5)[anchor=south]$R_{p+t',q+t'}$;[-stealth](0,1.6) – (0,1.2);
at (3,1.5)[anchor=south]$(x_0-1,y_0)$;[-stealth](3,1.7) – (3,1.2);
at (6,1) $\bullet$;  at (6,1)[anchor=south west]$P_{p+t',q+t'+1}$;
(0, 1) – (4,1) ;
[blue, thick, dotted] (-2,1)–(0,1) (0,0)–(3,0)–(3,1)–(6,1);
at (-2.5,-0)[anchor=north]$H''_{p+t'-1}$;

[decorate, decoration=  zigzag]  (-3,0) – (-2,1);
[decorate, decoration=  zigzag]  (-1,-1) – (0,0);
at (0,0)$\bullet$;
at (-.7,-1)[anchor=north]$H''_{p+t'}$;

at (0,1)$\bullet$;
at (0.5,-.7)[anchor=south]$R_{p+t'+1,q+t'+1}$;[-stealth](0,0.2) – (0,.8);
at (1,1)$\bullet$; at (1.1,1)[anchor=north]$(x_0,y_0)$;

Lemma <ref> Case 2. Left: $t'=0$, case (ii); Right: case $t'>0$, case (ii).

Finally we show the stated consequence. Assume the contrary that an essential NW corner $(i,j,k)$ of $C=C_{\max}(S)$ is not in $S$. Without loss of generality, assume $(i,j,k)$ is an essential horizontal NW corner. Let $C'$ be the concurrent map constructed above. Then $C_{\max}(S)<_T C'$ and $S\subset C'$, contradicting the definition of $C_{\max}(S)$.

Let $C$ be a concurrent vertex map and $S$ be a subset of $C$. Then $C_{\max}(S)\ge_T C$, and the equality holds if and only $S$ contains all the essential horizontal and vertical NW corners of $C$.

$C_{\max}(S)\ge_T C$ is obvious. So we only need to prove the condition for the equality to hold.

“$\Rightarrow$”: we prove the contrapositive. Without lost of generality assume that $S$ does not contain an essential horizontal NW corner $(i,j,k)$ of $C$, so $S\subseteq C\setminus\{(i,j,k)\}$. By Lemma <ref>, there exists $C'=(C\setminus\{(i,j,k)\})\cup\{(i',j',k')\}>_TC$, so $C'$ contains $S$ and thus $C_{\max}(S)\ge_T C'>_T C$.

“$\Leftarrow$”:  Assume that $S$ contains all the essential horizontal and vertical NW corners of $C$. Let $C':=C_{\max}(S)$.

We will prove $C' =  C$ by contradiction: assume the contrary that $C' >_T C$.

$$\textrm{$(i,j,k)$ be the largest point in $C'\setminus C$ under the order ``$<_T$''.}$$

Note that a point $(i',j',k')$ satisfying $(i',j',k')>_T (i,j,k)$ lies in $C'$ if and only if it lies in $C$.

Then the choice of $(i,j,k)$ guarantees

\begin{equation}\label{eq:s=s}
\bar{s}_{ijk}(C')=\bar{s}_{ijk}(C).
\end{equation}

Let $\alpha={\rm t}(h_k)$, $\beta={\rm s}(h_k)$,
let $p_0=\bar{r}_{ijk}(C)$. By Proposition <ref>,
in $A_\alpha$,  $\phi_\alpha^{-1}(i,j,k)$ is strictly below $H_{p_0}^\alpha$ (if $p_0>0$) and weakly above $H_{p_0+1}^\alpha$ (if $p_0<u_\alpha-1$). Let $q_0$ be the integer in the range $0\le q_0\le v_\alpha-1$ such that $\phi_\alpha^{-1}(i,j,k)$ is strictly to the right of $V_{q_0}^\alpha$ (if $q_0>0$) and weakly to the left of $V_{q_0+1}^\alpha$ (if $q_0<v_\alpha-1$).

We shall construct s sequence of points

\begin{equation}\label{eq:sequence S}
S^\alpha_{p_0},T^\alpha_{p_0},S^\alpha_{p_0-1},T^\alpha_{p_0-1},\dots,S^\alpha_{1}, T^\alpha_1
\textrm{ in }A_\alpha
\end{equation}

recursively as follows.

Start from $\phi_\alpha^{-1}(i,j,k)$, walk west (for at least 1 unit) until reaching path $H^\alpha_{p_0}$ at point $S^\alpha_{p_0}$, then walk north along $H^\alpha_{p_0}$ (for at least one unit) until reaching a NW corner $T^\alpha_{p_0}$; then for $p=p_0, p_0-1,\dots,2$, once $T^\alpha_p$ is constructed, walk west from it (for at least 1 unit) until reaching path $H^\alpha_{p-1}$ at point $S^\alpha_{p-1}$,  then walk north along $H^\alpha_{p-1}$ (for at least 1 unit) until reaching a NW corner which we denote $T^\alpha_{p-1}$. (See an example in Figure <ref>.)

[gray] (0,0.5) rectangle (5.5,5.5);
[gray] (6,0.5) rectangle (11.5,5.5);
[gray] (12,0.5) rectangle (17.5,5.5);

[blue,densely dotted,thick](1.5,0.5) node[scale=.1] (v6)  – (0,0.5);
[blue,densely dotted,thick](2,1) node[scale=.1]  (v4)  – (0,1);
[blue,densely dotted,thick](3,1.5) node[scale=.1]  (v2)  – (0,1.5);
[blue,densely dotted,thick](2,0.5) node[scale=.1]  (v5)  – (3.5,0.5) node[scale=.1]  (v12) ;
[blue,densely dotted,thick](3,1) node[scale=.1]  (v3)  – (4.5,1) node[scale=.1]  (v10) ;
[blue,densely dotted,thick](4,2.5) node[scale=.1]  (v1)  – (5,2.5) node[scale=.1]  (v8) ;
[blue,densely dotted,thick](5,2) node[scale=.1]  (v9)  – (7,2) node[scale=.1]  (v16) ;
[blue,densely dotted,thick](5.5,3.5) node[scale=.1]  (v7)  – (8,3.5) node[scale=.1]  (v14)   (4.5,0.5) node[scale=.1]  (v11)  – (6.5,0.5) node [scale=.1] (v18) ;
[blue,densely dotted,thick](7,1.5) node[scale=.1]  (v17)  – (8.5,1.5) node[scale=.1]  (v24) ;
[blue,densely dotted,thick](9,4.5) node[scale=.1]  (v13)  – (10.5,4.5) node [scale=.1] (v20) ;
[blue,densely dotted,thick](11,5.5) node[scale=.1]  (v19)  – (13.5,5.5) node[scale=.1]  (v26) ;
[blue,densely dotted,thick](14.5,5.5) node[scale=.1]  (v25)  – (15,5.5) node[scale=.1]  (v32) ;
[blue,densely dotted,thick](17,5.5) node[scale=.1]  (v31)  – (17.5,5.5);
[blue,densely dotted,thick](8,3) node [scale=.1] (v15)  – (9.5,3) node[scale=.1]  (v22)   (10.5,4) node[scale=.1]  (v21)  – (13,4) node[scale=.1]  (v28) ;
[blue,densely dotted,thick](13.5,5) node [scale=.1] (v27)  – (14.5,5) node [scale=.1] (v34) ;
[blue,densely dotted,thick](15,5) node[scale=.1]  (v33)  – (17.5,5);
[blue,densely dotted,thick](9.5,2) node[scale=.1]  (v23)  – (12.5,2) node [scale=.1] (v30)   (13,3) node[scale=.1]  (v29)  – (13.5,3) node[scale=.1]  (v36) ;
[blue,densely dotted,thick](14.5,4.5) node[scale=.1]  (v35)  – (17.5, 4.5);
[red,densely dotted,thick](4, 6) – (v1)  (v2) – (v3)  (v4) – (v5)  (v6) – (1.5,0);
[red,densely dotted,thick](5.5, 6) – (v7)  (v8) – (v9)  (v10) – (v11)  (v12) – (3.5,0);
[red,densely dotted,thick](9, 6) – (v13)  (v14) – (v15)  (v16) – (v17)  (v18) – (6.5,0);
[red,densely dotted,thick](11,6) – (v19)  (v20) – (v21)  (v22) – (v23)  (v24) – (8.5,0);
[red,densely dotted,thick](14.5, 6) – (v25)  (v26) – (v27)  (v28) – (v29)  (v30) – (12.5,0);
[red,densely dotted,thick](17, 6) – (v31)  (v32) – (v33)  (v34) – (v35)  (v36) – (13.5,0);
[thick] (v6) – (v5);
[thick] (v4) – (v3);
[thick] (v12) – (v11);

[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v2) – (v1);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v10) – (v9);

[thick] (v8) – (5.1,2.5)–(5.1,2.7)–(5.3,2.7)–(5.3, 3.2)–(5.5,3.2)– (v7);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v14) – (v13);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm](v20) – (v19);
[thick] (v26) – (14.5,5.5);
[thick] (v32) – (v31);

[thick] (v16) – (7,2.2)–(7.3,2.2)–(7.3, 2.7)–(7.7,2.7)–(7.7,2.8)–(8,2.8)– (v15);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v22) – (v21);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v28) – (v27);
[thick] (v34) – (v33);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v18) – (v17);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v24) – (v23);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v30) – (v29);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm]  (v36) – (v35);

(v2) node [above left] $P_{11}$;
(v1) node [above left] $Q_{11}$;

(v7) node [above] $Q_{12}$;
(v8) node [above left] $P_{12}$;

(2,0.9) node [above] $P_{21}$;
(3,1.1) node [below] $Q_{21}$;

(1.5,.4) node [above] $P_{31}$;
(v5) node [below] $Q_{31}$;

(v9) node [left] $Q_{22}$;
(v10) node [above left] $P_{22}$;

(v11) node [below] $Q_{32}$;
(3.5,.6) node [below] $P_{32}$;

(v13) node [above left] $Q_{13}$;
(v14) node [above left] $P_{13}$;

(v15) node [right] $Q_{23}$;
(v16) node [above left] $P_{23}$;

(v17) node [left] $Q_{33}$;
(v18) node [right] $P_{33}$;

(v19) node [left] $Q_{14}$;
(v20) node [right] $P_{14}$;

(v21) node [left] $Q_{24}$;
(v22) node [right] $P_{24}$;

(v23) node [below right] $Q_{34}$;
(v24) node [below right] $P_{34}$;

(v25) node [above left] $Q_{15}$;
(v26) node [above left] $P_{15}$;

(v27) node [left] $Q_{25}$;
(v28) node [right] $P_{25}$;

(v29) node [left] $Q_{35}$;
(v30) node [right] $P_{35}$;

(v31) node [below] $Q_{16}$;
(v32) node [above ] $P_{16}$;

(v33) node [below] $Q_{26}$;
(v34) node [below left] $P_{26}$;

(v35) node [below right] $Q_{36}$;
(v36) node [right] $P_{36}$;

(0,1.5) node [left] $H^\alpha_1$;
(0,1) node [left] $H^\alpha_2$;
(0,0.5) node [left] $H^\alpha_3$;

(4,6) node [above] $V^\alpha_1$;
(5.5,6) node [above] $V^\alpha_2$;

(9,6) node [above] $V^\alpha_3$;
(11,6) node [above] $V^\alpha_4$;

(14.5,6) node [above] $V^\alpha_5$;
(17,6) node [above] $V^\alpha_6$;

[red] (11,2.2) circle(1.5pt) (7.3,2.2) circle(1.5pt)  (7.3,2.7) circle(1.5pt) (5.3,2.7) circle (1.5pt) (5.3,3.2) circle (1.5pt);
at (11,2.2)[anchor=south]$\phi_\alpha^{-1}(i,j,k)$;
[red, thick, dotted](11,2.2)–(7.3,2.2) (7.3,2.7)–(5.3,2.7);
(7.1,2.3) node [below right] $S^\alpha_{2}$;
(7.5,3) node [left] $T^\alpha_{2}$;
(5.1,2.4) node [right] $S^\alpha_{1}$;
(5.4,2.9) node [above left] $T^\alpha_{1}$;

An example of the sequence of points $S^\alpha_2, T^\alpha_2, S^\alpha_1, T^\alpha_1$ (with $p_0=2$) in (<ref>).

If some point in the sequence (<ref>) can be constructed, we call it constructable; otherwise we call it unconstructable. Obviously, if $S^\alpha_p$ is constructable, so is $T^\alpha_p$; if a point is unconstructable, so are all the points after it.  In the following claim, we will show that either all points are constructable, or none of them are.

Claim. “Any point in (<ref>) is unconstructable” $\Leftrightarrow$  “$S^\alpha_{p_0}$ is unconstructable” $\Leftrightarrow$ “$i=a_\alpha-u_\alpha+p_0+1$”.

Indeed,  $S^\alpha_{p_0}$ is unconstructable if walking west from $\phi_\alpha^{-1}(i,j,k)$ will never reach $H^\alpha_{p_0}$.
In this case, the $x$-coordinate of $\phi_\alpha^{-1}(i,j,k)$ is greater than the $x$-coordinate of the left endpoint of $H^\alpha_{p_0}$, that is, $i>a_\alpha-u_\alpha+p_0$.
Since $\phi_\alpha^{-1}(i,j,k)$ is weakly above $H_{p_0+1}^\alpha$,
the $x$-coordinate of $\phi_\alpha^{-1}(i,j,k)$ is no larger than the $x$-coordinate of the left endpoint of $H^\alpha_{p_0+1}$, that is, $i\le a_\alpha-u_\alpha+p_0+1$.
So we must have $i= a_\alpha-u_\alpha+p_0+1$.

Next consider the case  $S^\alpha_{p}$ is constructable but $S^\alpha_{p-1}$ is unconstructable for some $2\le p\le p_0$.
Then the $x$-coordinate of $S_p^\alpha$ is $> a_\alpha-u_\alpha+p$,
the $x$-coordinate of $S_{p+1}^\alpha$ is $> a_\alpha-u_\alpha+(p+1)$,
the $x$-coordinate of $S_{p_0}^\alpha$ is $i> a_\alpha-u_\alpha+p_0$. But then $S_{p_0}^\alpha$ is unconstructable, a contradiction to the assumption that $S^\alpha_{p}$ is constructable. So this case will never happen.

Assume the sequence of points in (<ref>) are constructable. Then $T^\alpha_{p_0},\dots,T^\alpha_1$ are horizontal NW corners of $C$, and form a diagonal chain in $A_\alpha$.
It is easy to see that:

\begin{equation}\label{eq:TonHV}
\textrm{$S^\alpha_p$ and $T^\alpha_p$ are on %the subpath
$H^\alpha_p\cap V^\alpha_{e_p}$ for $1\le p\le p_0$, where $1\le e_1<e_2<\cdots<e_{p_0}\le q_0$.}
\end{equation}

let $q_1=\bar{r}'_{ijk}(C)$.
For $\beta\in {\rm V}_{\rm source}$, let $H^\beta_1, \dots, H^\beta_{v_\beta}$ be the horizontal paths in $A^\beta$, and denote
$P'_{pq}\rightsquigarrow Q'_{pq}$ to be the subpath $H^\beta_p\cap V^\beta_q$ with SW endpoint $P'_{pq}$.
Assume that in $A_\beta$,  $\phi_\beta^{-1}(i,j,k)$ is strictly to the right of $V_{q_1}^\beta$ (if $q_1>0$) and weakly to the left of $V_{q_1+1}^\beta$ (if $q_1<u_\beta-1$). Let $p_1$ be the integer in the range $0\le p_1\le v_\beta-1$ such that $\phi_\beta^{-1}(i,j,k)$ is strictly below $V_{p_1}^\beta$ (if $p_1>0$) and weakly above  $V_{p_1+1}^\beta$ (if $p_1<v_\beta-1$).

We construct points $S^\beta_{q_1}, T^\beta_{q_1},S^\beta_{q_1-1}, T^\beta_{q_1-1},\dots,S^\beta_{1},T^\beta_{1}$ in $A_\beta$ recursively as follows.  Start from $\phi_\beta^{-1}(i,j,k)$, walk north until reaching path $V^\beta_{q_1}$ at point $S^\beta_{q_1}$, then walk west along $V^\beta_{q_1}$ until reaching a NW corner $T^\beta_{q_1}$; then for $q=q_1,q_1-1,\dots,2$, once $T^\beta_q$ is constructed, walk north from it until reaching path $V^\beta_{q-1}$ at point $S^\beta_{q-1}$,  then walk west along $V^\beta_{q-1}$ until reaching a NW corner which we denote $T^\beta_{q-1}$.

Note that “any of those point is unconstructable” $\Leftrightarrow$  “$S^\beta_{q_1}$ is unconstructable” $\Leftrightarrow$ $j=b_\beta-u_\beta+q_1+1$.

Assume those points are constructable. Then $T^\beta_{q_1},\dots,T^\beta_1$ in $A_\beta$  are vertical NW corners of $C$ and form a diagonal chain in $A^\beta$.
It is easy to see that:

\begin{equation}\label{eq:TonHV2}
\textrm{$S^\beta_q$ and $T^\beta_q$ are on %the subpath
$H^\beta_{f_q}\cap V^\beta_{q}$ for $1\le q\le q_1$, where $1\le f_1<f_2<\cdots<f_{q_1}\le p_1$.}
\end{equation}

We make the following observations:

Observation (a): $T^\alpha_{p_0},\dots,T^\alpha_1$ are all essential horizontal NW corners of $C$ if $\phi_\alpha^{-1}(i,j,k)$ lies on the SW side of the following broken line in $A_\alpha$:

$${\rm Bound}_1 := (1,(P_{1,1+v_\alpha-u_\alpha})_y)\to P_{1,1+v_\alpha-u_\alpha}\to P_{2,2+v_\alpha-u_\alpha}\to \cdots \to P_{u_\alpha v_\alpha}\to ((P_{u_\alpha v_\alpha})_x,b_\alpha).$$

(See Figure <ref> for an example of ${\rm Bound}_1$.)

[gray] (0,0.5) rectangle (5.5,5.5);
[gray] (6,0.5) rectangle (11.5,5.5);
[gray] (12,0.5) rectangle (17.5,5.5);

[blue,densely dotted,thick](1.5,0.5) node[scale=.1] (v6)  – (0,0.5);
[blue,densely dotted,thick](2,1) node[scale=.1]  (v4)  – (0,1);
[blue,densely dotted,thick](3,1.5) node[scale=.1]  (v2)  – (0,1.5);
[blue,densely dotted,thick](2,0.5) node[scale=.1]  (v5)  – (3.5,0.5) node[scale=.1]  (v12) ;
[blue,densely dotted,thick](3,1) node[scale=.1]  (v3)  – (4.5,1) node[scale=.1]  (v10) ;
[blue,densely dotted,thick](4,2.5) node[scale=.1]  (v1)  – (5,2.5) node[scale=.1]  (v8) ;
[blue,densely dotted,thick](5,2) node[scale=.1]  (v9)  – (7,2) node[scale=.1]  (v16) ;
[blue,densely dotted,thick](5.5,3.5) node[scale=.1]  (v7)  – (8,3.5) node[scale=.1]  (v14)   (4.5,0.5) node[scale=.1]  (v11)  – (6.5,0.5) node [scale=.1] (v18) ;
[blue,densely dotted,thick](7,1.5) node[scale=.1]  (v17)  – (8.5,1.5) node[scale=.1]  (v24) ;
[blue,densely dotted,thick](9,4.5) node[scale=.1]  (v13)  – (10.5,4.5) node [scale=.1] (v20) ;
[blue,densely dotted,thick](11,5.5) node[scale=.1]  (v19)  – (13.5,5.5) node[scale=.1]  (v26) ;
[blue,densely dotted,thick](14.5,5.5) node[scale=.1]  (v25)  – (15,5.5) node[scale=.1]  (v32) ;
[blue,densely dotted,thick](17,5.5) node[scale=.1]  (v31)  – (17.5,5.5);
[blue,densely dotted,thick](8,3) node [scale=.1] (v15)  – (9.5,3) node[scale=.1]  (v22)   (10.5,4) node[scale=.1]  (v21)  – (13,4) node[scale=.1]  (v28) ;
[blue,densely dotted,thick](13.5,5) node [scale=.1] (v27)  – (14.5,5) node [scale=.1] (v34) ;
[blue,densely dotted,thick](15,5) node[scale=.1]  (v33)  – (17.5,5);
[blue,densely dotted,thick](9.5,2) node[scale=.1]  (v23)  – (12.5,2) node [scale=.1] (v30)   (13,3) node[scale=.1]  (v29)  – (13.5,3) node[scale=.1]  (v36) ;
[blue,densely dotted,thick](14.5,4.5) node[scale=.1]  (v35)  – (17.5, 4.5);
[red,densely dotted,thick](4, 6) – (v1)  (v2) – (v3)  (v4) – (v5)  (v6) – (1.5,0);
[red,densely dotted,thick](5.5, 6) – (v7)  (v8) – (v9)  (v10) – (v11)  (v12) – (3.5,0);
[red,densely dotted,thick](9, 6) – (v13)  (v14) – (v15)  (v16) – (v17)  (v18) – (6.5,0);
[red,densely dotted,thick](11,6) – (v19)  (v20) – (v21)  (v22) – (v23)  (v24) – (8.5,0);
[red,densely dotted,thick](14.5, 6) – (v25)  (v26) – (v27)  (v28) – (v29)  (v30) – (12.5,0);
[red,densely dotted,thick](17, 6) – (v31)  (v32) – (v33)  (v34) – (v35)  (v36) – (13.5,0);
[thick] (v6) – (v5);
[thick] (v4) – (v3);
[thick] (v12) – (v11);

[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v2) – (v1);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v10) – (v9);

[thick] (v8) – (5.1,2.5)–(5.1,2.7)–(5.3,2.7)–(5.3, 3.2)–(5.5,3.2)– (v7);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v14) – (v13);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm](v20) – (v19);
[thick] (v26) – (14.5,5.5);
[thick] (v32) – (v31);

[thick] (v16) – (7,2.2)–(7.3,2.2)–(7.3, 2.7)–(7.7,2.7)–(7.7,2.8)–(8,2.8)– (v15);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v22) – (v21);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v28) – (v27);
[thick] (v34) – (v33);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v18) – (v17);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v24) – (v23);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (v30) – (v29);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm]  (v36) – (v35);

(v2) node [above left] $P_{11}$;
(v1) node [above left] $Q_{11}$;

(v7) node [above] $Q_{12}$;
(v8) node [above left] $P_{12}$;

(2,0.9) node [above] $P_{21}$;
(3,1.1) node [below] $Q_{21}$;

(1.5,.4) node [above] $P_{31}$;
(v5) node [below] $Q_{31}$;

(v9) node [left] $Q_{22}$;
(v10) node [above left] $P_{22}$;

(v11) node [below] $Q_{32}$;
(3.5,.6) node [below] $P_{32}$;

(v13) node [above left] $Q_{13}$;
(v14) node [above left] $P_{13}$;

(v15) node [right] $Q_{23}$;
(v16) node [above left] $P_{23}$;

(v17) node [left] $Q_{33}$;
(v18) node [right] $P_{33}$;

(v20) node [right] $P_{14}$;

(v21) node [left] $Q_{24}$;
(v22) node [right] $P_{24}$;

(v23) node [below right] $Q_{34}$;
(v24) node [below right] $P_{34}$;

(v25) node [above left] $Q_{15}$;
(v26) node [above left] $P_{15}$;

(v27) node [left] $Q_{25}$;
(v28) node [right] $P_{25}$;

(v29) node [left] $Q_{35}$;
(v30) node [right] $P_{35}$;

(v31) node [below] $Q_{16}$;
(v32) node [above ] $P_{16}$;

(v33) node [below] $Q_{26}$;
(v34) node [below left] $P_{26}$;

(v35) node [below right] $Q_{36}$;
(v36) node [right] $P_{36}$;

(0,1.5) node [left] $H^\alpha_1$;
(0,1) node [left] $H^\alpha_2$;
(0,0.5) node [left] $H^\alpha_3$;

(4,6) node [above] $V^\alpha_1$;
(5.5,6) node [above] $V^\alpha_2$;

(9,6) node [above] $V^\alpha_3$;
(11,6) node [above] $V^\alpha_4$;

(14.5,6) node [above] $V^\alpha_5$;
(17,6) node [above] $V^\alpha_6$;

[blue] (10.5,5.5) circle(1.5pt) (10.5,4.5) circle(1.5pt) (13,4) circle(1.5pt)  (13.5,3) circle(1.5pt) (17.5,3) circle(1.5pt);
[blue, very thick](10.5,5.5)–(10.5,4.5) – (13,4)–(13.5,3)–(17.5,3);
(10.5,5.5) node [above] $(1,(P_{14})_y)$;
(17.5,3) node [above left] $((P_{36)})_x,b_\alpha)$;
(17.5,3) node [below left] ${\rm Bound}_1$;

An example of ${\rm Bound}_1$.

Indeed, note that the $x$-coordinate of $\phi_\alpha^{-1}(i,j,k)$ is larger than the $x$-coordinate of $P_{p_0,p_0+v_\alpha-u_\alpha}$, so walking west from $\phi_\alpha^{-1}(i,j,k)$, we will meet $H^\alpha_{p_0}$ at the point $S^\alpha_{p_0}$ to the SW of $P_{p_0,p_0+v_\alpha-u_\alpha}$;
then $S^\alpha_{p_0}\to T^\alpha_{p_0}$, viewed as a subpath of $H^\alpha_{p_0}$, is on the left side of $P_{p_0,p_0+v_\alpha-u_\alpha}$;
$(T^\alpha_{p_0})_x \ge (P_{p_0,p_0+v_\alpha-u_\alpha})_x$ and
$(T^\alpha_{p_0})_y < (P_{p_0,p_0+v_\alpha-u_\alpha})_y$;
so $T^\alpha_{p_0} \neq Q_{p_0,p_0+v_\alpha-u_\alpha}$ and therefore is an essential NW corner.
Similarly, for $p=p_0, p_0-1,\dots,2$, once $T^\alpha_p$ is constructed, walk west to $S^\alpha_{p-1}$ to the SW of $P_{p-1,p-1+v_\alpha-u_\alpha}$,
we conclude that
$(T^\alpha_{p-1})_x \ge (P_{p-1,p-1+v_\alpha-u_\alpha})_x$ and
$(T^\alpha_{p-1})_y < (P_{p-1,p-1+v_\alpha-u_\alpha})_y$.
So $T^\alpha_{p-1}$ lies to the SW of ${\rm Bound}_1$, thus $T^\alpha_{p-1}\neq Q_{p-1,p-1+v_\alpha-u_\alpha}$, thus is an essential NW corner.

Similarly, we have the following, whose figure and proof are omitted:

Observation (b): $T^\beta_{q_1},\dots,T^\beta_1$ are all essential vertical NW corners of $C$ if $\phi_\beta^{-1}(i,j,k)$ is to the NE of the following broken line in $A_\beta$:

$${\rm Bound}_2=((Q'_{1+v_\beta-u_\beta})_x,1)\to Q'_{1+v_\beta-u_\beta,1}\to Q'_{2+v_\beta-u_\beta,2}\to \cdots \to Q'_{v_\beta u_\beta}\to (a_\beta,(Q'_{v_\beta u_\beta})_y).$$

Now we are ready to prove the desired contradiction for “$\Leftarrow$”  by discussing the following 4 cases separately.

Case 1: every point of $T^\alpha_1,\dots, T^\alpha_{p_0}$ and $T^\beta_1,\dots,T^\beta_{q_1}$ is either essential or unconstructable.

First we note that “$T^\alpha_1,\dots, T^\alpha_{p_0}$ are all essential or unconstructable” implies $\bar{r}_{ijk}(C')\ge p_0$; similarly, “$T^\beta_1,\dots, T^\beta_{q_1}$ are all essential or unconstructable” implies $\bar{r}'_{ijk}(C')\ge q_1$. We only prove the former since the latter is similar. Indeed,

– if these points are all essential, then by the assumption that $S$ contains all the essential NW corners of $C$, $\phi_\alpha^{-1}(S)$ must contain $T^\alpha_1,\dots, T^\alpha_{p_0}$, thus $\bar{r}_{ijk}(C')\ge p_0$.

– if one of these points is unconstructable (so all of them are unconstructable by the Claim in this proof), then $i=a_\alpha-u_\alpha+p_0+1$, and by definition,
\min(i-1,u_{\alpha}-1-\min(a_\alpha-i,b_\alpha-j'))
\ge \min(i-1,u_{\alpha}-1-(a_\alpha-i))
= \min(a_\alpha-u_\alpha+p_0,p_0)=p_0$.

In both cases,  $\bar{r}_{ijk}(C')\ge p_0=\bar{r}_{ijk}(C)$.
Together with (<ref>),
we have $\bar{r}_{ijk}(C)+\bar{s}_{ijk}(C)\le \bar{r}_{ijk}(C')+\bar{s}_{ijk}(C')=u_\alpha-1$.
Thus the equality $\bar{r}_{ijk}(C)+\bar{s}_{ijk}(C)=u_\alpha-1$ holds by Proposition <ref>,
and $\bar{r}_{ijk}(C') = p_0$.
Similarly, $\bar{r}'_{ijk}(C)+\bar{s}'_{ijk}(C)= u_\beta-1$ and $\bar{r}'_{ijk}(C')=q_1$. Thus $(i,j,k)\in C$ by Proposition <ref>, contradicting the assumption $(i,j,k)\notin C$.

Case 2: $T^\beta_1,\dots,T^\beta_{q_1}$ are essential or unconstructable, but for some $1\le a\le p_0$, $T^\alpha_a$ is non-essential (so $T^\alpha_a=Q_{a,a+v_\alpha-u_\alpha}$). Then $\bar{r}'_{ijk}(C)+\bar{s}'_{ijk}(C)= u_\beta-1$ and $\bar{r}'_{ijk}(C')=q_1$, for the similar reason we explain in Case 1. If $\bar{r}_{ijk}(C)+\bar{s}_{ijk}(C)=u_\alpha-1$ then $(i,j,k)\in C$, contradicting our assumption. So $\bar{r}_{ijk}(C)+\bar{s}_{ijk}(C)=u_\alpha$.

By Proposition <ref>,
$(i,j) \in V^{\beta}_{q_1+1}|_k$, but $(i,j)\notin H^\alpha_p|_k$ for any $p$. So there are $p,q$ such that $\phi_\alpha^{-1}(i,j,k)$ is on a path $V^\alpha_q$, and between the paths $H^\alpha_p$ and $H^\alpha_{p+1}$; therefore $\phi_\alpha^{-1}(i,j,k)$ lies in the interior of a vertical line segment $P_{p,q}Q_{p+1,q}$.

By Observation (a), $\phi^{-1}_\alpha(i,j,k)$ is weakly on the NE side of ${\rm Bound}_1$. So the whole segment $P_{p,q}Q_{p+1,q}$ is weakly on the NE side of  ${\rm Bound}_1$. Then $q\ge p+1+v_\alpha-u_\alpha$. By Lemma <ref>, the segment $P_{p,q}Q_{p+1,q}$ has length 1, which contradicts the fact that $\phi_\alpha^{-1}(i,j,k)$ lies in the interior of $P_{p,q}Q_{p+1,q}$.

Case 3: $T^\alpha_1,\dots,T^\alpha_{p_0}$ are essential or unconstructable, but for some $1\le b\le q_1$, $T^\beta_b$ is non-essential. We can get the desired contradiction as in Case 2.

Case 4: $T^\alpha_a=Q_{a,a+v_\alpha-u_\alpha}$ is non-essential for some $a$ such that $1\le a\le p_0$ and $a$ is the maximal choice, and $T^\beta_b=P_{b+v_\beta-u_\beta,b}$ is non-essential for some $b$ such that $1\le b\le q_1$ and $b$ is the maximal choice. Then $(i,j)$ lies in the intersection of the weakly NE side of ${\rm Bound}_1|_k$ and the weakly SE side of ${\rm Bound}_2|_k$.

$$D_1=p_1-p_0, \quad D_2=q_0-q_1.$$

Then $D_1$ is the number of horizontal paths in $A_\beta$ in those bocks above ${\rm Page}_k$,
$D_2$ is the number of vertical paths in $A_\alpha$ in those blocks to the left of ${\rm Page}_k$;

$$D_1=\sum_{r'_i<k} u_{\target(h_{r'_i})}, \quad
D_2=\sum_{r_i<k} u_{\source(h_{r_i})}. $$

We also have
$H^\alpha_p|_k=H^\beta_{p+D_1}|_k$ for $1\le p\le u_\alpha$,
$V^\beta_q|_k=H^\alpha_{q+D_2}|_k$ for $1\le q\le u_\beta$.

Since $\phi_\alpha^{-1}(i,j,k)$ is on the weakly NE side of ${\rm Bound}_1$, we have

\begin{equation}\label{eq:q0>=}
q_0\ge p_0+v_\alpha-u_\alpha.
\end{equation}

\begin{equation}\label{eq:p1>=}
p_1\ge q_1+v_\beta-u_\beta.
\end{equation}

From (<ref>) and (<ref>),
we get

$$\sum_{r'_i<k} u_{\target(h_{r'_i})}+\sum_{r_i<k} u_{\source(h_{r_i})} = D_1+D_2=(p_1-p_0)+(q_0-q_1)\ge v_\alpha-u_\alpha+v_\beta-u_\beta.$$

Since $\alpha={\target(h_{k})}$, $\beta={\source(h_{k})}$, $v_\alpha=\sum u_{\source(h_{r_i})}$,  $v_\beta=\sum u_{\target(h_{r'_i})}$, we have

$$\sum_{r'_i\le k} u_{\target(h_{r'_i})}+\sum_{r_i\le k} u_{\source(h_{r_i})}\ge \sum u_{\source(h_{r_i})}+\sum u_{\target(h_{r'_i})},$$

$$\sum_{r'_i> k} u_{\target(h_{r'_i})}+\sum_{r_i> k} u_{\source(h_{r_i})}\le 0.$$

Since $u_\gamma>0$ for any $\gamma$, there should be no summand at all in the above two sums. This implies the following:

– the equality $r_s=r'_t=k$ holds, that is,  ${\rm Page}_k$ is the rightmost block of $A_\alpha$, and is the bottommost block of $A_\beta$;

– the inequalities in (<ref>)  and (<ref>) become equalities, that is,

\begin{equation}\label{eq:qppq}
q_0 = p_0+v_\alpha-u_\alpha, \quad p_1 = q_1+v_\beta-u_\beta;
\end{equation}

– the equalities $D_1=v_\beta-u_\alpha$ and $D_2=v_\alpha-u_\beta$ hold, that is,

\begin{equation}\label{eq:ppqq}
p_1-p_0 = v_\beta-u_\alpha, \quad q_0-q_1=v_\alpha-u_\beta.
\end{equation}

From the first equation of (<ref>) and the second equation of (<ref>), we get $p_0+v_\alpha-u_\alpha=q_0=q_1+v_\alpha-u_\beta$, thus

\begin{equation}\label{eq:p0-q1}
\end{equation}

Without loss of generality, assume $p_0-a\le q_1-b$. Let $b'=a+q_1-p_0$, then $b\le b'\le q_1$ and $p_0-a=q_1-b'$.

We claim that the following holds for $d=0,\dots,p_0-a$:

(i) the subpath $P_{p_0-d,q_0-d}\rightsquigarrow Q_{p_0-d,q_0-d}$ is in the last block of $A_\alpha$, and

(ii) both $T^\alpha_{p_0-d}$ and $\phi_\alpha^{-1}\phi_\beta(T^\beta_{q_1-d})$ are on  $P_{p_0-d,q_0-d}\rightsquigarrow Q_{p_0-d,q_0-d}$, and

(iii) the point $T^\alpha_{p_0-d}$ is weakly SW of the point $\phi_\alpha^{-1}\phi_\beta(T^\beta_{q_1-d})$.

To show (i), note that
$q_0-d=(p_0+v_\alpha-u_\alpha)-d\ge v_\alpha-u_\alpha+a
= v_\alpha-u_\alpha+(p_0-q_1+b')\stackrel{\eqref{eq:p0-q1}}{=}
v_\alpha-u_\alpha+(u_\alpha-u_\beta+b')=v_\alpha-u_\beta+b'>v_\alpha-u_\beta$ (because $b'\ge b\ge1$).
Then (i) must hold because $A_\alpha$ has $v_\alpha$ vertical paths, $u_\beta$ of which are in the last block.
Therefore  the subpath $P_{p_0-d,q_0-d}\rightsquigarrow Q_{p_0-d,q_0-d}$, which is contained in the $(q_0-d)$-th vertical path $V^\alpha_{q_0-d}$, is in the last block.

To show (ii): since $T^\alpha_a=Q_{a,a+v_\alpha-u_\alpha}$, we have $e_a=a+v_\alpha-u_\alpha$, where $e_a$ is as  defined in (<ref>). Since $a+v_\alpha-u_\alpha=e_a<e_{a+1}<\cdots<e_{p_0}\le q_0=p_0+v_\alpha-u_\alpha$,  we must have $e_p=p+v_\alpha-u_\alpha$ for all $p$ in the range $a\le p\le p_0$. So for each $a\le p\le p_0$, $T^\alpha_{p}$ is on
$P_{p,p+v_\alpha-u_\alpha}\rightsquigarrow Q_{p,q+v_\alpha-u_\alpha}$.
Letting $d=p_0-p$, we see that
$T^\alpha_{p_0-d}$ lies on  $P_{p_0-d,q_0-d}\rightsquigarrow Q_{p_0-d,q_0-d}$ for $d=0,\dots,p_0-a$.  This proves half of (ii).

Similarly, using $f_q$ defined in (<ref>), we must have $f_q=q+v_\beta-u_\beta$ for all $q$ in the range $b\le q\le q_1$. So $T^\beta_q$ is on
$P'_{q+v_\beta-u_\beta,q}\rightsquigarrow Q'_{q+v_\beta-u_\beta,q}$ for all $b\le q\le q_1$.

Now consider those $q$ in the range $b'\le q\le q_1$.

Note that $H^\beta_{q+v_\beta-u_\beta}$ is in the last block of $A_\beta$ because
$q+v_\beta-u_\beta\ge b'+v_\beta-u_\beta = (a+q_1-p_0)+v_\beta-u_\beta \stackrel{\eqref{eq:p0-q1}}{=}
So $P'_{q+v_\beta-u_\beta,q}\rightsquigarrow Q'_{q+v_\beta-u_\beta,q}$ is in the last block of $A_\beta$.
Apply $\phi_\alpha^{-1}\phi_\beta$, we see that
$\phi_\alpha^{-1}\phi_\beta(T^\beta_q)$ is on
$\phi_\alpha^{-1}\phi_\beta(P'_{q+v_\beta-u_\beta,q}\rightsquigarrow Q'_{q+v_\beta-u_\beta,q})
=(P_{q+v_\beta-u_\beta-D_1,q+D_2}\rightsquigarrow Q_{q+v_\beta-u_\beta-D_1,q+D_2})

Let $d=q_1-q$, then the indices in the last expression become
$. Thus
$\phi_\alpha^{-1}\phi_\beta(T^\beta_{q_1-d})$ is indeed on  $P_{p_0-d,q_0-d}\rightsquigarrow Q_{p_0-d,q_0-d}$. This proves the other half of (ii).

To show (iii) by induction on $d$: for $d=0$, since $S^\alpha_{p_0}$ is to the west of $\phi_\alpha^{-1}(i,j,k)$,
$\phi_\alpha^{-1}\phi_\beta(S^\beta_{q_1})$ is to the north of $\phi_\alpha^{-1}(i,j,k)$, we see that
$S^\alpha_{p_0}$ is to the SW of $\phi_\alpha^{-1}\phi_\beta(S^\beta_{q_1})$, and therefore
$T^\alpha_{p_0}$ is weakly SW to $\phi_\alpha^{-1}\phi_\beta(T^\beta_{q_1})$.

Now assume $T^\alpha_{p_0-(d-1)}$ is weakly SW of $\phi_\alpha^{-1}\phi_\beta(T^\beta_{q_1-(d-1)})$, similar to
the above argument for $d=0$, we see that
$S^\alpha_{p_0-d}$ is SW of $\phi_\alpha^{-1}\phi_\beta(S^\beta_{q_1-d})$, and therefore
$T^\alpha_{p_0-d}$ is weakly SW of $\phi_\alpha^{-1}\phi_\beta(T^\beta_{q_1-d})$.

This completes the proof of (i)–(iii).

Now using (i)–(iii) for $d=p_0-a$, we see that the four points

$$(S,T,T',S')=(S^\alpha_a, T^\alpha_a,   \phi_\alpha^{-1}\phi_\beta(T^\beta_{a+q_1-p_0}), \phi_\alpha^{-1}\phi_\beta(T^\beta_{a+q_1-p_0}) )$$

are all on the path $P_{a,a+q_0-p_0}\rightsquigarrow Q_{a,a+q_0-p_0}$, and $S$ is to the south of $T$, $T$ is weakly SW of $T'$, $T'$ is to the west of $S'$. But $T=Q_{a,a+q_0-p_0}$ is the NE endpoint of the above path, so $T'=T$ and there is no place for $S'$, a contradiction. (See Figure <ref>.)

[gray] (0,0) rectangle (10,10);

(4,1) node [left] $P_{p_0,q_0}$;
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (4,1) – (5,2);
[thick] (5,2) – (5,3)–(5.5,3);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (5.5,3) – (7,4);
[thick] (7,4) – (7,4.5)–(8,4.5);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (8,4.5) – (9,6);
(9,6) node [right] $Q_{p_0,q_0}$;

(3,2) node [left] $P_{p_0-1,q_0-1}$;
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (3,2) – (4,2.5);
[thick] (4,2.5) – (4,4)–(4.5,4);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (4.5,4) – (6,5);
[thick] (6,5) – (6,5.5)–(7.5,5.5);
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (7.5,5.5) – (8,7);
(8,7) node [right] $Q_{p_0-1,q_0-1}$;

(1,3.5) node [left] $P_{a,a+q_0-p_0}$;
[thick, decorate,decoration=zigzag,segment length=2mm, amplitude=0.4mm] (1,3.5) – (2,4.5);
[thick] (2,4.5) – (2,5.5)–(2.5,5.5);