Let $x<y$ be two elements in a poset $P$. $y$ is said to $\bf cover$ $x$,
denoted by $x\lessdot y$, if the interval $[x,y]$ is the two element set
$\\{x,y\\}$. The covering relation of $P$ is the relation $\lessdot$ on $P$,
consisting of all such pairs in $P$. The Hasse diagram of the poset $(P,\leq)$
is the digraph $\mathscr{H}(P,\leq)$ on $P$ in which $(x,y)$ is an edge if and
only if $x\lessdot y$. Throughout this thesis, by the Hasse diagram of a
poset, we mean the underlying undirected graph of the Hasse diagram.

A maximal chain in $P$ is one not contained in any other chain in $P$. A
maximum chain in $P$ is one with maximal length. A chain $C$ is called
saturated if there does not exist an element $z\notin C$ and two elements
$x\leq y$ in $C$ such that $x\leq z\leq y$ and $z$ can be added to $C$ without
losing the property of being totally ordered.

The length $\operatorname{len}(C)$ of a finite chain $C$ is equal to $|C|-1$.
The length $\operatorname{len}(P)$ of a finite poset $P$ is the length of its
maximum chains. The length of an interval $[x,y]$ is denoted by
$\operatorname{len}(x,y)$.

We say that a poset $P$ is a graded poset if there exists an order preserving
rank function $\rho:P\rightarrow\mathbb{N}$ such that $x\lessdot y$ implies
that $\rho(x)=\rho(y)-1$. Equivalently, a poset $P$ is graded if and only if
for every $x\leq y$ in $P$ all the maximal chains in $[x,y]$ have the same
length. In a graded poset with a rank function $\rho$,
$\operatorname{len}(x,y)=\rho(y)-\rho(x)$ for every two elements $x\leq y$.

Let $P_{1},\dots,P_{n}$ be $n$ posets. The direct product (or product) order
$\leq$ on $P_{1}\times\dots\times P_{n}$ is the order in which
$(v_{1},\dots,v_{n})\leq(u_{1},\dots,u_{n})$ if $v_{i}\leq_{P_{i}}u_{i}$ for
every $1\leq i\leq n$. When we write $P_{1}\times\dots\times P_{n}$, we mean
the poset on $P_{1}\times\dots\times P_{n}$ equipped with the product order,
unless stated otherwise. Note that
$(v_{1},\dots,v_{n})\lessdot(u_{1},\dots,u_{n})$ in $P_{1}\times\dots\times
P_{n}$ if and only if $u_{i}$ covers $v_{i}$ in $P_{i}$ for some $1\leq i\leq
n$ and $u_{j}=v_{j}$ for every other $1\leq j\leq n$. The poset obtained by a
direct product of $(P,\leq)$ with itself $n$ times is denoted by
$(P^{n},\leq)$ or $P^{n}$. In this case, the meaning of $\leq$ should be clear
depending on the elements being compared.

######  Example 2.2.1.

$(\mathbb{Z}^{n},\leq)$ is a graded poset with a rank function
$\operatorname{rank}_{\leq}(v)=\sum_{1}^{n}v_{i}$. The distance between any
two elements $u=(u_{1},\dots,u_{n})$ and $v=(v_{1},\dots,v_{n})$ in its Hasse
diagram $\mathscr{H}(\mathbb{Z}^{n},\leq)$ is $\sum_{i=1}^{n}|u_{i}-v_{i}|$.

####  2.2.1 Lattices

Let $P$ be a poset and let $S\subseteq P$. The join of $S$ in $P$ is the least
upper bound of $S$ (if it exists). The join $s\vee t$ of two elements $s$ and
$t$ in $P$ is the join of $\\{s,t\\}$ in $P$. The meet of $S$ in $P$ is the
greatest lower bound of $S$ (if it exists). The meet $s\wedge t$ of two
elements $s$ and $t$ in $P$ is the meet of $\\{s,t\\}$ in $P$.

A poset $L$ is called a lattice if every two elements in $L$ have both a meet
and a join. A subposet $S$ of a lattice $L$ is called a sublattice if $S$ is
closed under the meet and join operations of $L$. For example, every interval
$[u,v]$ in a lattice $L$ is a sublattice of $L$. If $L$ and $M$ are lattices,
then so is $L\times M$ equipped with the product order.

######  Example 2.2.2.

$(\mathbb{Z}^{n},\leq)$ is a lattice with meet and join operations being the
point-wise $\min$ and $\max$, respectively.

If $P$ is a poset that has a least element $\hat{0}$ and a greatest element
$\hat{1}$ ($\hat{0}\leq p\leq\hat{1}$ for every $p$ in $P$), then we say that
$P$ is bounded. Note that every non-empty finite lattice is bounded (by taking
the meet and join of all the elements).

A lattice $L$ is said to be a modular lattice if $x\leq b$ implies that
$x\vee(a\wedge b)=(x\vee a)\wedge b$ for every $x,a,b\in L$. Clearly, every
sublattice of a modular lattice is modular.

######  Example 2.2.3.

$(\mathbb{Z}^{n},\leq)$ is a modular lattice.

######  Theorem 2.2.4.

([2, Lemma 1.2]) Let $L$ be a locally finite, modular lattice. Let $\rho$ be
its rank function. Denote the Hasse diagram of $L$ by $H$. Then for every
$s,t\in L$: $d_{H}(s,t)=\rho(s\vee t)-\rho(s\wedge t).$

####  2.2.2 The Dominance Order on $\mathbb{Z}^{n}$

######  Definition 2.2.5.

The dominance order $\trianglelefteq$ on $\mathbb{Z}^{n}$ is the order in
which $(v_{1},\dots,v_{n})\trianglelefteq(u_{1},\dots,u_{n})$ if
$\sum_{j=1}^{i}v_{j}\leq\sum_{j=1}^{i}u_{j}$ for every $1\leq i\leq n$.

######  Observation 2.2.6.

$(\mathbb{Z}^{n},\trianglelefteq)$ and $(\mathbb{Z}^{n},\leq)$ are isomorphic.
The following maps, $\chi$ and its inverse $\chi^{-1}$, are poset
isomorphisms.

$\begin{array}[]{llll}\chi:&(\mathbb{Z}^{n},\trianglelefteq)&\longrightarrow&(\mathbb{Z}^{n},\leq)\\\
&(v_{1},\dots,v_{n})&\longmapsto&(v_{1},v_{1}+v_{2},\dots,v_{1}+\dots+v_{n})\end{array}$
$\begin{array}[]{llll}\chi^{-1}:&(\mathbb{Z}^{n},\leq)&\longrightarrow&(\mathbb{Z}^{n},\trianglelefteq)\\\
&(v_{1},\dots,v_{n})&\longmapsto&(v_{1},v_{2}-v_{1},\dots,v_{n}-v_{n-1}).\end{array}$

Let $E$ be the standard basis of $\mathbb{R}^{n}$ as a vector space and let
$S=E\cup E^{-1}$. Note that the isomorphisms $\chi$ and $\chi^{-1}$ are also
automorphisms of $\mathbb{Z}^{n}$ as an additive group. Therefore, they are
determined by the mapping of the standard basis $E$. For example, for $n=3$

$\chi(u)=\left(\begin{array}[]{ccc}1&0&0\\\ 1&1&0\\\ 1&1&1\end{array}\right)u$

$\chi^{-1}(u)=\left(\begin{array}[]{ccc}1&0&0\\\ -1&1&0\\\
0&-1&1\end{array}\right)u.$

This implies that the generating set $\chi^{-1}(S)$ of $\mathbb{Z}^{n}$
describes the covering relation of $(\mathbb{Z}^{n},\trianglelefteq)$, since
the generating set $S$ describes the covering relation of
$(\mathbb{Z}^{n},\leq)$. In other words,
$\mathscr{H}(\mathbb{Z}^{n},\trianglelefteq)$ is the Cayley graph
$X(\mathbb{Z}^{n},\chi^{-1}(S))$, since the Hasse diagram
$\mathscr{H}(\mathbb{Z}^{n},\leq)$ is the Cayley graph $X(\mathbb{Z}^{n},S)$.

######  Observation 2.2.7.

The Hasse diagram $\mathscr{H}(\mathbb{Z}^{n},\trianglelefteq)$ is the Cayley
graph $X(\mathbb{Z}^{n},A)$ where
$A=\\{\pm(1,-1,0,\dots),\pm(0,1,-1,0,\dots),\dots,\pm(0,\dots,0,1)\\}$.

######  Observation 2.2.8.

Let $v=(v_{1},\dots,v_{n})$ and $u=(u_{1},\dots,u_{n})$ be two elements in
$\mathbb{Z}^{n}$. Examples 2.2.1, 2.2.2 and Observation 2.2.6 imply the
following properties.

  1. 1.

$(\mathbb{Z}^{n},\trianglelefteq)$ is a graded poset with the following rank
function:

$\operatorname{rank}_{\trianglelefteq}(v)=\operatorname{rank}_{\leq}(\chi(v))=\sum_{i=1}^{n}\sum_{j=1}^{i}v_{j}.$

  2. 2.

The distance between $u$ and $v$ in the Hasse diagram of
$(\mathbb{Z}^{n},\trianglelefteq)$ is as follows:

$\begin{split}d_{\mathscr{H}(\mathbb{Z}^{n},\trianglelefteq)}(v,u)&=d_{\mathscr{H}(\mathbb{Z}^{n},\leq)}(\chi(v),\chi(u))\\\
&=\sum_{i=1}^{n}|\chi(v)_{i}-\chi(u)_{i}|\\\
&=\sum_{i=1}^{n}|\sum_{k=1}^{i}(v_{k}-u_{k})|.\end{split}$

  3. 3.

$(\mathbb{Z}^{n},\trianglelefteq)$ is a lattice with the following meet and
join operations:

$v\wedge u=(\alpha_{1},\dots,\alpha_{n})\text{ where
}\alpha_{k}=\min\\{\sum\limits_{i=1}^{k}v_{i},\sum\limits_{i=1}^{k}u_{i}\\}-\min\\{\sum\limits_{i=1}^{k-1}v_{i},\sum\limits_{i=1}^{k-1}u_{i}\\};$
$v\vee u=(\beta_{1},\dots,\beta_{n})\text{ where
}\beta_{k}=\max\\{\sum\limits_{i=1}^{k}v_{i},\sum\limits_{i=1}^{k}u_{i}\\}-\max\\{\sum\limits_{i=1}^{k-1}v_{i},\sum\limits_{i=1}^{k-1}u_{i}\\}.$

##  Chapter 3 The Yoke Graphs $\mathrm{Y}_{n,m}$

In this chapter, we introduce Yoke graphs, the main object of this thesis.
After providing basic definitions in Section 3.1, we review three important
instances in Section 3.2 and discuss some group actions on these graphs in
Section 3.3.

###  3.1 Basic Definitions

For every non-negative integer $n$, denote the set $\\{0,\dots,n-1\\}$ by
$P_{n}$.

######  Definition 3.1.1.

Let $n\geq 1$ and $m\geq 0$ be two integers. The Yoke graph $\mathrm{Y}_{n,m}$
is a graph with vertices corresponding to all $v=(v_{0}\dots,v_{m+1})$ in
$\mathbb{Z}_{n}\times P_{2}^{m}\times\mathbb{Z}_{n}$ such that
$\sum_{i=0}^{m+1}v_{i}\equiv 0(\bmod n).$ Two vertices $u$ and $v$ are
adjacent in $\mathrm{Y}_{n,m}$, denoted $u\sim v$, if there exists $0\leq
i\leq m$ such that $u_{j}=v_{j}$ for every $j\notin\\{i,i+1\\}$ and one of the
following two cases holds: either $u_{i}=v_{i}+1$ and $u_{i+1}=v_{i+1}-1$, or
$u_{i}=v_{i}-1$ and $u_{i+1}=v_{i+1}+1$.

The name “Yoke graph” is derived from the shoulder yoke, a tool that can be
used to carry two buckets. Based on this analogy, we refer to the entries
$v_{0}$ and $v_{m+1}$ of a vertex $v$ in $\mathrm{Y}_{n,m}$ as the left bucket
and the right bucket of $v$, respectively.

######  Convention 3.1.2.

By Definition 3.1.1, the buckets of a vertex $v\in\mathrm{Y}_{n,m}$ are
elements (cosets) in the quotient group $\mathbb{Z}_{n}$ of $\mathbb{Z}$.
Throughout this thesis, a bucket is identified with its smallest non-negative
representative in $\mathbb{Z}$.

According to Convention 3.1.2, the sum $\sum_{i=0}^{m+1}v_{i}$ in Definition
3.1.1 is a non-negative integer. Note that a vertex $u$ in $\mathrm{Y}_{n,m}$
is determined by its first (or last) $m+1$ entries, since
$\sum_{i=0}^{m+1}u_{i}\equiv 0(\bmod n)$. When convenient, we identify a
vertex in $\mathrm{Y}_{n,m}$ by specifying its first (or last) $m+1$ entries.
We denote the vertex $(0,\dots,0)\in\mathrm{Y}_{n,m}$ by $0$.

In the first case of the adjacency relation in Definition 3.1.1, where
$u_{i}=v_{i}+1$ and $u_{i+1}=v_{i+1}-1$ for some $0\leq i\leq m$, we say that
$u$ is obtained from $v$ by shifting a unit from entry $i+1$ to the left, and
write $u=\overleftarrow{s}_{i}(v)$. In the second case, where $u_{i}=v_{i}-1$
and $u_{i+1}=v_{i+1}+1$, we say that $u$ is obtained from $v$ by shifting a
unit in entry $i$ to the right, and write $u=\overrightarrow{s}_{i}(v)$. For
an example of a Yoke graph, see $\mathrm{Y}_{3,3}$ in Figure 3.1. Observe that
$\mathrm{Y}_{n,m}$ is a connected simple graph.

(01110)(01101)(01011)(00111)(21111)(21102)(21012)(20112)(11112)(11100)(11010)(10110)(10101)(11001)(20001)(20010)(20100)(21000)0(00012)(00102)(01002)(10002)(10011)
Figure 3.1: $\mathrm{Y}_{3,3}$

######  Observation 3.1.3 (The case $m\leq 1$).

The cases $\mathrm{Y}_{1,0}$, $\mathrm{Y}_{2,0}$ and $\mathrm{Y}_{1,1}$ are
graphs on, at most, two vertices (see Figure 3.2). If $m=0$ and $2<n$, then
$\mathrm{Y}_{n,m}$ is the cycle graph on $n$ vertices and if $m=1$ and $1<n$,
then $\mathrm{Y}_{n,m}$ is the cycle graph on $2n$ vertices (see Figure 3.3).

(00)

(00)(11)

(000)(010)

Figure 3.2: $\mathrm{Y}_{1,0}$, $\mathrm{Y}_{2,0}$ and $\mathrm{Y}_{1,1}$

(00)(51)(42)(33)(24)(15)

(000)(210)(201)(111)(102)(012)

Figure 3.3: $\mathrm{Y}_{6,0}$ and $\mathrm{Y}_{3,1}$

###  3.2 Important Examples of Yoke Graphs

In this section, we show that the three flip graphs from Subsection 2.1.2 are
in fact instances of Yoke graphs. For every one of these graphs, we give its
isomorphism with the appropriate instance of a Yoke graph.

Colored Triangle-Free Triangulation Graphs

Recall the flip graph of colored triangle-free triangulations $\Gamma_{n}$
from Subsection 2.1.2. In [2, Definition 2.8], a bijection between its vertex
set $CTFT(n)$ and $\mathbb{Z}_{n}\times\\{0,1\\}^{n-4}$ is defined in order to
calculate the cardinality of $CTFT(n)$. This map is now used to prove that the
graphs $\Gamma_{n}$ and $\mathrm{Y}_{n,n-4}$ are isomorphic.

######  Definition 3.2.1.

Define the map $g:\Gamma_{n}\rightarrow\mathrm{Y}_{n,n-4}$ as follows. Let
$T\in\Gamma_{n}$. If the (short) chord labeled by $0$ in $T$ is $(a-1,a+1)$
for $a\in\mathbb{Z}_{n}$, then let $g(T)_{0}=a$. Extend the definition of
$g(T)_{i}$ iteratively for every $1\leq i\leq n-4$ as follows. First, note
that if the chord labeled by $i-1$ in $T$ is $(k,t)$, then the chord labeled
by $i$ is either $(k-1,t)$ or $(k,t+1)$. Now, let $g(T)_{i}$ be $0$ in the
former case and $1$ in the latter.

For example, assume that the edge $(0,6)$ in Figure 2.1 is labeled by $0$ in
$\Gamma_{8}$ (in both triangulations). Then these triangulations are mapped by
$g$ from $\Gamma_{8}$ to $\mathrm{Y}_{8,4}$. The left triangulation in the
figure is mapped to $(7,1,1,0,1,6)$ and the right is mapped to
$(7,1,0,1,1,6)$.

######  Observation 3.2.2.

It is straightforward to verify that $g$ is a bijection and that a chord flip
of the chord labeled by $i\in\\{0,\dots,n-4\\}$ in $T\in\Gamma_{n}$
corresponds to the case in the adjacency relation in $\mathrm{Y}_{n,n-4}$,
where a unit is shifted between the entries indexed by $i$ and $i+1$ of
$g(T)$. This implies that $g$ is a graph isomorphism.

Note that if $P_{n}$ would be extended to be defined similarly in the case
$n=4$, then the resulting graph $\Gamma_{4}$ would be a graph on $2$ vertices,
whereas $\mathrm{Y}_{4,0}$ is a graph on $4$ vertices. The definition of a
coloring of a triangle-free triangulation can be modified (from how it appears
in Subsection 2.1.2 and in [2]) such that the linear order is applied to the
triangles instead of the chords. This will extend the correspondence between
$\Gamma_{n}$ and $\mathrm{Y}_{n,n-4}$ to the case of $\Gamma_{4}$. In this
case, however, the flip action of the chord in $\Gamma_{4}$ is not involutive
(in contrast to the case $n\geq 5$) and its definition should be refined to
include “direction” of the flip.

Arc Permutation Graphs

Recall the flip graph of arc permutations $X_{n}$ from Subsection 2.1.2. In
[5, Subsection 6.2], a bijection between its vertex set $\mathcal{A}_{n}$ and
$\mathbb{Z}_{n}\times\\{0,1\\}^{n-2}$ is defined in order to embed $X_{n}$ in
the Hasse diagram of the dominance order on
$\\{0,\dots,n-1\\}\times\\{0,1\\}^{n-2}$. This map is now used to prove that
the graphs $X_{n}$ and $\mathrm{Y}_{n,n-2}$ are isomorphic.

######  Definition 3.2.3.

Define the map $f:X_{n}\rightarrow\mathrm{Y}_{n,n-2}$ as follows. Let $\pi\in
X_{n}$ and set $f(\pi)_{0}=\pi(1)-1$. Extend the definition of $f(\pi)_{i}$
iteratively for every $1\leq i\leq n-2$ as follows. Let $I_{i}$ be the
underlying set $\\{\pi(1),\dots,\pi(i)\\}$ of the interval formed by the
prefix of $\pi$ up to $i$. First, note that either $(\pi(i+1)-1)\bmod n\in
I_{i}$ or $(\pi(i+1)+1)\bmod n\in I_{i}$, since the interval $I_{i}$ must be
extended by $\pi(i+1)$. Now, let $f(\pi)_{i}$ be $1$ in the former case and
$0$ in the latter.

4321342132413214231421341234124314231432413243123412234121434123

$\rightarrow$
(3,0,0,1)(2,1,0,1)(2,0,1,1)(2,0,0,2)(1,1,0,2)(1,0,1,2)(0,1,1,2)(0,1,0,3)(0,0,1,3)(0,0,0,0)(3,1,0,0)(3,0,1,0)(2,1,1,0)(1,1,1,1)(1,0,0,3)(3,1,1,3)

Figure 3.4: $f:X_{4}\rightarrow\mathrm{Y}_{4,2}$

######  Observation 3.2.4.

It is straightforward to verify that $f$ is a bijection and that right
multiplication of $\pi\in X_{n}$ by the transposition $(i,i+1)$ (for $1\leq
i\leq n-1$) corresponds to the case in the adjacency relation in
$\mathrm{Y}_{n,n-2}$, where a unit is shifted between the entries indexed by
$i-1$ and $i$ of $f(\pi)$. This implies that $f$ is a graph isomorphism.

Geometric Caterpillar Graphs

Recall the flip graph of caterpillars $\mathcal{G}_{n}$ from Subsection 2.1.2.

######  Definition 3.2.5.

Let $C\in\mathcal{G}_{n}$ and let
$I(C)=[a,a+1,\dots,a+k]\subseteq\mathbb{Z}_{n}$ be the interval induced by the
spine of $C$ ($2\leq k$). Note that $a$ and $a+k$ are leaves of $C$. Define a
complete ordering $S(C)=(s_{0},s_{1},\dots,s_{n-3})$ on $n-2$ vertices of $C$
as follows. Set $s_{0}=a$. Define the interval $I_{0}(C)$ to be
$[a,a+1]\subset\mathbb{Z}_{n}$. Define $I_{i}(C)$ and $s_{i}$ iteratively for
every $1\leq i\leq n-3$ as follows. Assume that $I_{i-1}(C)=[l,\dots,r]$. If
$(l-1,r)$ is an edge in $C$, then $I_{i}(C)=[l-1,l,\dots,r]$ and $s_{i}=l-1$.
Otherwise, $I_{i}(C)=[l,\dots,r,r+1]$ and $s_{i}=r+1$.

Note that in the $i$-th iteration in Definition 3.2.5, if $I_{i-1}=[l,r]$ and
$(l-1,r)$ is not an edge in $C$, then $C$ has no leaf connected to $r$ that is
not in $I_{i-1}$. This implies that the iterations in the definition induce a
sequence $S(C)$ of distinct $n-2$ vertices and $n-2$ intervals that
monotonously increase in size.

For example, let $C$ be the leftmost caterpillar in Figure 2.5. Then
$S(C)=(7,6,5,4,1,3)$, $I_{0}(C)=[7,0]$, $I_{1}(C)=[6,7,0]$,
$I_{2}(C)=[5,6,7,0]$, $I_{3}(C)=[4,5,6,7,0]$, $I_{4}(C)=[4,5,6,7,0,1]$ and
$I_{5}(C)=[3,4,5,6,7,0,1]$.

######  Definition 3.2.6.

Let $C\in\mathcal{G}_{n}$. Let $I_{i}$ (for $0\leq i\leq n-3$) and let
$S(C)=(s_{0},s_{1},\dots,s_{n-3})$ be as in Definition 3.2.5. Define the map
$h:\mathcal{G}_{n}\rightarrow\mathrm{Y}_{n,n-3}$ as follows. Set
$h(C)_{0}=s_{0}$. Extend the definition of $h(C)_{i}$ iteratively for every
$1\leq i\leq n-3$ as follows. Assume that $I_{i-1}=[l,r]$. Note that either
$s_{i}=l-1$ or $s_{i}=r+1$. Let $h(C)_{i}$ be $1$ in the former case and $0$
in the latter.

For example, let $C\in\mathcal{G}_{8}$ be the leftmost caterpillar in Figure
2.5. Then $h$ maps $C$ to $\mathrm{Y}_{8,5}$ and $h(C)=(7,1,1,1,0,1,5)$.

######  Observation 3.2.7.

It is straightforward to verify that $h$ is a bijection and that shifting an
edge incident with a leaf along the spine in $C\in\mathcal{G}_{n}$ corresponds
to a unit shift between two entries indexed by $i$ and $i+1$ of $h(C)$ for
some $0\leq i\leq m$. This implies that $h$ is a graph isomorphism.

###  3.3 Group Actions on $\mathrm{Y}_{n,m}$

######  Definition 3.3.1.

Let $n\geq 1$ and $m\geq 1$. Define the set $\mathcal{S}_{n,m}=\\{s_{i}:0\leq
i\leq m\\}$ where $s_{i}$ is the map
$s_{i}:\mathrm{Y}_{n,m}\rightarrow\mathrm{Y}_{n,m}$ defined as follows:

$s_{0}(v)=\begin{cases}\overleftarrow{s}_{0}(v),&\text{if }v_{1}=1\\\
\overrightarrow{s}_{0}(v),&\text{if
}v_{1}=0\end{cases},\;\;\;\;\;s_{m}(v)=\begin{cases}\overleftarrow{s}_{m}(v),&\text{if
}v_{m}=0\\\ \overrightarrow{s}_{m}(v),&\text{if }v_{m}=1\end{cases}$

and for every $1\leq i\leq m-1$

$s_{i}(v)=(v_{0},\dots,v_{i+1},v_{i},\dots,v_{m+1})=\begin{cases}\overleftarrow{s}_{i}(v),&\text{if
}(v_{i},v_{i+1})=(0,1)\\\ \overrightarrow{s}_{i}(v),&\text{if
}(v_{i},v_{i+1})=(1,0)\\\ v,&\text{if }v_{i}=v_{i+1}\end{cases}.$

######  Observation 3.3.2.

Every $s_{i}$ in $\mathcal{S}_{n,m}$ is a distinct involutive permutation of
the vertex set of $\mathrm{Y}_{n,m}$.

######  Definition 3.3.3.

Denote the group generated by $\mathcal{S}_{n,m}$ by $\mathrm{G}_{n,m}$.

$\mathrm{G}_{n,m}$ is a subgroup of the symmetric group on the $n2^{m}$
vertices of $\mathrm{Y}_{n,m}$. Clearly, every edge $e$ in $\mathrm{Y}_{n,m}$
corresponds with the action of a unique generator $s_{i}\in\mathcal{S}_{n,m}$
on the endpoints of $e$. Therefore, $\mathrm{G}_{n,m}$ defines a faithful
group action on the vertices of $\mathrm{Y}_{n,m}$. Note that this action is
transitive, since $\mathrm{Y}_{n,m}$ is connected. This, combined with Remark
2.1.1, implies the following observation.

######  Observation 3.3.4.

Let $n\geq 1$ and $m\geq 1$. Then $\mathrm{Y}_{n,m}$ is the Schreier graph of
$\mathrm{G}_{n,m}$ with respect to the generating set $\mathcal{S}_{n,m}$ and
the action of $\mathrm{G}_{n,m}$ on $\mathrm{Y}_{n,m}$.

Recall that the affine Weyl group of type $\tilde{C}_{m}$ is the group
generated by $S=\\{\sigma_{0},\dots,\sigma_{m}\\}$ ($m\geq 2$) whose Coxeter
relations are the following (see e.g. [7]):

$\displaystyle\sigma_{i}^{2}=Id$ $\displaystyle\quad\mbox{for all }0\leq i\leq
m;$ $\displaystyle(\sigma_{i}\sigma_{j})^{2}=Id$ $\displaystyle\quad\mbox{for
all }|j-i|>1;$ $\displaystyle(\sigma_{i}\sigma_{i+1})^{3}=Id$
$\displaystyle\quad\mbox{for all }1\leq i\leq m-2;$
$\displaystyle(\sigma_{0}\sigma_{1})^{4}=(\sigma_{m-1}\sigma_{m})^{4}=Id.$

######  Proposition 3.3.5.

Let $n\geq 1$ and $m\geq 2$. The generators $\mathcal{S}_{n,m}$ of
$\mathrm{G}_{n,m}$ satisfy the Coxeter relations of $\tilde{C}_{m}$.

###### Proof.

The generators in $\mathcal{S}_{n,m}$ are involutive and $s_{i}$ and $s_{j}$
clearly commute whenever $|j-i|>1$. Therefore the first two relations,
$s_{i}^{2}=Id$ for all $0\leq i\leq m$ and $(\sigma_{i}\sigma_{j})^{2}=Id$ for
all $|j-i|>1$, are true. It can be verified that
$s_{i}s_{i+1}s_{i}=s_{i+1}s_{i}s_{i+1}$ for every $1\leq i\leq m-2$. This
proves the third relation: $(s_{i}s_{i+1})^{3}=Id$ for all $1\leq i\leq m-2$.
Note that the orbit of every vertex in $\mathrm{Y}_{n,m}$ under the action of
$\left<s_{0}s_{1}\right>$ (and $\left<s_{m-1}s_{m}\right>$) is of size $4$.
This proves the final relation: $(s_{0}s_{1})^{4}=(s_{m-1}s_{m})^{4}=Id$. ∎

######  Corollary 3.3.6.

Let $n\geq 1$ and $m\geq 2$. $\mathrm{G}_{n,m}$ is a quotient of the affine
Weyl group $\tilde{C}_{m}$.

######  Corollary 3.3.7.

Let $n\geq 1$, $m\geq 2$ and let $S=\\{\sigma_{0},\dots,\sigma_{m}\\}$ be the
generators of the affine Weyl group of type $\tilde{C}_{m}$.

  1. 1.

For every $0\leq i\leq m$, define the action of $\sigma_{i}$ on
$\mathrm{Y}_{n,m}$ by $\sigma_{i}(v)=s_{i}(v)$ as in Definition 3.3.1 . Then,
by Proposition 3.3.5, the action of $\tilde{C}_{m}$ on $\mathrm{Y}_{n,m}$,
induced by extending the actions of $\sigma_{i}$ multiplicatively, is well
defined.

  2. 2.

$\mathrm{Y}_{n,m}$ is the Schreier graph of $\tilde{C}_{m}$ with respect to
the generating set $S=\\{\sigma_{0},\dots,\sigma_{m}\\}$ and the above action
of $\tilde{C}_{m}$ on $\mathrm{Y}_{n,m}$.

Corollary 3.3.7 generalizes [2, Proposition 3.2] and [5, Corollary 10.4], by
which the colored triangle-free triangulation graphs $\Gamma_{n}$ and the arc
permutation graphs $X_{n}$ are Schreier graphs of the affine Weyl group of
type $\tilde{C}_{n-4}$ for $n>5$ and $\tilde{C}_{n-2}$ for $n>3$,
respectively.

##  Chapter 4 The Eccentricity of $0$ in $\mathrm{Y}_{n,m}$

The main purpose of this chapter is to develop the theory that will allow us
to state and prove the following theorem.

######  Theorem 4.0.1.

Let $n\geq 1$ and $m\geq 0$.

  1. 1.

If $n=1$, then
$\operatorname{ecc}_{\mathrm{Y}_{n,m}}(0)=\binom{\lceil\frac{m}{2}\rceil+1}{2}+\binom{\lfloor\frac{m}{2}\rfloor+1}{2}$.

  2. 2.

If $0\leq m\leq n$, then
$\operatorname{ecc}_{\mathrm{Y}_{n,m}}(0)=\lfloor\frac{n(m+1)}{2}\rfloor$.

  3. 3.

If $2\leq n\leq m$, let
$d^{0}_{n,m}=\binom{\lfloor\frac{m+n}{2}\rfloor+1}{2}+\binom{\lceil\frac{m-n}{2}\rceil+1}{2}$.
Then

    1. (a)

if either $2\divides(m-n)$ or $n\leq\lceil\frac{m+1}{2}\rceil$, then
$\operatorname{ecc}_{\mathrm{Y}_{n,m}}(0)=d^{0}_{n,m}$;

    2. (b)

otherwise,
$\operatorname{ecc}_{\mathrm{Y}_{n,m}}(0)=d^{0}_{n,m}+n-\lceil\frac{m+1}{2}\rceil$.

###### Proof.

The theorem is the combined result of Observation 4.0.2 and Lemmas 4.3.1,
4.3.2, 4.3.7, 4.3.10 and 4.3.12 that appear in the following sections. ∎

######  Observation 4.0.2 (The case $m\leq 1$).

By Observation 3.1.3, Theorem 4.0.1 clearly holds for $m\leq 1$.

In the rest of this chapter, unless explicitly stated otherwise, we assume
that $m\geq 2$.

###  4.1 The Shift Direction Lemma

Let $\mathcal{S}_{n,m}$ be the set of generators of $\mathrm{G}_{n,m}$ as in
Definition 3.3.1. A word $w$ in the letters $\mathcal{S}_{n,m}$ is a sequence
$f_{d}\cdots f_{1}$ where $f_{1},\dots,f_{d}\in\mathcal{S}_{n,m}$. Let $P$ be
a path $(v=v^{0}\sim\dots\sim v^{d}=u)$ in $\mathrm{Y}_{n,m}$. Clearly, there
is a unique word $f_{d}\cdots f_{1}$ such that $f_{t}(v^{t-1})=v^{t}$ for
every $1\leq t\leq d$ or, equivalently, $f_{t}\cdots f_{1}(v)=v^{t}$ for every
$1\leq t\leq d$. We say that $f_{d}\cdots f_{1}$ is the word corresponding to
the path $P$ from $v$ to $u$ (or corresponding to the path $P$ starting at
$v$).

Note that a word $f_{d}\cdots f_{1}$ does not correspond to a path starting at
$v$ if $f_{t}\cdots f_{1}(v)=f_{t+1}f_{t}\cdots f_{1}(v)$ for some $1\leq
t\leq d-1$. For example, the word $s_{1}s_{0}$ corresponds to the path
$(v=(0,1,1,1)\sim(1,0,1,1)\sim(1,1,0,1))$ in $\mathrm{Y}_{3,2}$ starting at
$v$. However, $s_{0}s_{1}$ does not correspond to a path starting at $v$,
since $v$ is a fixed point of $s_{1}$.

Let $f_{d}\cdots f_{1}$ be the word corresponding to a path
$(v=v^{0}\sim\dots\sim v^{d})$ in $\mathrm{Y}_{n,m}$ starting at $v$. For
convenience, if $v^{t}=\overleftarrow{s}_{i}(v^{t-1})$ for some $0\leq i\leq
m$ and $1\leq t\leq d$, then we write $f_{t}=\overleftarrow{s}_{i}$.
Similarly, if $v^{t}=\overrightarrow{s}_{i}(v^{t-1})$, then we write
$f_{t}=\overrightarrow{s}_{i}$.

######  Lemma 4.1.1 (Shift Direction Lemma).

Let $f_{d}\cdots f_{1}$ be the word corresponding to a geodesic in
$\mathrm{Y}_{n,m}$. For every $0\leq i\leq m$, all of the instances of
$s_{i}\in\mathcal{S}_{n,m}$ in $f_{d}\cdots f_{1}$ shift in the same
direction.

###### Proof.

Let $v$ and $u$ be two vertices in $\mathrm{Y}_{n,m}$. Assume to the contrary
that there exist words corresponding to geodesics from $v$ to $u$ not
satisfying the lemma. Denote the set of such words by $\mathcal{W}$. For every
word $f_{d}\cdots f_{1}$ in $\mathcal{W}$, there exist $0\leq i\leq m$ and
$1\leq t_{1},t_{2}\leq d$ such that $f_{t_{1}}=\overrightarrow{s}_{i}$ and
$f_{t_{2}}=\overleftarrow{s}_{i}$. Let $w=f_{d}\cdots f_{1}$ be a word in
$\mathcal{W}$ in which
$\min\\{|t_{2}-t_{1}|:f_{t_{1}}=\overrightarrow{s}_{i},f_{t_{2}}=\overleftarrow{s}_{i}\\}$
is minimal. Assume without loss of generality that $t_{1}<t_{2}$.

If $t_{2}=t_{1}+1$, then the word obtained by deleting both $f_{t_{1}}$ and
$f_{t_{2}}$ from $f_{d}\cdots f_{1}$ is a word corresponding to a shorter path
from $v$ to $u$, contradicting the minimality of $d$. Therefore, we can assume
that $t_{2}-t_{1}>1$.

If $f_{t_{1}+1}=s_{j}$ for some $0\leq j\leq m$ such that $|i-j|>1$, then
$f_{t_{1}}$ and $f_{t_{1}+1}$ commute as functions, and the word obtained by
interchanging $f_{t_{1}}$ and $f_{t_{1}+1}$ in $w$ corresponds to a path from
$v$ to $u$. This contradicts the minimality of $t_{2}-t_{1}$ in the choice of
$w$. Therefore,
$f_{t_{1}+1}\in\\{\overrightarrow{s}_{i-1},\overrightarrow{s}_{i+1}\\}$.

Let $v^{\prime}=f_{t_{1}+1}\cdots f_{1}(v)$. If
$f_{t_{1}+1}=\overrightarrow{s}_{i-1}$, then $v^{\prime}_{i}=1$. Since
$f_{t_{2}}=\overleftarrow{s}_{i}$, there must exist some $t_{1}+1<k<t_{2}$
such that $f_{k}=\overleftarrow{s}_{i-1}$ or $f_{k}=\overrightarrow{s}_{i}$.
Similarly, if $f_{t_{1}+1}=\overrightarrow{s}_{i+1}$, then
$v^{\prime}_{i+1}=0$ and there must exist some $t_{1}+1<k<t_{2}$ such that
$f_{k}=\overleftarrow{s}_{i+1}$ or $f_{k}=\overrightarrow{s}_{i}$. All of the
cases contradict the minimality of $t_{2}-t_{1}$. ∎

###  4.2 Pivots and Walls

######  Definition 4.2.1 (Pivot).

A pivot of a vertex $v\in\mathrm{Y}_{n,m}$ is an integer $-1\leq p\leq m+1$
such that $\sum_{i=0}^{p}v_{i}$ is divisible by $n$. We call $-1$ and $m+1$
the outer pivots of $v$; they are pivots of every $v\in\mathrm{Y}_{n,m}$.
Every other pivot, if it exists, is called an inner pivot. Denote the set of
pivots of $v$ by $\operatorname{Piv}(v)$.

For example, in $\mathrm{Y}_{3,5}$,
$\operatorname{Piv}((0,1,1,0,1,1,2))=\\{-1,0,4,6\\}$.

######  Definition 4.2.2 (Wall).

Let $P$ be a path from $v$ to $0$ in $\mathrm{Y}_{n,m}$ and let $f_{d}\cdots
f_{1}$ be the word corresponding to $P$. An inner wall of $P$ is an integer
$0\leq p\leq m$ such that $s_{p}$ does not appear in $f_{d}\cdots f_{1}$. $-1$
is a left outer wall of $P$ if $\overleftarrow{s}_{0}$ does not appear in
$f_{d}\cdots f_{1}$. Similarly, $m+1$ is a right outer wall of $P$ if
$\overrightarrow{s}_{m}$ does not appear in $f_{d}\cdots f_{1}$. Finally, we
say that $-1\leq p\leq m+1$ is a wall of $P$ if it is either an inner wall or
an outer wall of $P$.

Clearly, paths from $v$ to $0$ with a wall $p$ exist if and only if $p$ is a
pivot of $v$.

######  Definition 4.2.3 (Pivot Path).

Let $p$ be a pivot of a vertex $v$ in $\mathrm{Y}_{n,m}$. We say that a path
$P$ from $v$ to $0$ is a $p$-pivot path of $v$, if $P$ is shortest among the
paths from $v$ to $0$ with a wall $p$. Denote the length of a $p$-pivot path
of $v$ by $\sigma_{p}(v)$. We say that $P$ is a pivot path, if it is a
$p$-pivot path for some $p$.

For example, let $v=(2,0,1,1,2)$ in $\mathrm{Y}_{3,3}$.
$\overrightarrow{s}_{3}\overleftarrow{s}_{0}\overleftarrow{s}_{1}$ is a word
corresponding to a $2$-pivot path $P$ of $v$:
$P=(v=(2,0,1\|1,2)\sim(2,1,0\|1,2)\sim(0,0,0\|1,2)\sim(0,0,0\|0,0)=0)$ where
we added the symbol $\|$ to visualize the wall $2$ of $P$. For an example of
an outer pivot path with a wall -1, let $v=(1,0,1,0)$ in $\mathrm{Y}_{2,2}$.
$\overrightarrow{s}_{2}\overrightarrow{s}_{1}\overrightarrow{s}_{0}\overrightarrow{s}_{2}$
is a word corresponding to a $(-1)$-pivot path $P$ of $v$:
$P=(v=(\|1,0,1,0)\sim(\|1,0,0,1)\sim(\|0,1,0,1)\sim(\|0,0,1,1)\sim(\|0,0,0,0)=0)$.

######  Lemma 4.2.4.

Every geodesic in $\mathrm{Y}_{n,m}$ ending at $0$ is a pivot path (namely,
has a wall).

###### Proof.

Let $w=f_{d}\cdots f_{1}$ be the word corresponding to a geodesic $P$ in
$\mathrm{Y}_{n,m}$ from $v$ to $0$. Assume to the contrary that $P$ has no
walls. Therefore, both $\overleftarrow{s}_{0}$ and $\overrightarrow{s}_{m}$
appear in $w$ (since $P$ has no outer walls); and by the Shift Direction Lemma
4.1.1, exactly one of $\\{\overleftarrow{s}_{i},\overrightarrow{s}_{i}\\}$
appears in $w$ (at least once) for every $0\leq i\leq m$. Let $1\leq i\leq m$
be minimal such that $\overrightarrow{s}_{i}$ appears in $w$. Therefore, both
$\overleftarrow{s}_{i-1}$ and $\overrightarrow{s}_{i}$ appear in $w$. This is
a contradiction, since it implies that, throughout $P$, at least two units are
shifted from the entry $v_{i}$ and no units are shifted to $v_{i}$. ∎

######  Observation 4.2.5.

By Lemma 4.2.4,

$\operatorname{ecc}_{\mathrm{Y}_{n,m}}(0)=\max_{v}d(v,0)=\max_{v}\min_{p}\sigma_{p}(v).$

######  Definition 4.2.6.

Let $v\in\mathrm{Y}_{n,m}$ and $p\in\operatorname{Piv}(v)$. If (one,
equivalently all) $p$-pivot paths of $v$ are also geodesics between $v$ and
$0$, then we say that $p$ is a geodesic pivot of $v$.

The Shift Direction Lemma 4.1.1 deals with geodesics, or equivalently (by
Lemma 4.2.4) with $p$-pivot paths for geodesic pivots $p$. It can be extended
to arbitrary pivot paths, with essentially the same proof.

######  Lemma 4.2.7 (Pivot Shift Direction Lemma).

Let $f_{d}\cdots f_{1}$ be the word corresponding to a pivot path in
$\mathrm{Y}_{n,m}$. For every $0\leq i\leq m$, all of the instances of $s_{i}$
in $f_{d}\cdots f_{1}$ shift in the same direction.

######  Observation 4.2.8.

Let $P$ be a $p$-pivot path of $v$, and let $w$ be the word corresponding to
$P$. Then, for each $i<p$, if $s_{i}$ appears in $w$, then it appears as
$\overleftarrow{s}_{i}$; and, for each $i>p$, if $s_{i}$ appears in $w$, then
it appears as $\overrightarrow{s}_{i}$.

######  Corollary 4.2.9.

Let $v\in\mathrm{Y}_{n,m}$ and let $p\in\operatorname{Piv}(v)$. Then

$\sigma_{p}(v)=\sum_{i=1}^{p}iv_{i}+\sum_{i=p+1}^{m}(m+1-i)v_{i}.$

In particular, if $p$ is an inner pivot, then

$\sigma_{p}(v)\leq\binom{p+1}{2}+\binom{m-p+1}{2}.$

######  Definition 4.2.10.

For $v\in\mathrm{Y}_{n,m}$ define:

  1. 1.

$p_{l}(v)=\max\\{p\in\operatorname{Piv}(v):p\leq\frac{m}{2}\\}$;

  2. 2.

$p_{r}(v)=\min\\{p\in\operatorname{Piv}(v):p>\frac{m}{2}\\}$.

We abbreviate $p_{l}$, $p_{r}$ when $v$ is evident.

Note that if $p_{1}$ and $p_{2}$ are two pivots of $v$ such that $-1\leq
p_{1}<p_{2}\leq\frac{m}{2}$, then $\sigma_{p_{2}}(v)\leq\sigma_{p_{1}}(v)$.
Similarly, if $\frac{m}{2}<p_{1}<p_{2}\leq m+1$, then
$\sigma_{p_{1}}(v)\leq\sigma_{p_{2}}(v)$. This implies the following
observation.

######  Observation 4.2.11.

Let $v\in\mathrm{Y}_{n,m}$. Then

$d(v,0)=\min_{p}\sigma_{p}(v)=\min\\{\sigma_{p_{l}}(v),\sigma_{p_{r}}(v)\\}.$

######  Fact 4.2.12.

Let $m,p,q$ be integers such that $0\leq p\leq m$, $0\leq q\leq m$ and
$|p-\frac{m}{2}|<|q-\frac{m}{2}|$. Then
$\sum_{i=1}^{p}i+\sum_{i=1}^{m-p}i<\sum_{i=1}^{q}i+\sum_{i=1}^{m-q}i$.

######  Lemma 4.2.13.

For any $n\geq 1$ and $m\geq 0$,
$\operatorname{ecc}_{\mathrm{Y}_{n,m}}(0)\geq\lfloor\frac{n(m+1)}{2}\rfloor$.

###### Proof.

If $m\leq 1$, this lemma follows from Observation 3.1.3. If $n=1$, it follows
from Lemma 4.3.1. Let $n,m\geq 2$, and let $u\in\mathrm{Y}_{n,m}$ be defined
as follows: $u_{0}=u_{m+1}=\lfloor\frac{n}{2}\rfloor$. If $n$ is even, then
$u_{i}=0$ for all $1\leq i\leq m$, and if $n$ is odd, then
$u_{\lfloor\frac{m+1}{2}\rfloor}=1$ and $u_{i}=0$ for all other $1\leq i\leq
m$. For example:

n | m | u
---|---|---
4 | 2 | $(2,0,0,2)$
4 | 3 | $(2,0,0,0,2)$
5 | 4 | $(2,0,1,0,0,2)$
5 | 5 | $(2,0,0,1,0,0,2)$

In all of these cases, $u$ has no inner pivots, that is,
$\operatorname{Piv}(u)=\\{-1,m+1\\}$. Therefore, by Observation 4.2.11,
$d(u,0)=\min\\{\sigma_{-1}(u),\sigma_{m+1}(u)\\}$. Note that
$\sum_{i=0}^{m+1}u_{i}=n$. Therefore, by Corollary 4.2.9,

$\sigma_{-1}(u)+\sigma_{m+1}(u)=\sum_{i=0}^{m}(m+1-i)u_{i}+\sum_{i=1}^{m+1}iu_{i}=n(m+1).$

It now suffices to show that $|\sigma_{-1}(u)-\sigma_{m+1}(u)|\leq 1$, since
this implies that $\operatorname{ecc}_{\mathrm{Y}_{n,m}}(0)\geq
d(u,0)=\lfloor\frac{n(m+1)}{2}\rfloor$.

Clearly, if either $2\divides n$ or $2\divides(m-n)$, then
$\sigma_{-1}(u)=\sigma_{m+1}(u)$. If $2\ndivides n$ and $2\divides m$, then
$|\sigma_{-1}(u)-\sigma_{m+1}(u)|=1$. This implies that
$|\sigma_{-1}(u)-\sigma_{m+1}(u)|\leq 1$, as required. ∎

######  Lemma 4.2.14.

Let $v\in\mathrm{Y}_{n,m}$ such that $v$ has no inner pivots. Then
$d(v,0)\leq\lfloor\frac{n(m+1)}{2}\rfloor$.

###### Proof.

Note that $v\neq 0$ and $\sum_{i=0}^{m+1}v_{i}=n$, since $v$ has no inner
pivots. Therefore, by Corollary 4.2.9 and Observation 4.2.11,

$\displaystyle d(v,0)$
$\displaystyle=\min\\{\sigma_{-1}(v),\sigma_{m+1}(v)\\}$
$\displaystyle\leq\lfloor\frac{\sigma_{-1}(v)+\sigma_{m+1}(v)}{2}\rfloor=\lfloor\frac{\sum_{i=0}^{m+1}iv_{i}+\sum_{i=0}^{m+1}(m+1-i)v_{i}}{2}\rfloor$
$\displaystyle=\lfloor\frac{n(m+1)}{2}\rfloor.$

∎

###  4.3 Computation of the Eccentricity

######  Lemma 4.3.1 ($n=1$).

Let $m\geq 0$. Then

$\operatorname{ecc}_{\mathrm{Y}_{1,m}}(0)=\binom{\lceil\frac{m}{2}\rceil+1}{2}+\binom{\lfloor\frac{m}{2}\rfloor+1}{2}.$

###### Proof.

The case $m=0$ is trivial. Assume that $m>0$. Note that since $n=1$,
$\operatorname{Piv}(v)=\\{-1,\ldots,m+1\\}$ for every $v\in\mathrm{Y}_{n,m}$.
Therefore, by Corollary 4.2.9, Observation 4.2.11 and Fact 4.2.12,
$d(v,0)\leq\sigma_{\lceil\frac{m}{2}\rceil}(v)\leq\sum_{i=1}^{\lceil\frac{m}{2}\rceil}i+\sum_{i=1}^{\lfloor\frac{m}{2}\rfloor}i=\binom{\lceil\frac{m}{2}\rceil+1}{2}+\binom{\lfloor\frac{m}{2}\rfloor+1}{2}$.
This upper bound is obtained by the vertex $v\in\mathrm{Y}_{n,m}$ with
$v_{i}=1$ for every $1\leq i\leq m$. ∎

######  Lemma 4.3.2.

If $0\leq m\leq n$, then
$\operatorname{ecc}_{\mathrm{Y}_{n,m}}(0)=\lfloor\frac{n(m+1)}{2}\rfloor$.

###### Proof.

The case $m\leq 1$ is true by Observation 3.1.3. Assume that $m\geq 2$. By
Lemma 4.2.13, it is sufficient to show that
$\operatorname{ecc}_{\mathrm{Y}_{n,m}}(0)\leq\lfloor\frac{n(m+1)}{2}\rfloor$.
Let $v\in\mathrm{Y}_{n,m}$. By Lemma 4.2.14, we can assume that $v$ has some
inner pivot $p\in\operatorname{Piv}(v)$. By Corollary 4.2.9 and Fact 4.2.12
(with $q=m$),
$d(v,0)\leq\sigma_{p}(v)\leq\binom{p+1}{2}+\binom{m-p+1}{2}\leq\binom{m+1}{2}$.
Since $m\leq n$, $\binom{m+1}{2}\leq\frac{n(m+1)}{2}$ and therefore
$d(v,0)\leq\lfloor\frac{n(m+1)}{2}\rfloor$. ∎

Throughout the rest of this subsection, we assume that $2\leq n\leq m$.

######  Definition 4.3.3.

Let $v\in\mathrm{Y}_{n,m}$.

  1. 1.

$I_{c}(v)=[p_{l}(v)+1,p_{r}(v)]$. If $v_{p_{l}+1}=v_{p_{r}}=0$ (and
$p_{l}+1=p_{r}$), then we say that $I_{c}(v)$ is trivial. We abbreviate
$I_{c}$ when $v$ is evident.

  2. 2.

$h(v)=\min\\{|p-\frac{m}{2}|:p\in\operatorname{Piv}(v)\\}$.

  3. 3.

$\eta_{n,m}=\begin{cases}\frac{n}{2}&\mbox{if }2\divides(m-n)\\\
\frac{n+1}{2}&\mbox{if }2\ndivides(m-n)\end{cases}.$

The outline of the rest of this subsection is as follows. We first construct
two candidates for a vertex eccentric to $0$ in Definitions 4.3.4 and 4.3.5
and compute their distances from $0$ in Lemma 4.3.7. We then prove that the
maximum of the two distances is an upper bound on the distance of an arbitrary
vertex $v$ from $0$. We split this proof into two cases.

  1. 1.

$h(v)<\eta_{n,m}$ (Lemma 4.3.10).

  2. 2.

$h(v)\geq\eta_{n,m}$ (Lemma 4.3.12).

######  Definition 4.3.4 ($u^{0}_{n,m}$).

Let $u\in\mathrm{Y}_{n,m}$ such that $u_{i}=1$ for all $1\leq i\leq m$ and
$u_{0}\equiv-\lfloor\frac{m-n}{2}\rfloor\bmod n$. Denote this vertex by
$u^{0}_{n,m}$ and denote $d^{0}_{n,m}=d(u^{0}_{n,m},0)$.

For example, $u^{0}_{3,5}=(2,1,1,1,1,1,2)$ and
$u^{0}_{3,6}=(2,1,1,1,1,1,1,1)$.

######  Definition 4.3.5 ($u^{1}_{n,m}$).

Assume that $2\ndivides(m-n)$. Let $u\in\mathrm{Y}_{n,m}$ such that $u_{i}=0$
for $i=\lceil\frac{m+1}{2}\rceil$, $u_{i}=1$ for all other $1\leq i\leq m$ and
$u_{0}\equiv-\lfloor\frac{m-n}{2}\rfloor\bmod n$. Denote this vertex by
$u^{1}_{n,m}$ and denote $d^{1}_{n,m}=d(u^{1}_{n,m},0)$.

For example, $u^{1}_{2,5}=(1,1,1,0,1,1,1)$ and
$u^{1}_{3,6}=(2,1,1,1,0,1,1,2)$.

######  Observation 4.3.6.

  1. 1.

If $2\divides(m-n)$, then $h(u^{0}_{n,m})=\frac{n}{2}=\eta_{n,m}$.

  2. 2.

If $2\ndivides(m-n)$, then $h(u^{0}_{n,m})=\frac{n-1}{2}=\eta_{n,m}-1$ and
$h(u^{1}_{n,m})=\frac{n+1}{2}=\eta_{n,m}$.

######  Lemma 4.3.7.

  1. 1.

$d^{0}_{n,m}=\binom{\lfloor\frac{m+n}{2}\rfloor+1}{2}+\binom{\lceil\frac{m-n}{2}\rceil+1}{2}$.

  2. 2.

If $2\ndivides(m-n)$, then
$d^{1}_{n,m}=d^{0}_{n,m}+n-\lceil\frac{m+1}{2}\rceil$.

###### Proof.

Note that by definition,
$p_{l}(u^{0}_{n,m})=p_{l}(u^{1}_{n,m})=\lfloor\frac{m-n}{2}\rfloor$ and
$p_{r}(u^{0}_{n,m})=\lfloor\frac{m+n}{2}\rfloor$. Regarding $d^{0}_{n,m}$: if
$2\divides(m-n)$, then
$|p_{l}(u^{0}_{n,m})-\frac{m}{2}|=|p_{r}(u^{0}_{n,m})-\frac{m}{2}|=\frac{n}{2}$.
It follows, by Corollary 4.2.9 and Observation 4.2.11, that
$d^{0}_{n,m}=d(u^{0}_{n,m},0)=\sigma_{p_{l}}(u^{0}_{n,m})=\sigma_{p_{r}}(u^{0}_{n,m})=\binom{\frac{m+n}{2}+1}{2}+\binom{\frac{m-n}{2}+1}{2}$.
If $2\ndivides(m-n)$, then
$|p_{l}(u^{0}_{n,m})-\frac{m}{2}|=|p_{r}(u^{0}_{n,m})-\frac{m}{2}|+1=\frac{n+1}{2}$.
Therefore
$d^{0}_{n,m}=d(u^{0}_{n,m},0)=\sigma_{p_{r}}(u^{0}_{n,m})=\binom{\lfloor\frac{m+n}{2}\rfloor+1}{2}+\binom{\lceil\frac{m-n}{2}\rceil+1}{2}$.

Regarding $d^{1}_{n,m}$: if $2\divides n$ and $2\ndivides m$, then
$|p_{l}(u^{1}_{n,m})-\frac{m}{2}|=|p_{r}(u^{1}_{n,m})-\frac{m}{2}|=\frac{n+1}{2}$
and computation gives
$d^{1}_{n,m}=d(u^{1}_{n,m},0)=\sigma_{p_{l}}(u^{1}_{n,m})=\sigma_{p_{r}}(u^{1}_{n,m})=d^{0}_{n,m}+n-\frac{m+1}{2}$.
If $2\ndivides n$ and $2\divides m$, then again
$|p_{l}(u^{1}_{n,m})-\frac{m}{2}|=|p_{r}(u^{1}_{n,m})-\frac{m}{2}|=\frac{n+1}{2}$,
but (since the entry at $\lceil\frac{m+1}{2}\rceil$ of $u^{1}_{n,m}$ is equal
to zero) $\sigma_{p_{r}}(u^{1}_{n,m})<\sigma_{p_{l}}(u^{1}_{n,m})$ and
$d^{1}_{n,m}=d(u^{1}_{n,m},0)=\sigma_{p_{r}}(u^{1}_{n,m})=d^{0}_{n,m}+n-\lceil\frac{m+1}{2}\rceil$.
∎

######  Definition 4.3.8 ($d_{n,m}$).

Denote

$d_{n,m}=\begin{cases}d^{0}_{n,m}&\mbox{if }2\divides(m-n);\\\
\max\\{d^{0}_{n,m},d^{1}_{n,m}\\}&\mbox{if }2\ndivides(m-n).\end{cases}$

######  Observation 4.3.9.

$\operatorname{ecc}_{\mathrm{Y}_{n,m}}(0)\geq d_{n,m}$.

It now suffices to show that $d(v,0)\leq d_{n,m}$ for each
$v\in\mathrm{Y}_{n,m}$. As noted above we distinguish two cases.

######  Lemma 4.3.10.

Let $v\in\mathrm{Y}_{n,m}$ such that $h(v)<\eta_{n,m}$. Then $d(v,0)\leq
d_{n,m}$.

###### Proof.

We show that actually $d(v,0)\leq d^{0}_{n,m}$. Let $p^{\prime}$ be an inner
pivot of $v$ for which $|p^{\prime}-\frac{m}{2}|=h(v)$. By Observation 4.3.6,
if $2\divides(m-n)$, then $h(u^{0}_{n,m})=\frac{n}{2}=\eta_{n,m}$, and if
$2\ndivides(m-n)$, then $h(u^{0}_{n,m})=\eta_{n,m}-1$. By assumption,
$h(v)\leq\eta_{n,m}-1$ and therefore $h(v)\leq h(u^{0}_{n,m})$. By Corollary
4.2.9 and Fact 4.2.12,
$d(v,0)\leq\sum_{i=1}^{p^{\prime}}i+\sum_{i=1}^{m-p^{\prime}}i\leq\sum_{i=1}^{p}i+\sum_{i=1}^{m-p}i=d^{0}_{n,m}$
∎

The following lemma generalizes Lemma 4.2.14.

######  Lemma 4.3.11.

Let $v\in\mathrm{Y}_{n,m}$. Then
$d(v,0)\leq\sum_{i=1}^{p_{l}}i+\sum_{i=1}^{m-p_{r}}i+\lfloor\frac{n(m+1)}{2}\rfloor.$

###### Proof.

Recall the definition of $I_{c}=I_{c}(v)$ (Definition 4.3.3). The sum
$\sum_{i=1}^{p_{l}}i+\sum_{i=1}^{m-p_{r}}i$ is an upper bound on the number of
steps needed to set to $0$ every $v_{i}$ with $i\in[1,m]\setminus I_{c}$,
without shifting units into $I_{c}$; note that necessarily, following these
steps, a bucket of $v$ not in $I_{c}$, is also equal to $0$. We can therefore
assume that $v_{i}=0$ for every $i\notin I_{c}$ and prove that
$d(v,0)\leq\lfloor\frac{n(m+1)}{2}\rfloor$. Note that $\sum_{i\in I_{c}}v_{i}$
is either $0$ or $n$. Therefore, as in the proof of Lemma 4.2.14,
$d(v,0)\leq\min\\{\sigma_{p_{l}}(v),\sigma_{p_{r}}(v)\\}\leq\lfloor\frac{\sigma_{p_{l}}(v)+\sigma_{p_{r}}(v)}{2}\rfloor\leq\lfloor\frac{n(m+1)}{2}\rfloor.$
∎

######  Lemma 4.3.12.

Let $v\in\mathrm{Y}_{n,m}$ such that $h(v)\geq\eta_{n,m}$. Then $d(v,0)\leq
d_{n,m}$.

###### Proof.

Assume that $2|(m-n)$. By Lemma 4.3.11,
$d({v},0)\leq\sum_{i=1}^{p_{l}}i+\sum_{i=1}^{m-p_{r}}i+\frac{n(m+1)}{2}$.
Since $h(v)\geq\eta_{n,m}=\frac{n}{2}$, $p_{l}\leq\frac{m-n}{2}$ and
$p_{r}\geq\frac{m+n}{2}$. Therefore
$d(v,0)\leq\sum_{i=1}^{\frac{m-n}{2}}i+\sum_{i=1}^{m-\frac{m-n}{2}}i+\frac{n(m+1)}{2}=d^{0}_{n,m}$.

Assume that $2\ndivides(m-n)$. By Lemma 4.3.11,
$d({v},0)\leq\sum_{i=1}^{p_{l}}i+\sum_{i=1}^{m-p_{r}}i+\lfloor\frac{n(m+1)}{2}\rfloor.$
Since $h(v)\geq\eta_{n,m}=\frac{n+1}{2}$,
$p_{l}\leq\frac{m-n-1}{2}=\lfloor\frac{m-n}{2}\rfloor$ and
$p_{r}\geq\frac{m+n+1}{2}=\lceil\frac{m+n}{2}\rceil$. Therefore
$d(v,0)\leq\sum_{i=1}^{\lfloor\frac{m-n}{2}\rfloor}i+\sum_{i=1}^{m-\lceil\frac{m+n}{2}\rceil}i+\lfloor\frac{n(m+1)}{2}\rfloor=d^{1}_{n,m}\leq
d_{n,m}$. ∎

This concludes the proof of Theorem 4.0.1.

##  Chapter 5 The Diameter of $\mathrm{Y}_{n,m}$

In this chapter, we study the diameter of Yoke graphs. Since Yoke graphs
generalize already studied graphs, we first build upon a method used in order
to calculate the diameter of one of these graphs. Specifically, in [5],
similarities between arc permutation graphs and the Hasse diagram of the
dominance order on $P_{n}\times P_{2}^{n-2}$ were used in order to calculate
the diameter of arc permutation graphs. In Section 5.1, we generalize this
approach in order to calculate the diameter of $\mathrm{Y}_{n,m}$ in the case
$m\leq n$.

This approach fails for $n<m$. In Sections 5.2, 5.3 and 5.4, we present a new
approach that works for all instances of Yoke graphs. In the core of this
approach lies the idea to convert the problem of computation of diameter to
that of computation of eccentricity. Specifically, in Section 5.2, we
introduce dYoke graphs $\mathrm{Z}_{n,m}$. In Section 5.3, we show that the
diameter of $\mathrm{Y}_{n,m}$ is equal to the eccentricity of $0$ in
$\mathrm{Z}_{n,m}$. In Section 5.4, we compute the eccentricity of $0$ in
dYoke graphs and show that
$\operatorname{ecc}_{\mathrm{Z}_{n,m}}(0)=\operatorname{ecc}_{\mathrm{Y}_{n,m}}(0)$
and therefore
$\operatorname{diam}(\mathrm{Y}_{n,m})=\operatorname{ecc}_{\mathrm{Y}_{n,m}}(0)$
with an explicit formula for all values of $n$ and $m$.

###  5.1 Proof for $m\leq n$ via the Dominance Order

Recall the dominance order $\trianglelefteq$ in Definition 2.2.5 and recall
that we denote the set $\\{0,\dots,n-1\\}$ by $P_{n}$.

######  Observation 5.1.1.

$(P_{n}\times P_{2}^{m},\trianglelefteq)$ is a sublattice of
$(\mathbb{Z}^{m+1},\trianglelefteq)$.

###### Proof.

Let $\chi$ be the isomorphism in Observation 2.2.6 and let $L=\chi(P_{n}\times
P_{2}^{m})\subseteq(\mathbb{Z}^{m+1},\leq)$. Note that
$x=(x_{0},\dots,x_{m})\in L$ if and only if $0\leq x_{0}\leq n-1$ and
$x_{i}-x_{i-1}\in\\{0,1\\}$ for every $1\leq i\leq m$. $L$ is clearly closed
under the meet and join operations of $(\mathbb{Z}^{m+1},\leq)$. Therefore,
$L$ is a sublattice of $(\mathbb{Z}^{m+1},\leq)$. This proves that
$(P_{n}\times P_{2}^{m},\trianglelefteq)$ is a sublattice of
$(\mathbb{Z}^{m+1},\trianglelefteq)$. ∎

######  Definition 5.1.2.

Denote $\mathscr{H}(P_{n}\times P_{2}^{m},\trianglelefteq)$ (the Hasse diagram
of $(P_{n}\times P_{2}^{m},\trianglelefteq)$) by $\mathscr{H}_{n,m}$. Denote
the elements $(0,\dots,0)$ and $(n-1,1,\dots,1)$ in $P_{n}\times P_{2}^{m}$ by
$\hat{0}$ and $\hat{1}$, respectively.

Note that $\hat{0}$ and $\hat{1}$ are the minimum and maximum elements of
$(P_{n}\times P_{2}^{m},\trianglelefteq)$, respectively.

Recall that vertices in $\mathrm{Y}_{n,m}$ are determined by their first $m+1$
entries. Accordingly (and in accordance with Convention 3.1.2), we identify
vertices in $\mathrm{Y}_{n,m}$ with vertices in $\mathscr{H}_{n,m}$ by
ignoring the last entry, namely “forgetting” the right bucket of every vertex
in $\mathrm{Y}_{n,m}$.

If $m\leq 1$, then the diameter of $\mathrm{Y}_{n,m}$ is trivial by
Observation 3.1.3. Unless explicitly stated otherwise, we assume that $2\leq
m\leq n$ (in $\mathrm{Y}_{n,m}$, $\mathscr{H}_{n,m}$ and $P_{n}\times
P_{2}^{m}$) throughout this section.

######  Observation 5.1.3.

Let $x$ and $y$ be two elements in $P_{n}\times P_{2}^{m}$. Then $x\lessdot y$
in $(P_{n}\times P_{2}^{m},\trianglelefteq)$ if and only if $x\lessdot y$ in
$(\mathbb{Z}^{m+1},\trianglelefteq)$.

By Observations 2.2.7 and 5.1.3, the covering relation of $(P_{n}\times
P_{2}^{m},\trianglelefteq)$ is precisely the adjacency relation of
$\mathrm{Y}_{n,m}$ except for $2^{m-1}$ edges between every pair of vertices
of the form $(n-1,1,v_{2},\dots,v_{m})$ and $(0,0,v_{2},\dots,v_{m})$ in
$\mathrm{Y}_{n,m}$.

######  Observation 5.1.4.

$\mathrm{Y}_{n,m}$ is isomorphic to the graph obtained by taking
$\mathscr{H}_{n,m}$ and adding to it $2^{m-1}$ edges between every pair of
elements of the form $(n-1,1,v_{2},\dots,v_{m})$ and
$(0,0,v_{2},\dots,v_{m})$.

Recall the rank function $\operatorname{rank}_{\trianglelefteq}$ on
$(\mathbb{Z}^{n},\trianglelefteq)$ in Observation 2.2.8. By Observation 5.1.3,
it induces a rank function on $(P_{n}\times P_{2}^{m},\trianglelefteq)$: for
every $v=(v_{0},\dots,v_{m})\in P_{n}\times P_{2}^{m}$

$\operatorname{rank}_{\trianglelefteq}(v)=\sum_{i=0}^{m}\sum_{j=0}^{i}v_{j}.$

######  Observation 5.1.5.

If $u$ and $v$ are two elements in $P_{n}\times P_{2}^{m}$, then

$d_{\mathscr{H}_{n,m}}(u,v)=d_{\mathscr{H}(\mathbb{Z}^{m+1},\trianglelefteq)}(u,v).$

###### Proof.

The statement in this observation is implied by Theorem 2.2.4 and Observation
5.1.1. Specifically:

$d_{\mathscr{H}_{n,m}}(u,v)=d_{\mathscr{H}(\mathbb{Z}^{m+1},\trianglelefteq)}(u,v)=\operatorname{rank}_{\trianglelefteq}(u\vee
v)-\operatorname{rank}_{\trianglelefteq}(u\wedge v).$

∎

######  Lemma 5.1.6.

If $u$ and $v$ are a pair of incomparable elements in $(P_{n}\times
P_{2}^{m},\trianglelefteq)$, then

$d_{\mathscr{H}_{n,m}}(u,v)\leq 1+\binom{m}{2}.$

###### Proof.

Let $\chi$ be the isomorphism in Observation 2.2.6 and let
$x=(x_{0},\dots,x_{m})=\chi(u)$ and $y=(y_{0},\dots,y_{m})=\chi(v)$. Note that
$x$ and $y$ are incomparable in $(\mathbb{Z}^{m+1},\leq)$, since $u$ and $v$
are incomparable in $(P_{n}\times P_{2}^{m},\trianglelefteq)$. By Observation
5.1.5,
$d_{\mathscr{H}_{n,m}}(u,v)=d_{\mathscr{H}(\mathbb{Z}^{m+1},\leq)}(x,y)$. We
prove that $d_{\mathscr{H}(\mathbb{Z}^{m+1},\leq)}(x,y)\leq 1+\binom{m}{2}$.

Note that $z=(z_{0},\dots,z_{m})\in\chi(P_{n}\times P_{2}^{m})$ if and only if
$0\leq z_{0}\leq n-1$ and $z_{i}-z_{i-1}\in\\{0,1\\}$ for every $1\leq i\leq
m$. Therefore
$(x_{i+1}-y_{i+1})-(x_{i}-y_{i})=(x_{i+1}-x_{i})-(y_{i+1}-y_{i})\in\\{-1,0,1\\}$
for every $1\leq i\leq m$. Since $x$ and $y$ are incomparable, there exist
$0\leq j_{1},j_{2}\leq m$ such that $x_{j_{1}}-y_{j_{1}}<0$ and
$x_{j_{2}}-y_{j_{2}}>0$. This implies that there exists some $1\leq k\leq m-1$
such that $|x_{k}-y_{k}|=0$. Finally
$d_{\mathscr{H}(\mathbb{Z}^{m+1},\leq)}(x,y)=\sum_{i=0}^{m}|x_{i}-y_{i}|\leq
k+\dots+1+0+1+\dots+m-k=\binom{k+1}{2}+\binom{m-k+1}{2}\leq 1+\binom{m}{2}$.
The maximum is obtained for $k=1$ (or $k=m-1$). ∎

######  Lemma 5.1.7.

If $u,v$ are two elements in $P_{n}\times P_{2}^{m}$ such that
$|\operatorname{rank}_{\trianglelefteq}(v)-\operatorname{rank}_{\trianglelefteq}(u)|\leq\lfloor\frac{n(m+1)}{2}\rfloor$,
then
$d_{\mathrm{Y}_{n,m}}(u,v)\geq|\operatorname{rank}_{\trianglelefteq}(v)-\operatorname{rank}_{\trianglelefteq}(u)|$.

###### Proof.

If an edge $e=(x,y)$ in $\mathrm{Y}_{n,m}$ is also an edge in
$\mathscr{H}_{n,m}$, then, by Observation 5.1.3,
$|\operatorname{rank}_{\trianglelefteq}(x)-\operatorname{rank}_{\trianglelefteq}(y))|=1$.
Otherwise, by Observation 5.1.4, $e$ is one of the additional $2^{m-1}$ edges
in $\mathrm{Y}_{n,m}$ for which
$|\operatorname{rank}_{\trianglelefteq}(x)-\operatorname{rank}_{\trianglelefteq}(y)|$
is constant and is equal to $n(m+1)-1$. Therefore,
$\operatorname{rank}_{\trianglelefteq}(x)$ changes by $\pm 1$ modulo $n(m+1)$
along every edge in $\mathrm{Y}_{n,m}$. This implies the claim of this lemma.
∎

######  Corollary 5.1.8.

Every saturated chain of length smaller or equal to
$\lfloor\frac{n(m+1)}{2}\rfloor$ in $(P_{n}\times P_{2}^{m},\trianglelefteq)$
is a geodesic in $\mathrm{Y}_{n,m}$.

Saturated chains of length $\lfloor\frac{n(m+1)}{2}\rfloor$ exist in
$\mathrm{Y}_{n,m}$, since
$\operatorname{rank}_{\trianglelefteq}(\hat{1})\geq\lfloor\frac{n(m+1)}{2}\rfloor$
for any $n$ and $m$.

######  Corollary 5.1.9.

$diam(\mathrm{Y}_{n,m})\geq\lfloor\frac{n(m+1)}{2}\rfloor$.

In the rest of this section, we show that $\lfloor\frac{n(m+1)}{2}\rfloor$ is
also an upper bound on the diameter of $\mathrm{Y}_{n,m}$, for $n\geq m$.

######  Definition 5.1.10.

Let $u_{0}=(n-1,1,0,\dots,0)$ and $u_{1}=(0,0,1,\dots,1)$ in $P_{n}\times
P_{2}^{m}$.

  1. 1.

Denote the interval $[\hat{0},u_{0}]\subseteq(P_{n}\times
P_{2}^{m},\trianglelefteq)$ by $I_{0}$. Denote by $\mathrm{Y}_{n,m}^{0}$ the
subgraph induced by $I_{0}$ (in $\mathrm{Y}_{n,m}$).

  2. 2.

Denote the interval $[u_{1},\hat{1}]\subseteq(P_{n}\times
P_{2}^{m},\trianglelefteq)$ by $I_{1}$. Denote by $\mathrm{Y}_{n,m}^{1}$ the
subgraph induced by $I_{1}$ (in $\mathrm{Y}_{n,m}$).

######  Observation 5.1.11.

The elements in $I_{0}$ and $I_{1}$ can be characterized as follows.

  1. 1.

$I_{0}=\\{v\in P_{n}\times P_{2}^{m}:\sum_{i=0}^{m}v_{i}\leq n\\}$.

  2. 2.

$I_{1}=\\{v\in P_{n}\times P_{2}^{m}:\sum_{i=0}^{m}v_{i}\geq m-1\\}$.

Therefore, the following is true (since $m\leq n$).

  1. 1.

$I_{0}\cup I_{1}=P_{n}\times P_{2}^{m}$.

  2. 2.

$I_{0}\cap I_{1}=\\{v\in\mathrm{Y}_{n,m}:m-1\leq\sum_{i=0}^{m}v_{i}\leq
n\\}=[u_{1},u_{0}]$.

######  Definition 5.1.12.

Let $\varphi$ and $\tau$ be the following two maps from $\mathrm{Y}_{n,m}$ to
$\mathrm{Y}_{n,m}$:

$\begin{array}[]{c c c
l}&\varphi(v_{0},v_{1},\dots,v_{m})&=&(v_{0}+1,v_{1},\dots,v_{m})\\\
&\tau(v_{0},v_{1},\dots,v_{m})&=&(-v_{0},1-v_{1},\dots,1-v_{m})\\\
\end{array}$

It is straightforward to verify that $\varphi$ and $\tau$ are automorphisms of
$\mathrm{Y}_{n,m}$.

######  Lemma 5.1.13.

$\mathrm{Y}_{n,m}^{0}$ and $\mathrm{Y}_{n,m}^{1}$ are isomorphic as graphs.

###### Proof.

Let $\tau$ and $\varphi$ be the automorphisms of $\mathrm{Y}_{n,m}$ in
Definition 5.1.12 and let $f=\tau\varphi$. Note that $f$ is involutive. We
show that both $f(\mathrm{Y}_{n,m}^{0})\subseteq\mathrm{Y}_{n,m}^{1}$ and
$f(\mathrm{Y}_{n,m}^{1})\subseteq\mathrm{Y}_{n,m}^{0}$. This implies that $f$
is a graph isomorphism between $\mathrm{Y}_{n,m}^{0}$ and
$\mathrm{Y}_{n,m}^{1}$.

Let $x\in\mathrm{Y}_{n,m}$ and let $y=f(x)$. Assume that $x_{0}=t$ and
$\sum_{i=1}^{m}x_{i}=k$. Then $y_{0}=n-t-1$ and $\sum_{i=1}^{m}y_{i}=m-k$.
Therefore $\sum_{i=0}^{m}y_{i}=n+m-1-(t+k)$.

By Observation 5.1.11, if $x\in\mathrm{Y}_{n,m}^{0}$, then $t+k\leq n$.
Therefore, $\sum_{i=0}^{m}y_{i}=n+m-1-(t+k)\geq m-1$ and
$y\in\mathrm{Y}_{n,m}^{1}$. Similarly, if $x\in\mathrm{Y}_{n,m}^{1}$, then
$t+k\geq m-1$. Therefore, $\sum_{i=0}^{m}y_{i}=n+m-1-(t+k)\leq n$ and
$y\in\mathrm{Y}_{n,m}^{0}$. ∎

######  Lemma 5.1.14.

$\operatorname{diam}(\mathrm{Y}_{n,m}^{0})=\operatorname{diam}(\mathrm{Y}_{n,m}^{1})=\big{\lfloor}\frac{n(m+1)}{2}\big{\rfloor}.$

###### Proof.

By Lemma 5.1.13, it is sufficient to prove that
$\operatorname{diam}(\mathrm{Y}_{n,m}^{0})=\lfloor\frac{n(m+1)}{2}\rfloor.$
Let $u$ and $v$ be a pair of vertices in $\mathrm{Y}_{n,m}^{0}$. Since
$\operatorname{rank}_{\trianglelefteq}(u_{0})=n(m+1)-1\geq\big{\lfloor}\frac{n(m+1)}{2}\big{\rfloor}$,
$I_{0}$ contains saturated chains of length
$\big{\lfloor}\frac{n(m+1)}{2}\big{\rfloor}$. Therefore, by Corollary 5.1.8,
it is sufficient to show that
$d_{\mathrm{Y}_{n,m}^{0}}(u,v)\leq\lfloor\frac{n(m+1)}{2}\rfloor$. By Lemma
5.1.6, we can assume that $u$ and $v$ are comparable, since $n\geq m$.
Therefore, there exists a saturated chain $A$ in $I_{0}$ between $0$ and
$u_{0}$ containing both $u$ and $v$.
$\operatorname{len}(A)=\operatorname{rank}_{\trianglelefteq}(u_{0})=n(m+1)-1$.
There is an edge in $\mathrm{Y}_{n,m}^{0}$ connecting $0$ and $u_{0}$. It
completes $A$ to a cycle $C$ of length $n(m+1)$. This proves that
$d_{\mathrm{Y}_{n,m}^{0}}(u,v)\leq
d_{C}(u,v)\leq\lfloor\frac{n(m+1)}{2}\rfloor$. ∎

######  Theorem 5.1.15.

If $0\leq m\leq n$, then

$\operatorname{diam}(\mathrm{Y}_{n,m})=\big{\lfloor}\frac{n(m+1)}{2}\big{\rfloor}.$

###### Proof.

If $m\leq 1$, then this theorem is trivial by Observation 3.1.3. Assume that
$2\leq m\leq n$.

By Corollary 5.1.9, it is sufficient to prove that
$diam(\mathrm{Y}_{n,m})\leq\lfloor\frac{n(m+1)}{2}\rfloor$. Let
$u,v\in\mathrm{Y}_{n,m}$. By Observation 5.1.11, $I_{0}\cup I_{1}=P_{n}\times
P_{2}^{m}$. If both $u$ and $v$ are in the same interval, say $I_{0}$, then by
Lemma 5.1.14, $d_{\mathrm{Y}_{n,m}}(u,v)\leq
d_{\mathrm{Y}_{n,m}^{0}}(u,v)\leq\lfloor\frac{n(m+1)}{2}\rfloor$. Otherwise,
assume without loss of generality that $u\in I_{1}$ and $v\in I_{0}\setminus
I_{1}$. By Observation 5.1.11, $I_{0}\setminus
I_{1}=\\{v\in\mathrm{Y}_{n,m}:\sum_{i=0}^{m}v_{i}\leq m-2\\}$. It is
sufficient to show that $v$ can be mapped into $I_{0}\cap I_{1}$ via an
automorphism of $\mathrm{Y}_{n,m}$.

Let $\varphi$ be the automorphism of $\mathrm{Y}_{n,m}$ in Definition 5.1.12.
Note that if $v_{0}\neq 0$, then $\varphi^{-1}(v)$ is still in $I_{0}\setminus
I_{1}$. Therefore, we can assume that $v_{0}=0$. Let
$c=(m-1)-\sum_{i=0}^{m}v_{i}$ and let $v^{\prime}=\varphi^{c}(v)$. Note that
$1\leq c\leq m-1\leq n-1$, since $\sum_{i=0}^{m}v_{i}\leq m-2$. Therefore,
$v^{\prime}_{0}=c$ and $\sum_{i=0}^{m}v^{\prime}_{i}=m-1$. This proves, by
Observation 5.1.11, that $\varphi^{c}(v)\in I_{0}\cap I_{1}$ as required. ∎

The above line of proof fails for $n<m$. We therefore pursue a new, totally
different approach, which works for all values of $n$ and $m$.

###  5.2 The dYoke Graphs $\mathrm{Z}_{n,m}$

As noted in the introduction of this thesis, at the heart of our approach to
the calculation of the diameter of $\mathrm{Y}_{n,m}$ lies the idea of
converting the diameter problem of one graph into an eccentricity problem of
another graph. To this end, we introduce a new family of graphs.

######  Definition 5.2.1.

Let $n\geq 1$ and $m\geq 0$ be two integers. Denote the subset
$\\{-1,0,1\\}\subseteq\mathbb{Z}$ by $Q_{3}$. The dYoke graph
$\mathrm{Z}_{n,m}$ is a graph with vertices corresponding to all
$u=(u_{0}\dots,u_{m+1})\in\mathbb{Z}_{n}\times Q_{3}^{m}\times\mathbb{Z}_{n}$
such that $\sum_{i=0}^{m+1}u_{i}\equiv 0(\bmod n).$ Two vertices $u$ and $v$
are adjacent in $\mathrm{Z}_{n,m}$ if there exists $0\leq i\leq m$ such that
$u_{j}=v_{j}$ for every $j\notin\\{i,i+1\\}$ and one of the following two
cases holds: either $u_{i}=v_{i}+1$ and $u_{i+1}=v_{i+1}-1$, or
$u_{i}=v_{i}-1$ and $u_{i+1}=v_{i+1}+1$.

As with Yoke graphs, we refer to the entries $u_{0}$ and $u_{m+1}$ of a vertex
$u$ in $\mathrm{Z}_{n,m}$ as buckets; and Convention 3.1.2 applies to dYoke
graphs as well, so that the sum $\sum_{i=0}^{m+1}u_{i}$ in Definition 5.2.1 is
an integer.

Note that, as with Yoke graphs, a vertex $u$ in $\mathrm{Z}_{n,m}$ is
determined by its first (or last) $m+1$ entries, since
$\sum_{i=0}^{m+1}u_{i}\equiv 0(\bmod n)$. We denote the vertex
$(0,\dots,0)\in\mathrm{Z}_{n,m}$ by $0$. In the first case of the adjacency
relation, where $u_{i}=v_{i}+1$ and $u_{i+1}=v_{i+1}-1$ for some $0\leq i\leq
m$, we say that $u$ is obtained from $v$ by shifting a unit from entry $i+1$
to the left, and write $u=\overleftarrow{s}_{i}(v)$. In the second case, where
$u_{i}=v_{i}-1$ and $u_{i+1}=v_{i+1}+1$, we say that $u$ is obtained from $v$
by shifting a unit from entry $i$ to the right, and write
$u=\overrightarrow{s}_{i}(v)$. When $v_{0}=0$ ($v_{m+1}=0$), we say that the
left (right) bucket is empty.

For example, if $v=(3,0,-1,1,2)\in\mathrm{Z}_{5,3}$, then
$\overleftarrow{s}_{2}(v)=(3,0,0,0,2)$ and
$\overrightarrow{s}_{1}(v)=(3,-1,0,1,2)$. If $i<j$, we say that $v_{j}$ is an
entry to the right of $v_{i}$ and that $v_{i}$ is an entry to the left of
$v_{j}$. For convenience, we write $s_{i}$ to indicate a unit shift between
the entries indexed by $i$ and $i+1$ without specifying its direction.

Note, that if $m>0$, $1\leq k\leq m$ and $v_{k}=-1$, then a unit shift from
entry $k$ of $v$ is not possible. Similarly, if $v_{k}=1$, then a unit shift
to entry $k$ of $v$ not possible. Nevertheless, for every $0\leq i\leq m$,
$\overleftarrow{s}_{i}$ and $\overrightarrow{s}_{i}$ induce functions from
$\mathrm{Z}_{n,m}$ to $\mathrm{Z}_{n,m}$, in which if a unit shift $s_{i}(v)$
is not possible for some $v\in\mathrm{Z}_{n,m}$, then $v$ is a fixed point of
$s_{i}$. Denote the set $\\{\overleftarrow{s}_{i},\overrightarrow{s}_{i}:0\leq
i\leq m\\}$ by $\mathcal{F}_{n,m}$. If $m=0$, then $\overleftarrow{s}_{0}$ and
$\overrightarrow{s}_{0}$ are inverses of each other and $\mathcal{F}_{n,0}$
generates the cyclic group $\mathbb{Z}_{n}$. If $m>0$, then none of the
functions in $\mathcal{F}_{n,m}$ are bijective and $\mathcal{F}_{n,m}$
generates a semigroup.

A word in the letters $\mathcal{F}_{n,m}$ is a sequence $f_{d}\cdots f_{1}$
where $f_{1},\dots,f_{d}\in\mathcal{F}_{n,m}$. Let $P$ be a path
$(v=v^{0}\sim\dots\sim v^{d}=u)$ in $\mathrm{Z}_{n,m}$. Clearly, there is a
unique word $f_{d}\cdots f_{1}$ such that $f_{t}(v^{t-1})=v^{t}$ for every
$1\leq t\leq d$ or, equivalently, $f_{t}\cdots f_{1}(v)=v^{t}$ for every
$1\leq t\leq d$. We say that $f_{d}\cdots f_{1}$ is the word corresponding to
the path $P$ from $v$ to $u$ (or the path $P$ starting at $v$).

Note that a word $f_{d}\cdots f_{1}$ does not correspond to a path starting at
$v$ if $f_{t}\cdots f_{1}(v)=f_{t+1}f_{t}\cdots f_{1}(v)$ for some $1\leq
t\leq d-1$. For example, the word $\overleftarrow{s_{1}}\overleftarrow{s_{0}}$
corresponds to the path $(v=(0,1,1,1)\sim(1,0,1,1)\sim(1,1,0,1))$ in
$\mathrm{Z}_{3,2}$ starting at $v$. However,
$\overleftarrow{s_{0}}\overleftarrow{s_{1}}$ does not correspond to a path
starting at $v$, since $v$ is a fixed point of $\overleftarrow{s_{1}}$.

Let $f_{d}\cdots f_{1}$ be the word corresponding to a path from $v$ to $u$
and let $1\leq t\leq d-1$. If $f_{d}\cdots f_{t}f_{t+1}\cdots f_{1}$ (changing
the order of $f_{t}$ and $f_{t+1}$) is also a word corresponding to a path
from $v$ to $u$, then we say that $f_{t}$ and $f_{t+1}$ relatively commute in
(the path) $f_{d}\cdots f_{1}(v)$. Note that the fact that $f_{t}$ and
$f_{t+1}$ relatively commute in $f_{d}\cdots f_{1}(v)$, does not imply that
$f_{t}$ and $f_{t+1}$ commute (as functions from the set of vertices of
$\mathrm{Z}_{n,m}$ to itself). For example, if $f_{d}\cdots f_{1}$ corresponds
to a path from $v$ to $u$ such that $f_{t}=\overrightarrow{s}_{i}$ and
$f_{t+1}=\overleftarrow{s}_{i+1}$ for some $1\leq t\leq d-1$ and $0\leq i\leq
m-1$, then $f_{t}$ and $f_{t+1}$ relatively commute in $f_{d}\cdots f_{1}(v)$
but do not commute (as functions). If, however, $f_{t}$ and $f_{t+1}$ commute,
then they also relatively commute in $f_{d}\cdots f_{1}(v)$. Clearly, two
distinct $s_{i}$ and $s_{j}$ in $\mathcal{F}_{n,m}$ commute if and only if
$|i-j|>1$.

######  Lemma 5.2.2 (Shift Direction Lemma).

Let $f_{d}\cdots f_{1}$ be the word corresponding to a geodesic in
$\mathrm{Z}_{n,m}$. For every $0\leq i\leq m$, all of the instances of $s_{i}$
in $f_{d}\cdots f_{1}$ shift in the same direction.

###### Proof.

Let $v$ and $u$ be two vertices in $\mathrm{Z}_{n,m}$. If $m=0$, then a word
corresponding to a geodesic from $v$ to $u$ is of the form $f^{k}$ where
$f\in\mathcal{F}_{n,0}$ and $0\leq k\leq\lfloor\frac{n}{2}\rfloor$. Assume
that $m>0$ and assume to the contrary that there exist words corresponding to
geodesics from $v$ to $u$ not satisfying the lemma. Denote the set of such
words by $\mathcal{W}$. For every word $f_{d}\cdots f_{1}$ in $\mathcal{W}$,
there exist $0\leq i\leq m$ and $1\leq t_{1},t_{2}\leq d$ such that
$f_{t_{1}}=\overrightarrow{s}_{i}$ and $f_{t_{2}}=\overleftarrow{s}_{i}$. Let
$w=f_{d}\cdots f_{1}$ be a word in $\mathcal{W}$ in which
$\min\\{|t_{2}-t_{1}|:f_{t_{1}}=\overrightarrow{s}_{i},f_{t_{2}}=\overleftarrow{s}_{i}\\}$
is minimal. Assume without loss of generality that $t_{1}<t_{2}$.

If $t_{2}=t_{1}+1$, then the word obtained by deleting both $f_{t_{1}}$ and
$f_{t_{2}}$ from $f_{d}\cdots f_{1}$ is a word corresponding to a shorter path
from $v$ to $u$, contradicting the minimality of $d$. Therefore, we can assume
that $t_{2}-t_{1}>1$.

If $f_{t_{1}+1}=s_{j}$ for some $0\leq j\leq m$ such that $|i-j|>1$, then
$f_{t_{1}}$ and $f_{t_{1}+1}$ commute as functions. If
$f_{t_{1}+1}\in\\{\overleftarrow{s}_{i-1},\overleftarrow{s}_{i+1}\\}$, then
$f_{t_{1}}$ and $f_{t_{1}+1}$ relatively commute in $f_{d}\cdots f_{1}(v)$. In
both cases, the word obtained by interchanging $f_{t_{1}}$ and $f_{t_{1}+1}$
in $w$ corresponds to a path from $v$ to $u$. This contradicts the minimality
of $t_{2}-t_{1}$ in the choice of $w$. Therefore,
$f_{t_{1}+1}\in\\{\overrightarrow{s}_{i-1},\overrightarrow{s}_{i+1}\\}$.

Let $v^{\prime}=f_{t_{1}+1}\cdots f_{1}(v)$. If
$f_{t_{1}+1}=\overrightarrow{s}_{i-1}$, then $v^{\prime}_{i}=1$ (otherwise
$f_{t_{1}}$ and $f_{t_{1}+1}$ relatively commute in $f_{d}\cdots f_{1}(v)$).
Since $f_{t_{2}}=\overleftarrow{s}_{i}$, there must exist some
$t_{1}+1<k<t_{2}$ such that $f_{k}=\overleftarrow{s}_{i-1}$ or
$f_{k}=\overrightarrow{s}_{i}$. Similarly, if
$f_{t_{1}+1}=\overrightarrow{s}_{i+1}$, then $v^{\prime}_{i+1}=-1$ and there
must exist some $t_{1}+1<k<t_{2}$ such that $f_{k}=\overleftarrow{s}_{i+1}$ or
$f_{k}=\overrightarrow{s}_{i}$. All of the cases contradict the minimality of
$t_{2}-t_{1}$. ∎

###  5.3 From Diameter to Eccentricity

In this section, we show (Theorem 5.3.5) that the diameter of
$\mathrm{Y}_{n,m}$ is equal to the eccentricity of $0$ in $\mathrm{Z}_{n,m}$.
Every Yoke graph $\mathrm{Y}_{n,m}$ is naturally embedded in the dYoke graph
$\mathrm{Z}_{n,m}$ as an induced subgraph on the vertices with no negative
entries. Note that for every two vertices $v,u\in\mathrm{Y}_{n,m}$, the
difference $v-u=(v_{0}-u_{0},v_{1}-u_{1},\dots,v_{m+1}-u_{m+1})$ is in
$\mathrm{Z}_{n,m}$.

######  Definition 5.3.1.

For every $u\in\mathrm{Y}_{n,m}$ let
$\varphi_{u}:\mathrm{Y}_{n,m}\rightarrow\mathrm{Z}_{n,m}$ be the map (on
vertices) defined by $\varphi_{u}(v)=v-u$.

######  Observation 5.3.2.

For every $u\in\mathrm{Y}_{n,m}$, $\varphi_{u}$ is a graph isomorphism between
$\mathrm{Y}_{n,m}$ and the subgraph induced by $\varphi_{u}(\mathrm{Y}_{n,m})$
(in $\mathrm{Z}_{n,m}$).

The following lemma is essential for the proof of Lemma 5.3.4. We start with a
given $z\in\mathrm{Z}_{n,m}$ such that $z_{i}=0$ for some $1\leq i\leq m$, and
a geodesic $P$ between $z$ and $0$. We show that $P$ can be transformed into a
geodesic $P^{\prime}$ in which the $i$th entry is either non-negative or non-
positive along the path. We can do this without changing the sets of values of
other entries.

######  Lemma 5.3.3.

Let $z\in\mathrm{Z}_{n,m}$ such that $z_{i}=0$ for some $1\leq i\leq m$ and
let $P=(z=x^{0}\sim x^{1}\sim\dots\sim x^{d}=0)$ be a geodesic between $z$ and
$0$. Then a geodesic $P^{\prime}=(z=y^{0}\sim y^{1}\sim\dots\sim y^{d}=0)$
exists such that:

  1. 1.

either $y^{t}_{i}\leq 0$ for every $0\leq t\leq d$ or $y^{t}_{i}\geq 0$ for
every $0\leq t\leq d$ ($P^{\prime}$ can be constructed either way);

  2. 2.

$\\{y^{t}_{j}:0\leq t\leq d\\}=\\{x^{t}_{j}:0\leq t\leq d\\}$ for every $j\neq
i$ where $0\leq j\leq m+1$.

###### Proof.

We prove the existence of $P^{\prime}$ such that $y^{t}_{i}\leq 0$ for every
$0\leq t\leq d$. The proof for the case $y^{t}_{i}\geq 0$ follows by symmetric
arguments. Let $Q=(w^{0}\sim w^{1}\sim\dots\sim w^{l})$ be a path in
$\mathrm{Z}_{n,m}$. Define $O_{i}(Q)=|\\{0\leq t\leq l:w^{t}_{i}=1\\}|$. If
$O_{i}(P)=0$, then set $P^{\prime}=P$. Otherwise, assume that $O_{i}(P)>0$. We
show that there exists a geodesic $Q=(z=w^{0}\sim w^{1}\sim\dots\sim w^{d}=0)$
with the following properties:

  1. (1)

$O_{i}(Q)<O_{i}(P)$.

  2. (2)

$\\{w^{t}_{j}:0\leq t\leq d\\}=\\{x^{t}_{j}:0\leq t\leq d\\}$ for every $j\neq
i$ where $0\leq j\leq m+1$.

Note that if $O_{i}(Q)>0$, then the process can be repeated implying the
existence of $P^{\prime}$, as required.

Let $f_{d}\cdots f_{1}$ be the word corresponding to $P$. Note that by the
Shift Direction Lemma 5.2.2, either both $\overrightarrow{s}_{i-1}$ and
$\overrightarrow{s}_{i}$ or both $\overleftarrow{s}_{i-1}$ and
$\overleftarrow{s}_{i}$ appear in $f_{d}\cdots f_{1}$, since $x^{0}_{i}=0$,
$x^{d}_{i}=0$ and $O_{i}(P)>0$. Assume without loss of generality that both
$\overrightarrow{s}_{i-1}$ and $\overrightarrow{s}_{i}$ appear in $f_{d}\cdots
f_{1}$.

Let $t_{1}$ be the minimal index such that $x^{t_{1}}_{i}=1$ and therefore
$f_{t_{1}}=\overrightarrow{s}_{i-1}$. Let $t_{2}$ be the minimal index such
that $t_{1}<t_{2}$ and $f_{t_{2}}=\overrightarrow{s}_{i}$ (such $t_{2}$ exists
since $x^{d}_{i}=0$). If $t_{2}-t_{1}=1$, then $f_{t_{1}}$ and $f_{t_{2}}$
relatively commute in $f_{d}\cdots f_{1}(z)$, and the path $Q$ obtained by
interchanging $f_{t_{1}}$ and $f_{t_{2}}$ satisfies properties (1) and (2) as
required. In the rest of this proof, we assume that $t_{2}-t_{1}>1$.

We can assume that $f_{d}\cdots f_{1}$ is in the form

$(*)\;\;f_{d}\dots f_{t_{2}}w_{2}w_{1}f_{t_{1}}\dots f_{1}$

where $w_{1}$ and $w_{2}$ are words (at least one of which is nonempty) such
that every letter in $w_{1}$ shifts a unit between entries to the right of
$i$, and every letter in $w_{2}$ shifts a unit between entries to the left of
$i$. Indeed, if there exist $t_{1}<t<t+1<t_{2}$ such that $f_{t}$ shifts a
unit between entries to the left of $i$ and $f_{t+1}$ shifts a unit between
entries to the right of $i$, then $f_{t}$ and $f_{t+1}$ commute and the word
obtained by interchanging $f_{t}$ and $f_{t+1}$ corresponds to a path between
$z$ and $0$ which satisfies property (2), and which does not change
$O_{i}(P)$. By repeatedly interchanging such pairs, we obtain a word in the
form $(*)$, since
$f_{t}\notin\\{\overrightarrow{s}_{i-1},\overrightarrow{s}_{i}\\}$ for every
$t_{1}<t<t_{2}$.

Note that $f_{t_{1}}$ commutes with every letter in $w_{1}$ and $f_{t_{2}}$
commutes with every letter in $w_{2}$. Therefore, $f_{d}\dots
w_{2}f_{t_{1}}f_{t_{2}}w_{1}\dots f_{1}$ corresponds to a path $Q$ between $z$
and $0$ satisfying properties (1) and (2), similarly to the case
$t_{2}-t_{1}=1$. ∎

######  Lemma 5.3.4.

Let $v,u\in\mathrm{Y}_{n,m}$. Then

$d_{\mathrm{Y}_{n,m}}(v,u)=d_{\mathrm{Z}_{n,m}}(v-u,0).$

###### Proof.

By Observation 5.3.2, $\mathrm{Y}_{n,m}$ is isomorphic to the subgraph induced
by $\varphi_{u}(\mathrm{Y}_{n,m})$ in $\mathrm{Z}_{n,m}$, implying that
$d_{\mathrm{Y}_{n,m}}(v,u)\geq
d_{\mathrm{Z}_{n,m}}(\varphi_{u}(v),\varphi_{u}(u))=d_{\mathrm{Z}_{n,m}}(v-u,0)$.

Conversely, let $P=(v-u=x^{0}\sim x^{1}\sim\dots\sim x^{d}=0)$ be a geodesic
from $v-u$ to $0$ in $\mathrm{Z}_{n,m}$. Note that if $x^{0}_{i}\leq 0$ for
some $1\leq i\leq m$, then, by Lemma 5.3.3, there exists a geodesic
$P^{\prime}=(v-u=y^{0}\sim y^{1}\sim\dots\sim y^{d}=0)$ such that
$y^{t}_{i}\leq 0$ for every $0\leq t\leq d$ (the lemma is applied to
$(x^{k}\sim x^{k+1}\sim\dots\sim x^{d}=0)$, where $k$ is the first index such
that $x^{k}_{i}=0$). Similarly, if $x^{0}_{i}\geq 0$ for some $1\leq i\leq m$,
then there exists a geodesic $P^{\prime}=(v-u=y^{0}\sim y^{1}\sim\dots\sim
y^{d}=0)$ such that $y^{t}_{i}\geq 0$ for every $0\leq t\leq d$.

Therefore, by its second property, Lemma 5.3.3 can be applied iteratively to
all $1\leq i\leq m$, to construct a geodesic $P^{\prime}=(v-u=y^{0}\sim
y^{1}\sim\dots\sim y^{d}=0)$ from the geodesic $P$ that satisfies the
following conditions for every $1\leq i\leq m$:

  1. 1.

If $u_{i}=1$ (implying that $(v-u)_{i}\leq 0$), then $y^{t}_{i}\leq 0$ for
every $0\leq t\leq d$.

  2. 2.

If $u_{i}=0$ (implying that $(v-u)_{i}\geq 0$), then $y^{t}_{i}\geq 0$ for
every $0\leq t\leq d$.

Clearly, $(v=y^{0}+u\sim y^{1}+u\sim\dots\sim y^{d}+u=u)$ is a path between
$v$ and $u$ in $\mathrm{Y}_{n,m}$. Therefore $d_{\mathrm{Y}_{n,m}}(v,u)\leq
d_{\mathrm{Z}_{n,m}}(v-u,0)$. ∎

######  Theorem 5.3.5.

$\operatorname{diam}(\mathrm{Y}_{n,m})=\operatorname{ecc}_{\mathrm{Z}_{n,m}}(0)$.

###### Proof.

By Lemma 5.3.4,
$d_{\mathrm{Y}_{n,m}}(v,u)=d_{\mathrm{Z}_{n,m}}(v-u,0)\leq\operatorname{ecc}_{\mathrm{Z}_{n,m}}(0)$
for each pair of vertices $v$ and $u$ in $\mathrm{Y}_{n,m}$. Therefore,
$\operatorname{diam}(\mathrm{Y}_{n,m})\leq\operatorname{ecc}_{\mathrm{Z}_{n,m}}(0)$.
On the other hand, for every $z\in\mathrm{Z}_{n,m}$ there exist
$v,u\in\mathrm{Y}_{n,m}$ such that $v-u=z$. By Lemma 5.3.4,
$d_{\mathrm{Z}_{n,m}}(z,0)=d_{\mathrm{Z}_{n,m}}(v-u,0)=d_{\mathrm{Y}_{n,m}}(v,u)\leq\operatorname{diam}(\mathrm{Y}_{n,m})$,
and therefore
$\operatorname{ecc}_{\mathrm{Z}_{n,m}}(0)\leq\operatorname{diam}(\mathrm{Y}_{n,m})$.
This proves equality. ∎

###  5.4 The Eccentricity of $0$ in $\mathrm{Z}_{n,m}$

In this section, we compute the eccentricity of $0$ in $\mathrm{Z}_{n,m}$
(Theorem 5.4.33). It turns out to be equal to the eccentricity of $0$ in
$\mathrm{Y}_{n,m}$ as it appears in Theorem 4.0.1. By Theorem 5.3.5, it is
also equal to the diameter of $\mathrm{Y}_{n,m}$.

In Subsection 5.4.1, we study pivot paths and some related concepts. Note that
many of the definitions that appear in this section are similar to the ones in
Chapter 4, where these notions were applied to compute the eccentricity of $0$
in Yoke graphs. Here, these definitions are applied to dYoke graphs and the
proofs are slightly more complex due to the richer structure of dYoke graphs.
In Subsection 5.4.2, we compute the eccentricity of $0$ in $\mathrm{Z}_{n,m}$.

######  Observation 5.4.1.

If $m=0$, then $\mathrm{Z}_{n,0}$ is a cycle graph on $n$ vertices. Therefore,
$\operatorname{ecc}_{\mathrm{Z}_{n,0}}(0)=\lfloor\frac{n}{2}\rfloor=\lfloor\frac{n(m+1)}{2}\rfloor$.

In the rest of this section, unless explicitly stated otherwise, we assume
that $m>0$.

####  5.4.1 Pivots and Walls

######  Definition 5.4.2 (Pivot).

A pivot of a vertex $v\in\mathrm{Z}_{n,m}$ is an integer $-1\leq p\leq m+1$
such that $\sum_{i=0}^{p}v_{i}$ is divisible by $n$. We call $-1$ and $m+1$
the outer pivots of $v$; they are pivots of every $v\in\mathrm{Z}_{n,m}$.
Every other pivot, if it exists, is called an inner pivot. Denote the set of
pivots of $v$ by $\operatorname{Piv}(v)$.

For example, in $\mathrm{Z}_{3,8}$,
$\operatorname{Piv}((0,1,-1,0,1,1,-1,-1,1,2))=\\{-1,0,2,3,7,9\\}$.

######  Definition 5.4.3 (Wall).

Let $P$ be a path from $v$ to $0$ in $\mathrm{Z}_{n,m}$ and let $f_{d}\cdots
f_{1}$ be the word corresponding to $P$. An inner wall of $P$ is an integer
$0\leq p\leq m$ such that $s_{p}$ does not appear in $f_{d}\cdots f_{1}$. $-1$
is a left outer wall of $P$ if $\overleftarrow{s}_{0}$ does not appear in
$f_{d}\cdots f_{1}$. Similarly, $m+1$ is a right outer wall of $P$ if
$\overrightarrow{s}_{m}$ does not appear in $f_{d}\cdots f_{1}$. Finally, we
say that $-1\leq p\leq m+1$ is a wall of $P$ if it is either an inner wall or
an outer wall of $P$.

Clearly, paths from $v$ to $0$ with a wall $p$ exist if and only if $p$ is a
pivot of $v$.

######  Definition 5.4.4 (Pivot Path).

Let $p$ be a pivot of a vertex $v$ in $\mathrm{Z}_{n,m}$. We say that a path
$P$ from $v$ to $0$ is a $p$-pivot path of $v$, if $P$ is shortest among the
paths from $v$ to $0$ with a wall $p$. Denote the length of a $p$-pivot path
of $v$ by $\sigma_{p}(v)$. We say that $P$ is a pivot path, if it is a
$p$-pivot path for some $p$.

For example, let $v=(1,0,-1,-1,1)$ in $\mathrm{Z}_{3,3}$. Then
$\overleftarrow{s}_{3}\overrightarrow{s}_{0}\overrightarrow{s}_{1}$ is a word
corresponding to a $2$-pivot path $P$ of $v$:
$P=(v=(1,0,-1\,\|-1,1)\sim(1,-1,0\,\|-1,1)\sim(0,0,0\,\|-1,1)\sim(0,0,0\,\|\,0,0)=0)$
where we added the symbol $\|$ to visualize the wall $2$ of $P$.

######  Lemma 5.4.5.

Every geodesic in $\mathrm{Z}_{n,m}$ ending at $0$ is a pivot path (namely,
has a wall).

###### Proof.

Let $w=f_{d}\cdots f_{1}$ be the word corresponding to a geodesic $P$ in
$\mathrm{Z}_{n,m}$ from $v$ to $0$. Assume to the contrary that $P$ has no
walls. Therefore, both $\overleftarrow{s}_{0}$ and $\overrightarrow{s}_{m}$
appear in $w$ (since $P$ has no outer walls). By the Shift Direction Lemma
5.2.2, and since $P$ has no walls, exactly one of
$\\{\overleftarrow{s}_{i},\overrightarrow{s}_{i}\\}$ appears in $w$ (at least
once) for every $0\leq i\leq m$. Let $1\leq i\leq m$ be minimal such that
$\overrightarrow{s}_{i}$ appears in $w$. Then both $\overleftarrow{s}_{i-1}$
and $\overrightarrow{s}_{i}$ appear in $w$. This is a contradiction, since it
implies that, throughout $P$, at least two units are shifted from the entry
$v_{i}$ and no units are shifted to $v_{i}$. ∎

######  Observation 5.4.6.

By Lemma 5.4.5,

$\operatorname{ecc}_{\mathrm{Z}_{n,m}}(0)=\max_{v}d(v,0)=\max_{v}\min_{p}\sigma_{p}(v).$

######  Definition 5.4.7.

Let $v\in\mathrm{Z}_{n,m}$ and $p\in\operatorname{Piv}(v)$. If (one,
equivalently all) $p$-pivot paths of $v$ are also geodesics between $v$ and
$0$, then we say that $p$ is a geodesic pivot of $v$.

The Shift Direction Lemma 5.2.2 deals with geodesics, or equivalently (by
Lemma 5.4.5) with $p$-pivot paths for geodesic pivots $p$. It can be extended
to arbitrary pivot paths, with essentially the same proof.

######  Lemma 5.4.8 (Pivot Shift Direction Lemma).

Let $f_{d}\cdots f_{1}$ be the word corresponding to a pivot path in
$\mathrm{Z}_{n,m}$. For every $0\leq i\leq m$, all of the instances of $s_{i}$
in $f_{d}\cdots f_{1}$ shift in the same direction.

######  Observation 5.4.9.

Let $v\in\mathrm{Z}_{n,m}$ and let $p\in\operatorname{Piv}(v)$. Then

$\sigma_{p}(v)\leq\sum_{i=1}^{p}i|v_{i}|+\sum_{i=p+1}^{m}(m+1-i)|v_{i}|.$

If, in addition, $v_{i}\geq 0$ for every $1\leq i\leq m$, then the above is an
equality.

###### Proof.

There exists a path with a wall $p$ from $v$ to $0$ of length
$\sum_{i=1}^{p}i|v_{i}|+\sum_{i=p+1}^{m}(m+1-i)|v_{i}|$ (not necessarily a
$p$-pivot path). It is a path in which the entries $\\{v_{0},\dots,v_{p}\\}$
and $\\{v_{p+1},\dots,v_{m+1}\\}$ of $v$ are handled one by one, left to right
and right to left, respectively; each $v_{i}$, in turn, can be set to $0$ by
$i$ unit shifts from (if $v_{i}=-1$) or to (if $v_{i}=1$) the bucket on the
same side of $p$ as $v_{i}$.

For example, if $v=(0,-1,1,0)$ in $\mathrm{Z}_{n,2}$ for some $n\geq 1$ and
$p=2$, then the path from $v$ to $0$ that corresponds to the word
$\overleftarrow{s}_{0}\overleftarrow{s}_{1}\overrightarrow{s}_{0}$ has length
$1+2=3$, as above. Note that it is not a $2$-pivot path, since
$\overleftarrow{s}_{1}(v)=0$.

If, however, $v_{i}\geq 0$ for every $1\leq i\leq m$, then by the Pivot Shift
Direction Lemma 5.4.8, a path as above is, in fact, a $p$-pivot path. ∎

######  Corollary 5.4.10.

If $p$ is an inner pivot of $v\in\mathrm{Z}_{n,m}$, then

$\sigma_{p}(v)\leq\binom{p+1}{2}+\binom{m-p+1}{2}.$

Comparing Corollary 4.2.9 and Observation 5.4.9 leads to the following
corollary:

######  Corollary 5.4.11.

Let $v\in\mathrm{Y}_{n,m}$, considered also as a vertex in $\mathrm{Z}_{n,m}$.
Then

$d_{\mathrm{Z}_{n,m}}(v,0)=d_{\mathrm{Y}_{n,m}}(v,0).$

######  Definition 5.4.12 ($P$-interval).

Let $P$ be a pivot path of $v$ and let $\\{p_{1},\ldots,p_{t}\\}$ with
$-1<p_{1}<\ldots<p_{t}<m+1$ be the set of inner walls of $P$. Denote
$p_{0}=-1$, $p_{t+1}=m+1$ and
$\operatorname{Piv}(P)=\\{p_{0},p_{1},\ldots,p_{t},p_{t+1}\\}$. Note that
$\operatorname{Piv}(P)\subseteq\operatorname{Piv}(v)$. We call every
$p\in\operatorname{Piv}(P)$ a pivot of $P$. $\operatorname{Piv}(P)$ induces
$t+1$ intervals $[p_{k}+1,p_{k+1}]$ for $-1\leq k\leq t$. Note that these
intervals are a partition of $[0,m+1]$. We call every such interval a
$P$-interval. For convenience, we say that an entry $v_{i}$ is in the interval
$I$ if $i\in I$.

######  Lemma 5.4.13.

Let $f_{d}\cdots f_{1}$ be the word corresponding to a pivot path $P$ of $v$
and let $I$ be a $P$-interval. Then for every $[i,i+1]\subseteq I$ and
$[j,j+1]\subseteq I$, the instances of $s_{i}$ and $s_{j}$ in $f_{d}\cdots
f_{1}$ shift in the same direction.

###### Proof.

By the Pivot Shift Direction Lemma 5.4.8 and the definition of a $P$-interval,
exactly one of $\\{\overleftarrow{s}_{i},\overrightarrow{s}_{i}\\}$ appears in
$f_{d}\cdots f_{1}$, for every $[i,i+1]\subseteq I$. Assume to the contrary,
without loss of generality, that both $\overleftarrow{s}_{i}$ and
$\overrightarrow{s}_{j}$ appear in $f_{d}\cdots f_{1}$ for some $i<j$ in $I$.
Let $k\in I$ such that $i<k$, $s_{k}$ appears shifting right in $f_{d}\cdots
f_{1}$ and $k$ is minimal with these properties. Then both
$\overleftarrow{s}_{k-1}$ and $\overrightarrow{s}_{k}$ appear in $f_{d}\cdots
f_{1}$. A contradiction. ∎

######  Definition 5.4.14 ($\sigma_{I}(P)$).

By Lemma 5.4.13, all of the unit shifts between entries in the same
$P$-interval $I$ are in the same direction throughout $P$. If this direction
is left (right), we say that $P$ shifts left (right) in $I$. Denote the number
of unit shifts between entries in some $P$-interval $I\subseteq[0,m+1]$ within
a pivot path $P$ by $\sigma_{I}(P)$.

######  Lemma 5.4.15.

Let $I=[p_{1}+1,p_{2}]$ be a $P$-interval of some pivot path $P$ of
$v\in\mathrm{Z}_{n,m}$. If $I$ contains one of the buckets, then also assume
that no step in $P$ shifts a unit from an empty bucket (i.e.
$\overleftarrow{s}_{m}((\dots,0))=((\dots,n-1))$ and
$\overrightarrow{s}_{0}((0,\dots))=((n-1,\dots))$ do not appear in $P$). Then

  1. 1.

If $P$ shifts left in $I$, then $\sigma_{I}(P)=\sum_{i\in I}iv_{i}$.

  2. 2.

If $P$ shifts right in $I$, then $\sigma_{I}(P)=\sum_{i\in I}(m+1-i)v_{i}$.

###### Proof.

By Lemma 5.4.13, $P$ shifts either right or left in $I$. Assume that $P$
shifts left in $I$ (the proof of the other case is similar). Note that every
left unit shift in $P$ between entries in $I$ reduces the value of the sum
$\sum_{i\in I}iv_{i}$ exactly by $1$, since a unit is never shifted left from
an empty right bucket. Therefore $\sum_{i\in I}iv_{i}\geq 0$ and
$\sigma_{I}(P)=\sum_{i\in I}iv_{i}$. ∎

######  Lemma 5.4.16.

Let $I=[p_{1}+1,p_{2}]$ be a $P$-interval of some pivot path $P$ of
$v\in\mathrm{Z}_{n,m}$.

  1. 1.

Assume that $p_{2}=m+1$ and that $P$ shifts left in $I$. If
$\sum_{i=j}^{m+1}v_{i}\geq 0$ for every $j\in I$, then there is no left unit
shift in $P$ from an empty right bucket.

  2. 2.

Assume that $p_{1}=-1$ and that $P$ shifts right in $I$. If
$\sum_{i=0}^{j}v_{i}\geq 0$ for every $j\in I$, then there is no right unit
shift in $P$ from an empty left bucket.

###### Proof.

We prove the first case and similar arguments apply to the second case. Note
that a left unit shift from an empty right bucket increases $\sum_{i\in
I}iv_{i}$. On the other hand, every other left unit shift between entries in
$I$ (we call such unit shifts simple left unit shifts in the rest of this
proof) reduces the value of the sum $\sum_{i\in I}iv_{i}$ exactly by $1$.
Therefore, it is sufficient to prove the following.

Claim. It is possible to set to $0$ every $v_{i}$ in $I$ using only simple
left unit shifts between entries in $I$.

Proof. Assume first that $I$ contains no negative entries. If $p_{1}=-1$, then
the claim is trivial. If $p_{1}$ is an inner pivot, then $v_{i}=0$ for every
$i\in I$, since, in this case, a left unit shift between entries in $I$ cannot
decrease the sum $\sum_{i\in I}v_{i}$ (implying, in fact, that $v_{m+1}=0$ and
$|I|=1$).

Otherwise, let $j$ be maximal in $I$ such that $v_{j}=-1$. Of course, $1\leq
j\leq m$. The assumption that $\sum_{i=j}^{m+1}v_{i}\geq 0$ implies that
$\sum_{i=j+1}^{m+1}v_{i}>0$. Therefore, it is possible to set $v_{j}$ to $0$
using only simple left unit shifts between entries in $[j,m+1]$ without
creating new negative entries in $I$. Note that $\sum_{i=j}^{m+1}v_{i}$ does
not change in this process, since all of the unit shifts are simple.
Therefore, this can be repeated until $I$ contains no negative entries.
$\blacksquare$

∎

######  Lemma 5.4.17.

Let $v\in\mathrm{Z}_{n,m}$ such that $v$ has no inner pivots. Then
$d(v,0)\leq\lfloor\frac{n(m+1)}{2}\rfloor$.

###### Proof.

$0<v_{0},v_{m+1}<n$ and $\sum_{i=0}^{m+1}v_{i}=n$, since $v$ has no inner
pivots. The assumption $\operatorname{Piv}(v)=\\{-1,m+1\\}$ also implies that
both $\sum_{i=0}^{j}v_{i}>0$ and $\sum_{i=j}^{m+1}v_{i}>0$ for every $0\leq
j\leq m+1$. Note that $I=[0,m+1]$ is a $P$-interval for every $(m+1)$-pivot
path $P$ and every such path shifts left in $I$. Similarly, every $(-1)$-pivot
path $P$ shifts right in $I$. Therefore, by Lemmas 5.4.15 and 5.4.16,
$\sigma_{m+1}(v)=\sum_{i=0}^{m+1}iv_{i}$ and
$\sigma_{-1}(v)=\sum_{i=0}^{m+1}(m+1-i)v_{i}$.

$\sum_{i=0}^{m+1}iv_{i}+\sum_{i=0}^{m+1}(m+1-i)v_{i}=(m+1)\sum_{i=0}^{m+1}v_{i}=n(m+1)$.
Therefore, by Lemma 5.4.5,
$d(v,0)=\min\\{\sigma_{-1}(v),\sigma_{m+1}(v)\\}\leq\lfloor\frac{\sigma_{-1}(v)+\sigma_{m+1}(v)}{2}\rfloor=\lfloor\frac{n(m+1)}{2}\rfloor.$

∎

######  Lemma 5.4.18.

For every dYoke graph $\mathrm{Z}_{n,m}$ we have
$\operatorname{ecc}_{\mathrm{Z}_{n,m}}(0)\geq\lfloor\frac{n(m+1)}{2}\rfloor$.

###### Proof.

By Lemma 4.2.13 and Corollary 5.4.11,
$\operatorname{ecc}_{\mathrm{Z}_{n,m}}(0)\geq\operatorname{ecc}_{\mathrm{Y}_{n,m}}(0)\geq\lfloor\frac{n(m+1)}{2}\rfloor$.
∎

####  5.4.2 Computation of the Eccentricity

######  Lemma 5.4.19 ($n=1$).

Let $m\geq 0$. Then

$\operatorname{ecc}_{\mathrm{Z}_{1,m}}(0)=\binom{\lceil\frac{m}{2}\rceil+1}{2}+\binom{\lfloor\frac{m}{2}\rfloor+1}{2}.$

###### Proof.

The case $m=0$ is trivial. Assume that $m>0$. Then
$\operatorname{Piv}(v)=\\{-1,\ldots,m+1\\}$ for every $v\in\mathrm{Z}_{1,m}$.
Therefore, by Fact 4.2.12, Observation5.4.6 and Corollary 5.4.10,
$d(v,0)\leq\sigma_{\lceil\frac{m}{2}\rceil}(v)\leq\binom{\lceil\frac{m}{2}\rceil+1}{2}+\binom{\lfloor\frac{m}{2}\rfloor+1}{2}$.
By Observation 5.4.9, this upper bound is obtained by the vertex
$v\in\mathrm{Y}_{1,m}$ with $v_{i}=1$ for every $1\leq i\leq m$. ∎

######  Lemma 5.4.20.

If $0\leq m\leq n$, then
$\operatorname{ecc}_{\mathrm{Z}_{n,m}}(0)=\lfloor\frac{n(m+1)}{2}\rfloor$.

###### Proof.

The case $m=0$ is true by Observation 5.4.1. Assume that $m>0$. Then by Lemma
5.4.18, it is sufficient to show that
$\operatorname{ecc}_{\mathrm{Z}_{n,m}}(0)\leq\lfloor\frac{n(m+1)}{2}\rfloor$.
Let $v\in\mathrm{Z}_{n,m}$. By Lemma 5.4.17, we can assume that $v$ has some
inner pivot $p\in\operatorname{Piv}(v)$. By Observation 5.4.9 and Fact 4.2.12,
$d(v,0)\leq\sum_{i=0}^{p}i+\sum_{i=0}^{m-p}i\leq\binom{m+1}{2}$. Since $m\leq
n$, $\binom{m+1}{2}\leq\frac{n(m+1)}{2}$ and therefore
$\binom{m+1}{2}\leq\lfloor\frac{n(m+1)}{2}\rfloor$. ∎

Throughout the rest of this subsection we assume that $2\leq n\leq m$.

######  Definition 5.4.21.

For $v\in\mathrm{Z}_{n,m}$ define:

  1. 1.

$p_{l}(v)=\max\\{p\in\operatorname{Piv}(v):p\leq\frac{m}{2}\\}$.

  2. 2.

$p_{r}(v)=\min\\{p\in\operatorname{Piv}(v):p>\frac{m}{2}\\}$.

  3. 3.

$I_{c}(v)=[p_{l}(v)+1,p_{r}(v)]$.

  4. 4.

$h(v)=\min\\{|p-\frac{m}{2}|:p\in\operatorname{Piv}(v)\\}$.

  5. 5.

$\eta_{n,m}=\begin{cases}\frac{n}{2}&\mbox{if }2\divides(m-n)\\\
\frac{n+1}{2}&\mbox{if }2\ndivides(m-n)\end{cases}.$

We abbreviate $p_{l}$, $p_{r}$ and $I_{c}$ when $v$ is evident.

Recall the definitions of $u^{0}_{n,m}$, $d^{0}_{n,m}$, $u^{1}_{n,m}$,
$d^{1}_{n,m}$ and $d_{n,m}$ (in $\mathrm{Y}_{n,m}$) from Definitions 4.3.4,
4.3.5 and 4.3.8. Note that $u^{0}_{n,m}$ and $u^{1}_{n,m}$ can also be
considered as vertices in $\mathrm{Z}_{n,m}$ and by Corollary 5.4.11,
$d_{\mathrm{Z}_{n,m}}(u^{0}_{n,m},0)=d_{\mathrm{Y}_{n,m}}(u^{0}_{n,m},0)=d^{0}_{n,m}$
and
$d_{\mathrm{Z}_{n,m}}(u^{1}_{n,m},0)=d_{\mathrm{Y}_{n,m}}(u^{1}_{n,m},0)=d^{1}_{n,m}$.

######  Observation 5.4.22.

$\operatorname{ecc}_{\mathrm{Z}_{n,m}}(0)\geq d_{n,m}$.

In the rest of this subsection, we prove that $d_{n,m}$ is also an upper bound
on the distance of an arbitrary vertex $v$ in $\mathrm{Z}_{n,m}$ from $0$.
Note that $\sum_{i\in I_{c}}v_{i}\in\\{0,\pm n\\}$ for every $v$ in
$\mathrm{Z}_{n,m}$. We split this proof into three cases.

  1. 1.

$h(v)<\eta_{n,m}$ (Lemma 5.4.23).

  2. 2.

$h(v)\geq\eta_{n,m}$ and $\sum_{i\in I_{c}(v)}v_{i}=\pm n$ (Lemma 5.4.28).

  3. 3.

$h(v)\geq\eta_{n,m}$ and $\sum_{i\in I_{c}(v)}v_{i}=0$ (Lemma 5.4.31).

######  Lemma 5.4.23.

Let $v\in\mathrm{Z}_{n,m}$ such that $h(v)<\eta_{n,m}$. Then $d(v,0)\leq
d_{n,m}$.

###### Proof.

The proof of this lemma is identical to the proof of Lemma 4.3.10 in which
Corollary 4.2.9 is replaced by Corollary 5.4.10. ∎

We now deal with the case $h(v)\geq\eta_{n,m}$, $\sum_{i\in I_{c}}v_{i}=\pm
n$. We first reduce to the case $\sum_{i\in I_{c}}v_{i}=n$.

######  Definition 5.4.24.

Let $\mu:\mathrm{Z}_{n,m}\rightarrow\mathrm{Z}_{n,m}$ be the map defined by
$\mu(v)_{i}=-v_{i}$ for every $0\leq i\leq m+1$.

Note that if $v_{0}>0$, then $\mu(v)_{0}=n-v_{0}>0$ and similarly for
$v_{m+1}$. It is straightforward to verify that $\mu$ is an automorphism of
$\mathrm{Z}_{n,m}$.

######  Observation 5.4.25.

Let $v\in\mathrm{Z}_{n,m}$ such that $\sum_{i\in I_{c}}v_{i}=-n$. Then
$I_{c}\subseteq[1,m]$ and $\sum_{i\in I_{c}}\mu(v)_{i}=n$.

###### Proof.

If $I_{c}\nsubseteq[1,m]$, then either $p_{l}=-1$ or $p_{r}=m+1$. Assume that
$p_{l}=-1$. Recall that the buckets are identified with non-negative integers.
Since $0\notin\operatorname{Piv}(v)$, we have $v_{0}>0$. This implies that
$\sum_{i\in I_{c}}v_{i}\in\\{0,n\\}$. A contradiction. If $p_{r}=m+1$, then
$\sum_{i\in I_{c}}v_{i}\in\\{0,n\\}$ following similar arguments. Finally, if
$I_{c}\subseteq[1,m]$ and $\sum_{i\in I_{c}}v_{i}=-n$ then $\sum_{i\in
I_{c}}\mu(v)_{i}=n$, since $\operatorname{Piv}(v)=\operatorname{Piv}(\mu(v))$.
∎

The following lemma generalizes Lemma 5.4.17.

######  Lemma 5.4.26.

Let $v\in\mathrm{Z}_{n,m}$ such that $\sum_{i\in I_{c}}v_{i}=n$. Then

$d(v,0)\leq\sum_{i=1}^{p_{l}}i+\sum_{i=1}^{m-p_{r}}i+\lfloor\frac{n(m+1)}{2}\rfloor.$

###### Proof.

The sum $\sum_{i=1}^{p_{l}}i+\sum_{i=1}^{m-p_{r}}i$ is an upper bound on the
number of steps needed to set to $0$ every $v_{i}$ with $i\in[1,m]\setminus
I_{c}$; note that necessarily, following these steps, a bucket of $v$ not in
$I_{c}$, is also equal to $0$. We can therefore assume that $v_{i}=0$ for
every $i\notin I_{c}$ and prove that
$d(v,0)\leq\lfloor\frac{n(m+1)}{2}\rfloor$. The assumption implies that
$d(v,0)=\min\\{\sigma_{p_{l}}(v),\sigma_{p_{r}}(v)\\}$. Since $\sum_{i\in
I_{c}}v_{i}=n$, every $p_{r}$-pivot path of $v$ shifts left in $[0,p_{r}]$ and
every $p_{l}$-pivot path of $v$ shifts right in $[p_{l}+1,m+1]$. Moreover, the
assumption $\sum_{i\in I_{c}}v_{i}=n$ implies that $\sum_{i=j}^{p_{r}}v_{i}>0$
for every $j\in I_{c}$ and $\sum_{i=p_{l}+1}^{j}v_{i}>0$ for every $j\in
I_{c}$. Therefore, by Lemmas 5.4.15 and 5.4.16,
$d(v,0)=\min\\{\sigma_{p_{l}}(v),\sigma_{p_{r}}(v)\\}\leq\lfloor\frac{\sigma_{p_{l}}(v)+\sigma_{p_{r}}(v)}{2}\rfloor=\lfloor\frac{\sum_{i\in
I_{c}}iv_{i}+\sum_{i\in
I_{c}}(m+1-i)v_{i}}{2}\rfloor=\lfloor\frac{n(m+1)}{2}\rfloor.$ ∎

######  Observation 5.4.27.

  1.   2. 1.

If $2|(m-n)$, then
$d^{0}_{n,m}=\sum_{i=1}^{\frac{m-n}{2}}i+\sum_{i=1}^{m-\frac{m+n}{2}}i+\frac{n(m+1)}{2}$.

  3. 2.

$d^{1}_{n,m}=\sum_{i=1}^{\lfloor\frac{m-n}{2}\rfloor}i+\sum_{i=1}^{m-\lceil\frac{m+n}{2}\rceil}i+\lfloor\frac{n(m+1)}{2}\rfloor$.

###### Proof.

A direct (though tedious) comparison with Lemma 4.3.7. Alternatively, it
follows by observing that $|p_{l}-\frac{m}{2}|=|p_{r}-\frac{m}{2}|$ in both
cases under consideration. ∎

######  Lemma 5.4.28.

Let $v\in\mathrm{Z}_{n,m}$ such that $h(v)\geq\eta_{n,m}$ and $\sum_{i\in
I_{c}(v)}v_{i}=\pm n$. Then $d(v,0)\leq d_{n,m}.$

###### Proof.

By Observation 5.4.25, we can assume that $\sum_{i\in I_{c}(v)}v_{i}=n$.
Assume that $2|(m-n)$. By Observation 5.4.27,
$d_{n,m}=d^{0}_{n,m}=\sum_{i=1}^{\frac{m-n}{2}}i+\sum_{i=1}^{m-\frac{m+n}{2}}i+\frac{n(m+1)}{2}.$
By Lemma 5.4.26,
$d({v},0)\leq\sum_{i=1}^{p_{l}}i+\sum_{i=1}^{m-p_{r}}i+\frac{n(m+1)}{2}.$
Since $h(v)\geq\eta_{n,m}$, $p_{l}\leq\frac{m-n}{2}$ and
$p_{r}\geq\frac{m+n}{2}$. Therefore $d(v,0)\leq d_{n,m}$.

Otherwise assume that $2\ndivides(m-n)$. By Observation 5.4.27, $d_{n,m}\geq
d^{1}_{n,m}=\sum_{i=1}^{\lfloor\frac{m-n}{2}\rfloor}i+\sum_{i=1}^{m-\lceil\frac{m+n}{2}\rceil}i+\lfloor\frac{n(m+1)}{2}\rfloor.$
By Lemma 5.4.26,
$d({v},0)\leq\sum_{i=1}^{p_{l}}i+\sum_{i=1}^{m-p_{r}}i+\lfloor\frac{n(m+1)}{2}\rfloor.$
Since $h(v)\geq\eta_{n,m}$, $p_{l}\leq\lfloor\frac{m-n}{2}\rfloor$ and
$p_{r}\geq\lceil\frac{m+n}{2}\rceil$. Therefore $d(v,0)\leq d_{n,m}$. ∎

######  Lemma 5.4.29.

Let $v\in\mathrm{Z}_{n,m}$ such that $I_{c}(v)\subseteq[1,m]$ and $\sum_{i\in
I_{c}(v)}v_{i}=0$. Then

$d(v,0)\leq\sum_{i=1}^{p_{l}}i+\sum_{i=1}^{m-p_{r}}i+\lfloor\frac{\gamma}{2}\rfloor\lceil\frac{\gamma}{2}\rceil$

where $\gamma=|I_{c}(v)|$.

###### Proof.

As in the beginning of the proof of Lemma 5.4.26, we can assume that $v_{i}=0$
for every $i\notin I_{c}$ and prove that
$d(v,0)\leq\lfloor\frac{\gamma}{2}\rfloor\lceil\frac{\gamma}{2}\rceil$.

Let $P$ be any $p_{l}$\- or $p_{r}$-pivot path of $v$. $I_{c}$ is clearly a
$P$-interval (namely, both $p_{l}$ and $p_{r}$ are walls of $P$), since
$\sum_{i\in I_{c}}v_{i}=0$ and $I_{c}(v)\subseteq[1,m]$. Assume without loss
of generality, that $P$ shifts left in $I_{c}$. By Lemma 5.4.15,
$\sigma_{I_{c}}(P)=\sum_{i\in I_{c}}iv_{i}$. The number of entries of $v$ that
are equal to $1$ is equal to the number of entries of $v$ that are equal to
$-1$, since $\sum_{i\in I_{c}}v_{i}=0$. This number is at most
$\lfloor\frac{\gamma}{2}\rfloor$. The maximum value of $\sum_{i\in
I_{c}}iv_{i}$ is obtained when the first $\lfloor\frac{\gamma}{2}\rfloor$
entries in $I_{c}$ are equal to $-1$ and the last
$\lfloor\frac{\gamma}{2}\rfloor$ entries are equal to $1$. Therefore
$\sum_{i\in
I_{c}}iv_{i}\leq\lfloor\frac{\gamma}{2}\rfloor\lceil\frac{\gamma}{2}\rceil$. ∎

######  Fact 5.4.30.

Let $a$ and $b$ be two non-negative integers. Then

$\sum_{i=1}^{a}i+\sum_{i=1}^{b}i\geq\lfloor\frac{a+b}{2}\rfloor\lceil\frac{a+b}{2}\rceil.$

######  Lemma 5.4.31.

Let $v\in\mathrm{Z}_{n,m}$ such that $h(v)\geq\eta_{n,m}$ and $\sum_{i\in
I_{c}}v_{i}=0$. Then $d(v,0)\leq d_{n,m}$.

###### Proof.

If both $p_{l}$ and $p_{r}$ are outer pivots, then both buckets are non-empty
and $\sum_{i\in I_{c}}v_{i}=n$, since in this case, $v$ has no pivots other
than $p_{l}$ and $p_{r}$; but we assumed $\sum_{i\in I_{c}}v_{i}=0$. Assume
that exactly one of $p_{l}$ and $p_{r}$, say $p_{l}$, is an outer pivot (and
that the other pivot, $p_{r}$, is an inner pivot). Let $\mu$ be the
automorphism of $\mathrm{Z}_{n,m}$ from Definition 5.4.24. Clearly,
$I_{c}(v)=I_{c}(\mu(v))$. By assumption $v_{0}>0$ and therefore
$\mu(v)_{0}=n-v_{0}>0$; hence $\sum_{i\in I_{c}}\mu(v)_{i}=n-\sum_{i\in
I_{c}}v_{i}=n$. Since $0$ is a fixed point of $\mu$, by Lemma 5.4.28,
$d(v,0)=d(\mu(v),0)\leq d_{n,m}$, as required.

Otherwise both $p_{l}$ and $p_{r}$ are inner pivots, that is,
$I_{c}(v)\subseteq[1,m]$. By Lemma 5.4.29,
$d({v},0)\leq\sum_{i=1}^{p_{l}}i+\sum_{i=1}^{m-p_{r}}i+\lfloor\frac{\gamma}{2}\rfloor\lceil\frac{\gamma}{2}\rceil$
where $\gamma=|I_{c}(v)|$. Let $p=\lfloor\frac{m+n}{2}\rfloor$ so that, by
Lemma 4.3.7, $d^{0}_{n,m}=\sum_{i=1}^{p}i+\sum_{i=1}^{m-p}i$. Note that
$|p-\frac{m}{2}|\leq\eta_{n,m}$. The assumption $h(v)\geq\eta_{n,m}$ implies
that $p_{l}\leq p\leq p_{r}$. Therefore

$\displaystyle d_{n,m}-d(v,0)\geq
d^{0}_{n,m}-d(v,0)\geq\sum_{i=p_{l}+1}^{p}i+\sum_{i=m-p_{r}+1}^{m-p}i-\lfloor\frac{\gamma}{2}\rfloor\lceil\frac{\gamma}{2}\rceil.$

Clearly,
$\sum_{i=p_{l}+1}^{p}i+\sum_{i=m-p_{r}+1}^{m-p}i\geq\sum_{i=1}^{p-p_{l}}i+\sum_{i=1}^{p_{r}-p}i$.
Let $a=p-p_{l}$, let $b=p_{r}-p$ and note that $a+b=\gamma$. Therefore, by
Fact 5.4.30,
$d_{n,m}-d(v,0)\geq\sum_{i=1}^{a}i+\sum_{i=1}^{b}i-\lfloor\frac{\gamma}{2}\rfloor\lceil\frac{\gamma}{2}\rceil\geq
0.$ ∎

######  Lemma 5.4.32.

Let $2\leq n\leq m$ be two integers. Then
$\operatorname{ecc}_{\mathrm{Z}_{n,m}}(0)=d_{n,m}$.

###### Proof.

Combine Observation 5.4.22 with Lemmas 5.4.23, 5.4.28 and 5.4.31. ∎

######  Theorem 5.4.33.

For all values of $n$ and $m$, the eccentricity of $0$ in $\mathrm{Z}_{n,m}$
is equal to the eccentricity of $0$ in $\mathrm{Y}_{n,m}$ as it appears in
Theorem 4.0.1.

###### Proof.

This theorem is the combined result of Lemmas 5.4.19, 5.4.20 and 5.4.32. ∎

##  Chapter 6 Automorphisms of $\mathrm{Y}_{n,m}$

This chapter deals with automorphisms of $\mathrm{Y}_{n,m}$. In Section 6.1,
we introduce three fundamental automorphisms of $\mathrm{Y}_{n,m}$ and find
the structure of the group they generate. In Section 6.2, we show that the
group generated by these three fundamental automorphisms is, in fact,
precisely the automorphism group of $\mathrm{Y}_{n,m}$, whenever $m\neq 2$ and
$(n,m)\neq(1,3)$. We cover the case $(n,m)=(1,3)$ separately.

###  6.1 Fundamental Automorphisms

######  Definition 6.1.1.

Let $\varphi$, $\psi$ and $\tau$ be the following three maps from
$\mathrm{Y}_{n,m}$ to $\mathrm{Y}_{n,m}$:

$\begin{array}[]{c c c
l}&\varphi(v_{0},v_{1},\dots,v_{m},v_{m+1})&=&(v_{0}+1,v_{1},\dots,v_{m},v_{m+1}-1)\\\
&\psi(v_{0},v_{1},\dots,v_{m},v_{m+1})&=&(v_{m+1},v_{m},\dots,v_{1},v_{0})\\\
&\tau(v_{0},v_{1},\dots,v_{m},v_{m+1})&=&(-v_{0},1-v_{1},\dots,1-v_{m},-(m+v_{m+1}))\\\
\end{array}$

Note that $\varphi$ and $\tau$ are essentially as in Definition 5.1.12. We
define them here again for completeness.

######  Observation 6.1.2.

$\varphi$, $\psi$ and $\tau$ are automorphisms of $\mathrm{Y}_{n,m}$.

######  Definition 6.1.3.

Denote $\mathscr{A}_{n,m}=\left<\varphi,\psi,\tau\right>$; the subgroup of
$\operatorname{Aut}(\mathrm{Y}_{n,m})$ generated by $\\{\varphi,\psi,\tau\\}$.

Recall that the dihedral group $D_{n}$ ($\forall n\geq 1$) is the group of
order $2n$ with presentation:

$D_{n}=\left<g,h\;|\;g^{n}=h^{2}=1,hgh=g^{-1}\right>.$

Denote by $o(g)$ the order of an element $g$ in a finite group.

######  Theorem 6.1.4 (The structure of $\mathscr{A}_{n,m}$).

  1.   2. 1.

$\mathscr{A}_{1,0}\cong\\{1\\}$ and
$\mathscr{A}_{2,0}\cong\mathscr{A}_{1,1}\cong C_{2}$, the cyclic group of
order $2$.

  3. 2.

$\mathscr{A}_{n,0}\cong D_{n}$ ($\forall n>2$).

  4. 3.

$\mathscr{A}_{1,m}\cong C_{2}\times C_{2}$ ($\forall m>1$).

  5. 4.

If $n>1$ and $m>0$, then

    1. (a)

if at least one of $n$ and $m$ is odd, then $\mathscr{A}_{n,m}\cong D_{2n}$;

    2. (b)

otherwise ($n$ and $m$ are even), $\mathscr{A}_{n,m}\cong D_{n}\times C_{2}$.

This theorem is the combined result of forthcoming Lemmas 6.1.10 and 6.1.12.

######  Observation 6.1.5.

The following two properties hold in $\mathscr{A}_{n,m}$ for any $n$ and $m$.

  1. 1.

$\psi\varphi=\varphi^{-1}\psi$ and $\tau\varphi=\varphi^{-1}\tau$.

  2. 2.

$(\tau\psi)^{2}=\varphi^{m}$.

###### Proof.

The first property is trivial. Let $u\in\mathrm{Y}_{n,m}$ and $f=\tau\psi$.
Then

$\begin{split}(u_{0},\dots,u_{m+1})&\overset{f}{\mapsto}(-u_{m+1},1-u_{m},\dots,1-u_{1},-(m+u_{0}))\\\
&\overset{f}{\mapsto}(u_{0}+m,u_{1},\dots,u_{m},u_{m+1}-m).\end{split}$

This proves the second property. ∎

######  Fact 6.1.6.

Let $n>2$. If $g$ and $h$ are two elements in a group such that $o(g)=n$,
$o(h)=2$ and $gh=hg^{-1}$, then $\left<g,h\right>\cong D_{n}$.

######  Observation 6.1.7.

  1.   2. 1.

$\varphi=\psi$ if and only if $n=1$ and $m\leq 1$;

  3. 2.

$\varphi=\tau$ if and only if $n=1$ and $m=0$;

  4. 3.

$\psi=\tau$ if and only $m=0$;

######  Observation 6.1.8.

The orders of $\varphi$, $\psi$ and $\tau$ in $\mathscr{A}_{n,m}$ are as
follows:

  1. 1.

$\psi=Id$ if and only if $(n,m)\in\\{(1,0),(1,1),(2,0)\\}$, otherwise
$o(\psi)=2$;

  2. 2.

$\tau=Id$ if and only if $(n,m)\in\\{(1,0),(2,0)\\}$, otherwise $o(\tau)=2$;

  3. 3.

$o(\varphi)=n$.

######  Corollary 6.1.9.

If $n>1$ and $m>0$, then $\varphi$, $\psi$ and $\tau$ are distinct and of
orders $n$, $2$ and $2$, respectively.

######  Lemma 6.1.10.

  1.   2. 1.

$\mathscr{A}_{1,0}\cong\\{1\\}$ and
$\mathscr{A}_{2,0}\cong\mathscr{A}_{1,1}\cong C_{2}$.

  3. 2.

$\mathscr{A}_{n,0}\cong D_{n}$ ($\forall n>2$).

  4. 3.

$\mathscr{A}_{1,m}\cong C_{2}\times C_{2}$ ($\forall m>1$).

###### Proof.

The first case is trivial. By Observations 6.1.7 and 6.1.8, if $n>2$ and
$m=0$, then $\psi=\tau\neq Id$. Moreover, by Observation 6.1.5 (Property $1$),
Observation 6.1.8 and Fact 6.1.6, $\left<\varphi,\psi\right>$ is isomorphic to
$D_{n}$. This proves the second case. If $n=1$ and $m>1$, then $\varphi=Id$,
$\psi\neq\tau$, $o(\psi)=o(\tau)=2$ and $\psi\tau=\tau\psi$. This proves the
third case. ∎

######  Lemma 6.1.11.

If $m>0$ and $(n,m)\neq(1,1)$, then $|\mathscr{A}_{n,m}|=4n$.

###### Proof.

If $n=1$ (and $m>1$), then $|\mathscr{A}_{1,m}|=4$, by Lemma 6.1.10. Assume
that $n>1$ (and $m>0$). By Observation 6.1.5, every element in
$\mathscr{A}_{n,m}$ can be written in the form $\varphi^{k}\tau^{i}\psi^{j}$
where $0\leq k\leq n-1$ and $i,j\in\\{0,1\\}$. Therefore
$|\mathscr{A}_{n,m}|\leq 4n$.

Assume to the contrary that $\varphi^{k}\tau^{i}\psi^{j}=Id$ for
$(k,i,j)\neq(0,0,0)$. By Corollary 6.1.9, $\varphi$, $\psi$ and $\tau$ are
distinct and of orders $n$, $2$ and $2$, respectively. Therefore, $k\neq 0$.
If $i=0$, then $\varphi^{k}\psi=Id$. This is impossible, since
$\varphi^{k}\psi(0)\neq 0$. On the other hand, if $i=1$, then
$\varphi^{k}\tau\psi^{j}=Id$. This is also impossible, again, since
$\varphi^{k}\tau\psi^{j}(0)\neq 0$. This is a contradiction, completing the
proof. ∎

######  Lemma 6.1.12.

If $n>1$ and $m>0$, then

  1. 1.

if at least one of $n$ and $m$ is odd, then $\mathscr{A}_{n,m}\cong D_{2n}$;

  2. 2.

otherwise, $\mathscr{A}_{n,m}\cong D_{n}\times C_{2}$.

###### Proof.

We start with Case 1. Assume that at least one of $n$ and $m$ is odd.
Therefore, there exists some integer $k$ such that $m+2k$ and $n$ are coprime.
For this $k$ define $\alpha=\varphi^{k}\tau\psi$ and $\beta=\tau\varphi^{k}$.
We show that $\left<\alpha,\beta\right>\cong D_{2n}$. This proves Case 1,
since by Lemma 6.1.11, $|\mathscr{A}_{n,m}|=4n$.

$o(\alpha)$ is even, since $m>0$ and $(\alpha^{i}(0))_{j}=1$ for every odd
integer $i$ and $1\leq j\leq m$. Therefore, $o(\alpha)=2o(\alpha^{2})$. By
Observation 6.1.5,

$\alpha^{2}=\varphi^{k}\tau\psi\varphi^{k}\tau\psi=\varphi^{k}\tau\varphi^{-k}\psi\tau\psi=\varphi^{2k}\tau\psi\tau\psi=\varphi^{m+2k}.$

Since $m+2k$ and $n$ are coprime, this implies that $o(\alpha^{2})=n$. This
proves that $o(\alpha)=2n$. Now $\beta(0)\neq 0$, so by Observation 6.1.5,
$o(\beta)=2$ and
$\beta\alpha\beta=(\tau\varphi^{k})(\varphi^{k}\tau\psi)(\tau\varphi^{k})=\psi\tau\varphi^{-k}=\alpha^{-1}$.
By Fact 6.1.6, this proves that $\left<\alpha,\beta\right>\cong D_{2n}$, as
required.

We proceed to prove Case 2. $\mathscr{A}_{n,m}\cong D_{n}\times C_{2}$ if and
only if there exist two subgroups $N\cong D_{n}$ and $M\cong C_{2}$ of
$\mathscr{A}_{n,m}$ such that $N\cap M=\\{Id\\}$, $NM=\mathscr{A}_{n,m}$ and
the generator of $M$ commutes with the generators of $N$. Let
$N=\left<\varphi,\psi\right>$ and let $M=\left<\gamma\right>$ where
$\gamma=\varphi^{\frac{m}{2}}\psi\tau$ ($=\varphi^{-\frac{m}{2}}\tau\psi$).

If $n=2$ (and $m>0$), then $\varphi$ and $\psi$ clearly commute. Moreover, by
Observations 6.1.7 and 6.1.8, they are also distinct and of order $2$.
Therefore, $N\cong C_{2}\times C_{2}\cong D_{2}$. For $n>2$, $N\cong D_{n}$ by
Observations 6.1.5 and 6.1.8 and Fact 6.1.6. $M\cong C_{2}$, since
$\gamma^{2}=(\varphi^{-\frac{m}{2}}\tau\psi)^{2}=\varphi^{-m}(\tau\psi)^{2}=Id$
and $\gamma(0)\neq 0$. By Observation 6.1.5, $\gamma$ commutes with $\varphi$,
and
$\psi\gamma\psi=\psi(\varphi^{-\frac{m}{2}}\tau\psi)\psi=\varphi^{\frac{m}{2}}\psi\tau=\gamma$.
Therefore, $\gamma$ commutes also with $\psi$. For every $1\leq j\leq m$,
$\varphi(0)_{j}=\psi(0)_{j}=0$ but $\gamma(0)_{j}=1$. Therefore $\gamma\notin
N$ and $N\cap M=\\{Id\\}$. $\mathscr{A}_{n,m}\subseteq NM$, since
$\tau=\psi\varphi^{-\frac{m}{2}}\gamma\in NM$. This completes the proof. ∎

###  6.2 The Automorphism Group of $\mathrm{Y}_{n,m}$

The main result of this section is the following theorem.

######  Theorem 6.2.1.

  1.   2. 1.

$\operatorname{Aut}(\mathrm{Y}_{1,3})\cong D_{4}\times C_{2}.$

  3. 2.

$\operatorname{Aut}(\mathrm{Y}_{n,m})\cong\mathscr{A}_{n,m}$ for all $n\geq 1$
and $m\geq 0$ s.t. $m\neq 2$ and $(n,m)\neq(1,3)$.

This theorem is the combined result of forthcoming Lemmas 6.2.2, 6.2.16 and
Observation 6.2.3.

######  Lemma 6.2.2.

$\operatorname{Aut}(\mathrm{Y}_{1,3})\cong D_{4}\times C_{2}.$

###### Proof.

Since $v_{0}=v_{4}=0$ for every vertex $v\in\mathrm{Y}_{1,3}$, we identify
each vertex $v$ with $(v_{1}v_{2}v_{3})$ (since $v_{i}\in\\{0,1\\}$ for every
$1\leq i\leq 3$, the vertices are well defined without commas), see Figure
6.1. Let $f_{1}$, $f_{2}$ and $f_{3}$ be three automorphisms of
$\mathrm{Y}_{1,3}$, each one interchanging a single pair of vertices and
fixing the rest of the graph: $f_{1}$ interchanges $(100)$ and $(001)$,
$f_{2}$ interchanges $(101)$ and $(010)$ and $f_{3}$ interchanges $(110)$ and
$(011)$. Let $\tau$ be as in Definition 6.1.1 and note that $\tau$
interchanges $(000)$ and $(111)$.

$(000)$ and $(111)$ are the only two vertices of valency $2$ in
$\mathrm{Y}_{1,3}$. Therefore, for every
$\sigma\in\operatorname{Aut}(\mathrm{Y}_{1,3})$, either
$\sigma\in\operatorname{St}(000)$, the stabilizer of $(000)$, or
$\tau\sigma\in\operatorname{St}(000)$. This implies that
$|\operatorname{Aut}(\mathrm{Y}_{1,3})|=2|\operatorname{St}(000)|$. There are
precisely two vertices at each distance $1$, $2$ and $3$ from $(000)$ (and a
unique vertex at distance $4$). Therefore $|\operatorname{St}(000)|\leq
2^{3}=8$. $(000)$ is fixed by $f_{1}$, $f_{2}$ and $f_{3}$ and
$|\left<f_{1},f_{2},f_{3}\right>|=|C_{2}\times C_{2}\times C_{2}|=8$. This
implies that $|\operatorname{St}(000)|=8$ and therefore,
$|\operatorname{Aut}(\mathrm{Y}_{1,3})|=16$.

Let $\eta=\tau f_{1}$. Then $o(\eta)=4$ and $\eta f_{3}=f_{3}\eta^{-1}$.
Therefore, by Fact 6.1.6, $\left<\eta,f_{3}\right>\cong D_{4}$.
$f_{2}\notin\left<\eta,f_{3}\right>$ and $f_{2}$ commutes with both $\eta$ and
$f_{3}$. Therefore, $\left<\eta,f_{2},f_{3}\right>\cong D_{4}\times C_{2}$.
Since $|D_{4}\times C_{2}|=16=|\operatorname{Aut}(\mathrm{Y}_{1,3})|$, we have
$\operatorname{Aut}(\mathrm{Y}_{1,3})\cong\left<\eta,f_{2},f_{3}\right>\cong
D_{4}\times C_{2}$. ∎

(000)(100)(001)(101)(010)(011)(110)(111) Figure 6.1: $\mathrm{Y}_{1,3}$
(vertices are drawn without the buckets)

######  Observation 6.2.3.

For $m\leq 1$, $\operatorname{Aut}(\mathrm{Y}_{n,m})=\mathscr{A}_{n,m}$.

###### Proof.

The cases $\mathrm{Y}_{1,0}$, $\mathrm{Y}_{2,0}$ and $\mathrm{Y}_{1,1}$ are
trivial. By Observation 3.1.3, if $m=0$ and $n>2$, then $\mathrm{Y}_{n,m}$ is
the cycle graph on $n$ vertices. If $m=1$ and $n>1$, then $\mathrm{Y}_{n,m}$
is the cycle graph on $2n$ vertices. Therefore, in both cases,
$\operatorname{Aut}(\mathrm{Y}_{n,m})$ is the corresponding dihedral group. By
Theorem 6.1.4, it follows that
$\operatorname{Aut}(\mathrm{Y}_{n,m})=\mathscr{A}_{n,m}$ when $m\leq 1$. ∎

In the rest of this section, unless explicitly stated otherwise, we assume
that $m\geq 3$ and $(n,m)\neq(1,3)$ in $\mathrm{Y}_{n,m}$. The purpose of the
rest of this section is the proof of Lemma 6.2.16 where we show that indeed
$\operatorname{Aut}(\mathrm{Y}_{n,m})=\mathscr{A}_{n,m}$. Specifically, Lemma
6.2.12 implies that if there exists
$\pi\in\operatorname{Aut}(\mathrm{Y}_{n,m})$ such that
$\pi\notin\mathscr{A}_{n,m}$, then we can assume that $\pi$ maps between a
unique pair of vertices in $\mathrm{Y}_{n,m}$: $(n-1,0,0,1,0,\dots,0)$ and
$(n-2,1,1,0,0,\dots,0)$. This leads to a contradiction.

######  Definition 6.2.4.

Let $x\in\mathrm{Y}_{n,m}$ and let $k\in\\{0,\dots,n-1\\}$. We use the
following notations throughout this section.

  1. 1.

$0_{\ell}=\overrightarrow{s}_{0}(0)$ and $0_{r}=\overleftarrow{s}_{m}(0)$.

  2. 2.

$0_{k}=\varphi^{k}(0)=(k,0,\dots,0,n-k)$.

  3. 3.

$1_{k}=\varphi^{k}(0,1,\dots,1,-m)=(k,1,\dots,1,-(m+k))$.

  4. 4.

$N^{0}(x)=\\{y:y\sim x\mbox{ and }d(y,0)=d(x,0)-1\\}$.

  5. 5.

$n^{0}(x)=|N^{0}(x)|$.

If $y\in N^{0}(x)$, we say that $x$ covers $y$ and write $y\lessdot x$.

We use diagrams to visualize covering relations between vertices. For example,
in the following diagram $w=s_{j}(v)\lessdot v$ and the directed edge $(u,w)$,
combined with the label $\overleftarrow{s}_{i}$, indicates that
$w=\overleftarrow{s}_{i}(u)\lessdot u$.

${u}$ ${v}$ ${w}$ $\overleftarrow{s}_{i}$$s_{j}$

In Definition 6.2.5, we setup three vertices in $\mathrm{Y}_{n,m}$ in a way
that will recur throughout the statements in this section. The example diagram
above visualizes the covering relations in this setup.

######  Definition 6.2.5.

Let $u,v\in\mathrm{Y}_{n,m}$ be two distinct vertices such that
$N^{0}(u)=N^{0}(v)$ and $d(u,0)=d(v,0)\geq 2$. Assume that there exists $w\in
N^{0}(u)=N^{0}(v)$ such that $w=\overleftarrow{s}_{i}(u)=s_{j}(v)$ for some
$0\leq i,j\leq m$. We say that $(u,v,w)$ are in $V_{i,j}$-position.

######  Lemma 6.2.6.

Let $(u,v,w)$ be in $V_{i,j}$-position. Then $|i-j|>1$.

###### Proof.

$i\neq j$, since $u\neq v$. Assume to the contrary that $|i-j|=1$ and assume
that $j=i-1$. By definition, $u,v$ and $w$ are distinct and $s_{i}(u)$ shifts
left, therefore $s_{i-1}(w)$ must shift left as well. We visualize the
scenarios in this proof using diagrams in which the three entries that $s_{i}$
and $s_{j}$ change are all non-bucket entries. Note that the proof also covers
the cases in which one of these entries is a bucket (at most one of the
entries, since $m\geq 3$).

${(u_{i-1},u_{i},u_{i+1})=(0,0,1)}$${(w_{i-1},w_{i},w_{i+1})=(0,1,0)}$${(v_{i-1},v_{i},v_{i+1})=(1,0,0)}$$\overleftarrow{s}_{i}$$\overleftarrow{s}_{i-1}$

By Lemma 4.2.4 and Observation 4.2.8, $u$ has a geodesic pivot $p$ such that
$p\geq i+1$. $p$ is also a geodesic pivot of $w$; therefore, by Observation
4.2.8, $\overleftarrow{s}_{i-1}(w)=v\lessdot w$, in contradiction to $w\in
N^{0}(v)$.

Assume that $j=i+1$. Similarly to the previous case, $s_{i+1}(w)$ must shift
left as well, $u$ has a geodesic pivot $p$ such that $p\geq i+1$ and $p$ is
also a geodesic pivot of $w$. In this case, since
$\overleftarrow{s}_{i+1}(w)=v\gtrdot w$, $w$ has no geodesic pivot greater
than $i+1$. Therefore, $i+1$ is a geodesic pivot of $w$. $i$ is also a
geodesic pivot of $w$ following similar arguments. This implies that $i$ and
$i+1$ are geodesic pivots of $v$ and $u$ respectively. In the following
diagram, we use the symbol $\|$ to visualize a geodesic pivot.

${(u_{i},u_{i+1},u_{i+2})=(0,1\|1)}$ ${(v_{i},v_{i+1},v_{i+2})=(1\|1,0)}$
${(w_{i},w_{i+1},w_{i+2})=(1\|0\|1)}$
$\overleftarrow{s}_{i}$$\overleftarrow{s}_{i+1}$

We split the rest of the proof of this case ($j=i+1$) into the following three
sub-cases. Assume that $n=1$ and that $m$ is even ($3<m$). Then, by
Observation 4.2.11, $\frac{m}{2}$ is a geodesic pivot of every vertex in
$\mathrm{Y}_{1,m}$. Note that a unit shift between $\frac{m}{2}$ and
$\frac{m}{2}+1$ does not change the distance of any vertex from $0$. This
implies that there does not exist $w\in\mathrm{Y}_{1,m}$ and $i\in\\{0,\dots
m\\}$ such that both $w\lessdot\overrightarrow{s}_{i}(w)$ and
$w\lessdot\overleftarrow{s}_{i+1}(w)$.

In the last two cases, we show that $N^{0}(u)\neq N^{0}(v)$. Assume that $n=1$
and that $m$ is odd ($3<m$). Then, by Observation 4.2.11,
$\lfloor\frac{m}{2}\rfloor$ and $\lceil\frac{m}{2}\rceil$ are geodesic pivots
of every vertex in $\mathrm{Y}_{1,m}$. This implies that
$i=\lfloor\frac{m}{2}\rfloor$. For example, $u=(0,0,0,1,1,0,0)$,
$w=(0,0,1,0,1,0,0)$ and $v=(0,0,1,1,0,0,0)$ in $\mathrm{Y}_{1,5}$. Therefore,
there exists some $t<i$ such that $\overleftarrow{s}_{t}(v)=v^{\prime}\lessdot
v$ and clearly $v^{\prime}\notin N^{0}(u)$.

Assume that $1<n$ (and $3\leq m$). Then at least one of the following is true:
either $0<i$ or $i+2<m+1$. If $0<i$, then there exists some $t<i$ such that
$\overleftarrow{s}_{t}(v)=v^{\prime}\lessdot v$ and $v^{\prime}\notin
N^{0}(u)$. If $i+2<m+1$, then there exists some $t\geq i+2$ such that
$\overrightarrow{s}_{t}(u)=u^{\prime}\lessdot u$ and $u^{\prime}\notin
N^{0}(v)$. In both cases $N^{0}(u)\neq N^{0}(v)$. ∎

######  Lemma 6.2.7.

Let $u\in\mathrm{Y}_{n,m}$ and let $s_{t}$ and $s_{k}$ be two distinct
elements in $\mathcal{S}_{n,m}$ such that $1<|t-k|$, $s_{t}(u)\lessdot u$ and
$s_{k}(u)\lessdot s_{k}s_{t}(u)$. Then

  1. 1.

both $s_{t}(u)$ and $s_{k}(u)$ shift units from entries in $I_{c}(u)$;

  2. 2.

$s_{t}(u)$ and $s_{k}(u)$ shift in opposite directions;

  3. 3.

$p_{l}(u)$ and $p_{r}(u)$ are geodesic pivots.

###### Proof.

$s_{t}$ and $s_{k}$ commute, since $1<|t-k|$. Denote
$v=s_{t}s_{k}(u)=s_{k}s_{t}(u)$, $w=s_{t}(u)$ and $w^{\prime}=s_{k}(u)$. The
assumptions imply that $u$, $v$, $w$ and $w^{\prime}$ are distinct and the
covering relations between them can be presented as follows:

${u}$${v}$${w}$${w^{\prime}}$$s_{t}$$s_{k}$$s_{t}$

Assume that $s_{t}(u)$ shifts left (the proof is similar if $s_{t}(u)$ shifts
right). $t+1\leq p_{r}(u)$, since $\overleftarrow{s}_{t}(u)\lessdot u$. If
$t+1\leq p_{l}(u)$, then $s_{t}$ shifts left in every geodesic pivot path of
$u$. This implies that $\overleftarrow{s}_{t}s_{k}(u)\lessdot s_{k}(u)$. A
contradiction. Therefore $s_{t}$ shifts a unit from an entry in $I_{c}(u)$.
$s_{k}(u)$ also shifts a unit from an entry in $I_{c}(u)$, following similar
arguments. Note that $s_{k}(u)$ and $s_{k}(w)$ shift in the same direction,
since $1<|t-k|$. This implies that $s_{t}(u)$ and $s_{k}(u)$ shift in opposite
directions, otherwise $s_{k}(w)\lessdot w$. Case 3 is implied by the first
two, by Observation 4.2.11. ∎

######  Corollary 6.2.8.

Let $(u,v,w)$ be in $V_{i,j}$-position. If $s_{j}(u)\lessdot u$, then

  1. 1.

$\\{i+1,j\\}\subseteq I_{c}(u)$, $\\{i,j+1\\}\subseteq I_{c}(v)$;

  2. 2.

$s_{j}(u)$ shifts right;

  3. 3.

$p_{l}(u),p_{r}(u),p_{l}(v)$ and $p_{r}(v)$ are geodesic pivots.

######  Lemma 6.2.9.

Let $x\in\mathrm{Y}_{n,m}$ such that

  1. 1.

$n^{0}(x)=2$;

  2. 2.

$I_{c}(x)$ is not trivial (i.e. $x_{p_{l}+1}\neq 0$, $x_{p_{r}}\neq 0$ and
$\sum_{i\in I_{c}}x_{i}=n$);

  3. 3.

both $p_{l}(x)$ and $p_{r}(x)$ are geodesic pivots.

Then $x$ is in one of the following three forms:
Either $p_{l}=-1$ and $p_{r}=m+1$:

  1. (a)

$x=(\frac{n}{2},0,\dots,0,\frac{n}{2})$ (in this case $n$ is even);

  2. (b)

$x=(\frac{n-m}{2},1,\dots,1,\frac{n-m}{2})$ (in this case $n-m\geq 2$ and
$2\divides n-m$).

Or $p_{l}=\frac{m-n}{2}$, $p_{r}=\frac{m+n}{2}$, and for some $0\leq
t_{1}\leq\frac{m-n}{2}+1$ and $\frac{m+n}{2}\leq t_{2}\leq m$:

  1. (c)

$x=(-(\frac{n-m}{2}+1-t_{1}),0,\dots,0,\overbrace{1,\dots,1}^{x_{t_{1}},\dots,x_{t_{2}}},0,\dots,0,-(\frac{n+m}{2}-t_{2}))$
(in this case $m\geq n$ and $2\divides m-n$).

###### Proof.

We split the proof into the following three cases:

Assume that $p_{l}=-1$ and $p_{r}=m+1$. Then $x_{0}\neq 0$, $x_{m+1}\neq 0$
and $\sum_{i=0}^{m+1}x_{i}=n$. Note that all of the non-bucket entries of $x$
must be equal to each other, otherwise $n^{0}(x)>2$. If
$(x_{1},\dots,x_{m})=(0,\dots,0)$, then
$x=(\frac{n}{2},0,\dots,0,\frac{n}{2})$, the only vertex in which
$(x_{1},\dots,x_{m})=(0,\dots,0)$ and $\sigma_{-1}(x)=\sigma_{m+1}(x)$.
Similarly, if $(x_{1},\dots,x_{m})=(1,\dots,1)$, then
$x=(\frac{n-m}{2},1,\dots,1,\frac{n-m}{2})$ ($m<n$, $2\divides m-n$ and
$n-m\geq 2$).

Assume that both $p_{l}$ and $p_{r}$ are inner pivots. Then
$x_{p_{l}+1}=x_{p_{r}}=1$ and $\sum_{i\in I_{c}}x_{i}=n$. Note that all of the
non-bucket entries of $x$ that are equal to $1$ are contiguous, otherwise
$n^{0}(x)>2$. Therefore, $p_{r}-p_{l}=n$, $p_{l}=\frac{m-n}{2}$ and
$p_{r}=\frac{m+n}{2}$ (and $m\geq n$ and $2\divides m-n$). This implies that
$x$ is in the form of Case (c) of this lemma, since
$\sigma_{p_{l}}(x)=\sigma_{p_{r}}(x)$.

Finally, we show that if one of $p_{l}$ and $p_{r}$ is an inner pivot, the
other an outer pivot and $n^{0}(x)=2$, then $p_{l}$ and $p_{r}$ cannot both be
geodesic pivots. Assume, without loss of generality, that $p_{l}=-1$ and
$\frac{m}{2}<p_{r}\leq m$. Then $x_{0}\neq 0$, $x_{p_{r}}=1$ and
$\sum_{i=0}^{p_{r}}x_{i}=n$. Note, again, that all of the non-bucket entries
of $x$ that are equal to $1$ are contiguous, otherwise $n^{0}(x)>2$. This
implies that $\sigma_{-1}(x)=\sigma_{p_{l}}(x)>\sigma_{p_{r}}(x)$. ∎

######  Observation 6.2.10.

Let $u,v,w\in\mathrm{Y}_{n,m}$, such that $u$ and $v$ are each with one of the
forms in Lemma 6.2.9. Then $(u,v,w)$ is not in $V_{i,j}$-position.

######  Lemma 6.2.11.

Let $(u,v,w)$ be in $V_{i,j}$-position. Then $n^{0}(u)=n^{0}(v)=1$.

###### Proof.

By Lemma 6.2.6, necessarily $|i-j|>1$. Therefore, $s_{i}$ and $s_{j}$ commute
and both $v=s_{j}s_{i}(u)$ and $v=s_{i}s_{j}(u)$, are geodesics between $u$
and $v$. We first show that these two geodesics are, in fact, the only two
geodesics between $u$ and $v$ and therefore $n^{0}(u)=n^{0}(v)\leq 2$.

If $1<n$ or $1\leq i,j\leq m-1$, then $u$ and $v$ have four distinct entries
(indexed by $i,i+1,j$ and $j+1$) in which they are not equal. This implies
that $v=s_{j}s_{i}(u)$ and $v=s_{i}s_{j}(u)$ are the only two geodesics
between $u$ and $v$, as required.

Assume that $n=1$ (and $3<m$) and that at least one of $i$ and $j$ is in
$\\{0,m\\}$. Note that $s_{i}$ and $s_{j}$ shift in $s_{j}s_{i}(v)$ and
$s_{i}s_{j}(v)$ in opposite directions than they do in $v=s_{j}s_{i}(u)$ and
$v=s_{i}s_{j}(u)$. Therefore, we can assume without loss of generality, that
$i\in\\{0,m\\}$ (by interchanging the roles of $s_{i}$ and $s_{j}$ if
$i\notin\\{0,m\\}$; and if $s_{j}(u)$ shifts right, then also by interchanging
the roles of $u$ and $v$). Assume also that $i=0$ (the proof for the case
$i=m$ follows by similar arguments).

If $j=m$, then $v=s_{j}s_{i}(u)$ and $v=s_{i}s_{j}(u)$ are the only two
geodesics from $u$ to $v$, since $3<m$. Therefore $2\leq j\leq m-1$. In this
case, $\sum_{i=1}^{m}u_{i}-v_{i}=1$; therefore either $\overleftarrow{s}_{0}$
or $\overrightarrow{s}_{m}$ is in every word corresponding to a geodesic from
$u$ to $v$. It is sufficient to show that $\overleftarrow{s}_{0}$ is in every
word corresponding to a geodesic from $u$ to $v$. If $j<m-1$, then clearly,
$\overleftarrow{s}_{0}$ is in every word corresponding to a geodesic from $u$
to $v$. The same result follows if $j=m-1$, again, since $m>3$.

It remains to show that $n^{0}(u)=n^{0}(v)\neq 2$. Assume to the contrary that
$n^{0}(u)=n^{0}(u)=2$. Since $v=s_{j}s_{i}(u)$ and $v=s_{i}s_{j}(u)$ are the
only two geodesics from $u$ to $v$,
$N^{0}(u)=N^{0}(v)=\\{s_{i}(u),s_{j}(u)\\}=\\{s_{j}(v),s_{i}(v)\\}$. Therefore
$s_{j}(u)\lessdot u$ and the vertices $u$ and $v$ are as in Corollary 6.2.8.
By the second property of Corollary 6.2.8, $I_{c}(u)$ and $I_{c}(v)$ are not
trivial (and $n>1$). Therefore, $u$ and $v$ are two distinct vertices, each
with one of the forms as in Lemma 6.2.9. This is a contradiction by
Observation 6.2.10. ∎

######  Lemma 6.2.12.

Let $(u,v,w)$ be in $V_{i,j}$-position. Then

  1. 1.

$u$ and $v$ are the unique pair of vertices $(n-1,0,0,1,0,\dots,0)$ and
$(n-2,1,1,0,0,\dots,0)$, and $w=(n-1,0,1,0,0,\dots,0)$;

  2. 2.

if $n=1$, then $6\leq m$.

###### Proof.

By Lemma 6.2.11, $n^{0}(u)=n^{0}(v)=1$. We first prove that if $n=1$, then
$6\leq m$. Assume to the contrary that $n=1$ and $m\in\\{4,5\\}$. In this
case, there are precisely three vertices in $\mathrm{Y}_{n,m}$ which cover
only one vertex and that the covered vertex is obtained via a left unit shift:
$0_{\ell}$, $(0,1,1,0,\dots,0)$ and $(0,0,1,0,\dots,0)$. Therefore either
$u=(0,1,1,0,\dots,0)$ and $s_{i}=\overleftarrow{s}_{0}$ or
$u=(0,0,1,0,\dots,0)$ and $s_{i}=\overleftarrow{s}_{1}$, since $w\neq 0$. In
both cases, $n^{0}(v)=2$ for every possible $s_{j}$. A contradiction.

It is simple to verify that the pair of vertices given in this lemma indeed
satisfies the conditions of the lemma. Let $(u,v,w)$ be in $V_{i,j}$-position,
where $u$ and $v$ are any other pair of vertices. We show that $n^{0}(v)>1$.

Since $n^{0}(u)=1$ and $s_{i}(u)$ shifts left, every geodesic between $u$ and
$0$ contains only left unit shifts and $u$ consists of a sequence of $k\geq 1$
consecutive non-zero entries which are to be shifted into the left bucket in
every geodesic from $u$ to $0$ (including the case for $k=1$ where
$u=(u_{0},0,\dots,0,u_{m+1})$ with $0<u_{m+1}<\frac{n}{2}$).

If $k=1$, then $i\notin\\{0,2\\}$, since
$u\notin\\{0_{\ell},(n-1,0,0,1,0,\dots,0)\\}$. Clearly,
$s_{j}\in\\{s_{0},s_{m}\\}$ and in both cases, $n^{0}(v)=2$. Similarly, if
$k>1$, then it is simple to verify that $u=(n-2,1,1,0,0,\dots,0)$ is the only
case in which there exists $s_{j}$ such that $n^{0}(v)=1$. ∎

######  Observation 6.2.13.

By symmetric arguments to the ones in the proof of Lemma 6.2.12, if $s_{i}$
were to shift right in Definition 6.2.5, then the only pair of vertices for
which $n^{0}(u)=n^{0}(v)=1$ was $(0,\dots,0,1,0,0,n-1)$ and
$(0,\dots,0,0,1,1,n-2)$.

######  Observation 6.2.14.

If $f\in\operatorname{Aut}(\mathrm{Y}_{n,m})$, then there exist
$\alpha\in\\{0,\dots,n-1\\}$ and $\beta,\gamma\in\\{0,1\\}$ such that $0$,
$0_{\ell}$ and $0_{r}$ are fixed points of
$\pi=\psi^{\gamma}\tau^{\beta}\varphi^{\alpha}f$.

###### Proof.

A vertex in $\mathrm{Y}_{n,m}$ has valency $2$ if and only if all of its non-
bucket entries are equal to each other. Therefore, there exist
$\alpha\in\\{0,\dots,n-1\\}$ and $\beta\in\\{0,1\\}$ such that $0$ is a fixed
point of $\pi=\tau^{\beta}\varphi^{\alpha}f$. $0$ is also a fixed point of
$\psi$, and $\psi$ interchanges the only two neighbors of $0$; $0_{\ell}$ and
$0_{r}$. Therefore, there exists $\gamma\in\\{0,1\\}$ such that $0$,
$0_{\ell}$ and $0_{r}$ are fixed points of
$\pi=\psi^{\gamma}\tau^{\beta}\varphi^{\alpha}f$. ∎

######  Lemma 6.2.15.

Let $\pi\in\operatorname{Aut}(\mathrm{Y}_{n,m})$ such that $0$, $0_{\ell}$ and
$0_{r}$ are fixed points of $\pi$. Then $0_{1}$ and $0_{n-1}$ are also fixed
points of $\pi$.

###### Proof.

If $n=1$, then $0_{1}=0_{n-1}=0$, which is a fixed point of $\pi$. If $n>2$,
then $0_{1}$ and $0_{n-1}$ are the only (non zero) vertices of valency $2$
with a single geodesic between them and $0$. Therefore, $0_{1}$ and $0_{n-1}$
are either fixed or interchanged by $\pi$. Note that the geodesic between
$0_{1}$ and $0$ contains $0_{r}$ and doesn’t contain $0_{\ell}$ whereas the
geodesic between $0_{n-1}$ and $0$ contains $0_{\ell}$ and doesn’t contain
$0_{r}$. Therefore, $0_{1}$ and $0_{n-1}$ are fixed by $\pi$, since $0_{r}$
and $0_{\ell}$ are fixed by $\pi$.

Assume that $n=2$ and $m>3$. In this case, $0_{1}=0_{n-1}$ and there are four
vertices with valency $2$: $0,0_{1},1_{0}$ and $1_{1}$. Note that
$d(0_{1},0)=m+1$ and, by Observation 4.2.11 and Fact 4.2.12,
$d(1_{k},0)\geq\binom{\lfloor\frac{m}{2}\rfloor+1}{2}+\binom{\lceil\frac{m}{2}\rceil+1}{2}$
(for $k\in\\{0,1\\}$). Therefore, since $m>3$, $d(0_{1},0)<d(1_{k},0)$ for
both $k=0$ and $k=1$. This proves that $0_{1}$ is fixed by $\pi$.

The only case left is $n=2$ and $m=3$. Note that
$x=(1,1,0,1,1)\in\mathrm{Y}_{2,3}$ is fixed by $\pi$, since it is the only
vertex at distance $2$ from $0$ that is a neighbor of both $0_{\ell}$ and
$0_{r}$. Both vertices $1_{0}$ and $1_{1}$ are at distance $2$ from $x$
whereas the vertex $0_{1}$ is at distance $4$ from $x$. Therefore $0_{1}$ is
fixed by $\pi$. ∎

######  Lemma 6.2.16.

Let $n\geq 1$ and $m\geq 3$ be two integers such that $(n,m)\neq(1,3)$. Then
$\operatorname{Aut}(\mathrm{Y}_{n,m})=\mathscr{A}_{n,m}$.

###### Proof.

Let $f\in\operatorname{Aut}(\mathrm{Y}_{n,m})$. By Observation 6.2.14 and
Lemma 6.2.15, there exist integers $\alpha,\beta,\gamma$ such that $0$,
$0_{\ell}$, $0_{r}$, $0_{1}$ and $0_{n-1}$ are fixed points of
$\pi=\psi^{\gamma}\tau^{\beta}\varphi^{\alpha}f$. We show that $\pi$ is, in
fact, the trivial automorphism. Assume to the contrary that $\pi\neq Id$ and
let $u\in\mathrm{Y}_{n,m}$ be a vertex at minimal distance $d$ from $0$ such
that $u$ is not fixed by $\pi$. Denote $v=\pi(u)$. Note that
$N^{0}(u)=N^{0}(v)$, by the minimality of $d$, and let $w\in
N^{0}(u)=N^{0}(v)$. Note that $d\geq 2$ and therefore $w\neq 0$.

Let $0\leq i,j\leq m$ such that $s_{i}(u)=s_{j}(v)=w$, so that
$v=s_{j}s_{i}(u)$. Assume that $s_{i}$ shifts left (the proof of the other
case follows by symmetric arguments). Therefore, $(u,v,w)$ are in
$V_{i,j}$-position. By Lemma 6.2.12, $u$ and $v$ are the unique pair of
vertices $(n-1,0,0,1,0,\dots,0)$ and $(n-2,1,1,0,0,\dots,0)$; and if $n=1$,
then $6\leq m$.

If $m>3$, then $u$ and $v$ have different valencies, in contradiction to
$\pi(u)=v$. Finally, assume $m=3$ (and $n>1$). Then $u$ and $v$ are the pair
of vertices $u_{1}=(n-1,0,0,1,0)$ and $u_{2}=(n-2,1,1,0,0)$.

Since $0_{n-1}$ is a fixed point of $\pi$,
$d(u_{1},0_{n-1})=d(u_{2},0_{n-1})$. Therefore,

$d(\varphi(u_{1}),0)=d(\varphi(u_{1}),\varphi(0_{n-1}))=d(\varphi(u_{2}),\varphi(0_{n-1}))=d(\varphi(u_{2}),0).$

But $d(\varphi(u_{1}),0)=1$ and $d(\varphi(u_{2}),0)=3$. A contradiction. ∎

## References

  * [1]
  * [2] R. M. Adin, M. Firer and Y. Roichman, Triangle-free triangulations. Adv. in Appl. Math. 45 (2010), 77–95.
  * [3] G. Birkhoff, Lattice theory. Amer. Math. Soc, Colloquium Publications, vol. 25. Amer. Math. Soc., New York (1948).
  * [4] P. Bose and F. Hurtado, Flips in planar graphs. Comput. Geom. 42 (2009), 60–80.
  * [5] S. Elizalde and Y. Roichman, Arc permutations, J. Algebraic Combin. 39 (2014), 301–334.
  * [6] R. Fabila-Monroy, D. Flores-Penaloza, C. Huemer, F. Hurtado, D. R. Wood and J. Urrutia, On the chromatic number of some flip graphs. Discrete Math. Theor. Comput. Sci. 11 (2009), 47–56.
  * [7] J. E. Humphreys, Reflection groups and Coxeter groups. Cambridge Studies in Advanced Mathematics, Vol. 29. Cambridge University Press, Cambridge (1990).
  * [8] C. Keller and M. A. Perles, On the smallest sets blocking simple perfect matchings in a convex geometric graph. Israel J. Math. 187 (2012), 465–484.
  * [9] C. Keller and M. A. Perles, Characterization of co-blockers for simple perfect matchings in a convex geometric graph. Discrete Comput. Geom. 50 (2013), 491–502.
  * [10] Y. Khachatryan, Words, Groups and Graphs. M.Sc. Thesis, Bar-Ilan University (2015).
  * [11] Y. Khachatryan, Convex caterpillars are Schur-Positive. arXiv preprint arXiv:1812.09863 (2018).
  * [12] J. L. Martin, M. Morin, and J. D. Wagner, On distinguishing trees by their chromatic symmetric functions. J. Combin. Theory Ser. A 115 (2008), 237–253.
  * [13] H. Parlier and S. Zappa, Distances in domino flip graphs. Amer. Math. Monthly 124-8 (2017), 710–722.
  * [14] L. Pournin, The diameter of associahedra. Adv. Math. 259 (2014), 13–42.
  * [15] The Sage Developers, Sage Mathematics Software System, SageMath. (2017), http://www.sagemath.org.
  * [16] D. D. Sleator, R. E. Tarjan and W.P. Thurston, Rotation distance, triangulations, and hyperbolic geometry, J. Amer. Math. Soc. 1 (1988), 647–681.
  * [17] R. Stanley, Enumerative Combinatorics, vol. 1. Cambridge Studies in Advanced Mathematics, 49. Cambridge University Press, Cambridge (1997).