Séminaire Lotharingien de Combinatoire 79 (2020), Article B79f

FLIP GRAPHS, YOKE GRAPHS AND DIAMETER

ROY H. JENNINGS

Abstract. In this paper we introduce Yoke graphs, a family of flip graphs that generalizes several previously studied families of graphs: colored triangle free triangulations, arc permutations and caterpillars. Our main result is the computation of the diameter of an arbitrary Yoke graph.

1. Introduction

Over recent decades there has been an increasing interest in graphs on combinatorial objects in which the adjacency relation reflects a local change, for example, flip graphs (see [2, 4, 5, 11, 12, 14]). In this paper we introduce Yoke graphs, a family of flip graphs that generalizes previously studied families of graphs: colored triangle free triangulations [1] (CTFT), arc permutations [3] and geometric caterpillars [9].

The flip graph of triangulations of a convex polygon [14] inspired the definition of a few flip graphs on subsets of triangulations. One such graph is the CTFT graph. This graph is closely related to a distinguished lower interval in the weak order on the affine Weyl group { \atop C_{n}}. The diameter of this flip graph was calculated using lattice properties of the order, see [1].

An arc permutation in the symmetric group S_{n} is one in which every prefix (and suffix) forms an interval in ℤ_{n}. The flip graph of arc permutations is the subgraph induced by the set of arc permutations in the Cayley graph associated with S_{n}, S , where S is the generating set of S_{n} consisting of simple reflections. The diameter of the graph of arc permutations was computed using similarities between the graph and the dominance order on ℤ^{n}, see [3].

To define a geometric caterpillar, start with the complete graph K_{n} whose vertices are labeled by ℤ_{n}. Embed K_{n} in the plane such that its vertices form a convex polygon and its edges are straight line segments. Denote this geometric graph by K̂_{n}. A geometric caterpillar of order n is a non-crossing spanning tree of K̂_{n}, such that the vertices of its spine form an interval in ℤ_{n}. For a formal definition see [7]. Caterpillars are also called fishbones or combs and were studied by Keller, Perles, Sagan, Wachs and others in various contexts, see, e.g., [8, 10]. In the flip graph of geometric caterpillars, two caterpillars are adjacent if one is obtained from the other by moving an edge incident with a leaf along the spine. The problem of the diameter of the flip graph of geometric caterpillars is open.

The generalization (by Yoke graphs) of these three flip graphs is motivated by their surprising similarities in terms of algebraic, combinatorial and metric properties. In particular, they carry similar group actions, are intimately related to posets and have similar diameter formulas.

Supported by the Israel Science Foundation grant no. 1970/18.

Our main result, Theorem 2.3, is the computation of the diameter of an arbitrary Yoke graph. Since Yoke graphs generalize the flip graphs described above, this theorem provides a unified proof for the previous results. Our approach is different from the ones in [1] and [3]. At the heart of the proof lies the idea of transforming a diameter evaluation into an eccentricity problem.

2. Yoke Graphs

Definition 2.1. Let n 1 and m 0 be two integers. Denote the subset 0, 1 ℤ by P_{2}. The Yoke graph 𝒴_{n,m} is a graph with vertices corresponding to all u u_{0} …, u_{m 1} ℤ_{n} P_{2}^{m} ℤ_{n} such that _{i 0}^{m 1} u_{i} 0 mod n . Two vertices u and v are adjacent in 𝒴_{n,m}, denoted u v, if there exists 0 i m such that u_{j} v_{j} for every j 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.

Convention 2.2. Throughout this paper, elements (cosets) in a quotient group ℤ_{n} of ℤ are identified with their smallest non-negative representative in ℤ.

According to convention 2.2, the sum _{i 0}^{m 1} u_{i} in Definition 2.1 is a non-negative integer. Denote the vertex 0, …, 0 𝒴_{n,m} by 0. For an example of a Yoke graph see 𝒴_{3,3} in Figure 1.

Figure 1. 𝒴_{3,3}^{(01110) (01101) (01011) (00111) (21111) (21102) (21012) (20112) (11112) (11100) (11010) (10110) (10101) (11001) (20001) (20010) (20100) (21000) 0 (00012) (00102) (01002) (10002) (10011)}

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 will sometimes refer to the entries u_{0} and u_{m 1} of a vertex u in 𝒴_{n,m} as buckets.

As noted in the introduction, important special cases of yoke graphs include the following. The graph 𝒴_{n,n 4} is isomorphic to the CTFT graph. The map defined in [1, Definition 2.8] (which was used to calculate the cardinality of the CTFT graph) induces an isomorphism between this graph and 𝒴_{n,n 4}. The graph 𝒴_{n,n 2} is isomorphic to the flip graph of arc permutation. It can be verified that the encoding ψ, defined in [3, Section 6.2], induces an isomorphism between the graph of arc permutations and 𝒴_{n,n 2}. Similarly, it can be shown that 𝒴_{n,n 3} is isomorphic to the flip graph of geometric caterpillars.

Yoke graphs 𝒴_{n,m} are Schreier graphs of the affine Weyl group of type C̃_{m} whenever m 1. This fact is naturally extended from previously known results. For example, by [1, Proposition 3.2], the CTFT graph 𝒴_{n,n 4} is a Schreier graph of the affine Weyl group of type C̃_{n 4} for n 5. Also, by [3, Corollary 10.4], the arc permutations graph 𝒴_{n,n 2} is a Schreier graph of the affine Weyl group of type C̃_{n 2} for n 3. For more details see [6].

The main result of this paper is the following.

Theorem 2.3. If m n, then diam 𝒴_{n,m} \frac{n m 1}{2} .

If 1 n m, then diam 𝒴_{n,m}  _{2}^{\frac{m}{2} 1}  _{2}^{\frac{m}{2} 1} . Otherwise, 2 n m and

(1) if 2 m n or n \frac{m 1}{2} , then

diam 𝒴_{n,m} d_{n,m}^{0} {\frac{m n}{2} 1 \atop 2} {\frac{m n}{2} 1 \atop 2} ;

(2) otherwise,

diam 𝒴_{n,m} d_{n,m}^{0} n \frac{m 1}{2} .

The proof of Theorem 2.3 appears at the end of Subsection 5.2. At the heart of the proof lies the idea to convert the problem of computation of diameter to that of computation of eccentricity. Specifically, in Section 3, we introduce dYoke graphs 𝒵_{n,m}, which are closely related to Yoke graphs. In Section 4, we show that the diameter of 𝒴_{n,m} is equal to the eccentricity of 0 in 𝒵_{n,m}.

3. dYoke Graphs

As noted in Section 2, at the heart of the calculation of the diameter of 𝒴_{n,m} lies the idea of converting the diameter problem of one graph into an eccentricity problem in another graph. To this end, we introduce a family of graphs.

Definition 3.1. Let n 1 and m 0 be two integers. Denote the subset 1, 0, 1 ℤ by P_{3}. The dYoke graph 𝒵_{n,m} is a graph with vertices corresponding to all u u_{0} …, u_{m 1} ℤ_{n} P_{3}^{m} ℤ_{n} such that _{i 0}^{m 1} u_{i} 0 mod n . Two vertices u and v are adjacent in 𝒵_{n,m} if there exists 0 i m such that u_{j} v_{j} for every j 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.

Note that vertices in Yoke graphs and dYoke graphs are determined by their first (or last) m 1 entries, since _{i 0}^{m 1} u_{i} 0 mod n . We denote the vertex 0, …, 0 𝒵_{n,m} by 0. We will sometimes refer to the entries u_{0} and u_{m 1} of a vertex u in 𝒵_{n,m} as buckets, similarly to Yoke graphs. 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 i m, we say that u is obtained from v by shifting a unit from entry i 1 to the left, and write u \begin{matrix} \\ s \end{matrix}_{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 \begin{matrix} \\ s \end{matrix}_{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 𝒵_{5,3}, then \begin{matrix} \\ s \end{matrix}_{2} v 3, 0, 0, 0, 2 and \begin{matrix} \\ s \end{matrix}_{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.

If 1 k m and v_{k} 1, then a unit shift from entry k is not possible. Similarly, if v_{k} 1, then a unit shift to entry k not possible. However, for every i with 0 i m,\begin{matrix} \\ s \end{matrix}_{i} and \begin{matrix} \\ s \end{matrix}_{i} still induce functions from 𝒵_{n,m} to 𝒵_{n,m}, in which if a unit shift s_{i} v is not possible for some v 𝒵_{n,m}, then v is a fixed point of s_{i}. Denote the set \begin{matrix} \\ s \end{matrix}_{i},\begin{matrix} \\ s \end{matrix}_{i} 0 i m by _{n,m}. If m 0, then \begin{matrix} \\ s \end{matrix}_{0} and \begin{matrix} \\ s \end{matrix}_{0} are inverses of each other and _{n,0} generates the cyclic group ℤ_{n}. If m 0, then none of the functions in _{n,m} are bijective and _{n,m} generates a semigroup.

A word w in the letters _{n,m} is a sequence f_{d} f_{1} where f_{1}, …, f_{d} _{n,m}. Let P be a path v v^{0} v^{d} u in 𝒵_{n,m}. In this paper, when we write u v, it implies that u, v is an edge in the graph (and that u v, since the graphs in this paper have no loops). Clearly, there is a unique word f_{d} f_{1} such that f_{t} v^{t 1} v^{t} for 1 t d or, equivalently, f_{t} f_{1} v v^{t} for 1 t d. We say that f_{d} f_{1} is the word corresponding to the path P from v to u.

Let f_{d} f_{1} be the word corresponding to a path from v to u in 𝒵_{n,m}. If f_{d} f_{t 1}f_{t} f_{1} v f_{d} f_{t}f_{t 1} f_{1} v (changing the order of f_{t} and f_{t 1}), then we say that f_{t} and f_{t 1} relatively commute in (the path) f_{d} f_{1} v . Note that the fact that f_{t} and f_{t 1} relatively commute in f_{d} f_{1} v , does not imply that f_{t} and f_{t 1} commute (as elements in the semigroup generated by _{n,m}). For example, if f_{d} f_{1} corresponds to a path from v to u such that f_{t} \begin{matrix} \\ s \end{matrix}_{i} and f_{t 1} \begin{matrix} \\ s \end{matrix}_{i 1} for some 1 t d 1 and 0 i m 1, then f_{t} and f_{t 1} relatively commute in f_{d} f_{1} v (since a path has no repetitions and both f_{t} and f_{t 1} indeed shift a unit) but do not commute (in the semigroup). If, however, f_{t} and f_{t 1} commute, then they also relatively commute in f_{d} f_{1} v . Clearly, two distinct s_{i} and s_{j} in _{n,m} commute if and only if i j 1.

Lemma 3.2 (Shift Direction Lemma). Let f_{d} f_{1} be the word corresponding to a geodesic in 𝒵_{n,m}. For every i with 0 i m, all of the instances of s_{i} in f_{d} f_{1} shift in the same direction.

Proof. Let v and u be two vertices in 𝒵_{n,m}. If m 0, then a word corresponding to a geodesic from v to u is of the form f^{k} where f _{n,0} and 0 k \frac{n}{2} . Otherwise m 0. 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 . For every word f_{d} f_{1} in , there exist i, t_{1}, t_{2} with 0 i m and 1 t_{1}, t_{2} d such that f_{t_{1}} \begin{matrix} \\ s \end{matrix}_{i} and f_{t_{2}} \begin{matrix} \\ s \end{matrix}_{i}. Let w f_{d} f_{1} be a word in in which min t_{2} t_{1} f_{t_{1}} \begin{matrix} \\ s \end{matrix}_{i}, f_{t_{2}} \begin{matrix} \\ s \end{matrix}_{i} is minimal. Let 1 t_{1} t_{2} d be a pair of indices obtaining this minimum and assume without loss of generality that f_{t_{1}} \begin{matrix} \\ s \end{matrix}_{i} and f_{t_{2}} \begin{matrix} \\ s \end{matrix}_{i} where 0 i m.

If t_{2} t_{1} 1, then the word obtained by deleting both f_{t_{1}} and f_{t_{2}} from f_{d} f_{1} is a word corresponding to a path from v to u, contradicting the minimality of d. Therefore, we can assume that t_{2} t_{1} 1. Note that f_{t_{1}} does not relatively commute with f_{t_{1} 1} by the minimality of t_{2} t_{1} in the choice of w. Therefore we can assume that f_{t_{1} 1} \begin{matrix} \\ s \end{matrix}_{i 1},\begin{matrix} \\ s \end{matrix}_{i 1} (the only two elements in _{n,m} that do not necessarily relatively commute with f_{t_{1}}).

If f_{t_{1} 1} \begin{matrix} \\ s \end{matrix}_{i 1}, then we can assume that f_{t_{1} 1} f_{1} v _{i} 1, otherwise f_{t_{1}} and f_{t_{1} 1} relatively commute in f_{d} f_{1} v . Moreover, there must be some k with t_{1} 1 k t_{2} such that f_{k} \begin{matrix} \\ s \end{matrix}_{i 1}, since f_{t_{2}} \begin{matrix} \\ s \end{matrix}_{i}. Similarly, if f_{t_{1} 1} \begin{matrix} \\ s \end{matrix}_{i 1}, then we can assume that f_{t_{1} 1} f_{1} v _{i 1} 1 and there must be f_{k} \begin{matrix} \\ s \end{matrix}_{i 1} for some k with t_{1} 1 k t_{2}. Both cases contradicting the minimality of t_{2} t_{1}. □

4. From Diameter to Eccentricity

Recall that the eccentricity of a vertex v in a graph is the maximum distance between v and any other vertex. In this section, we show (Theorem 4.5) that the diameter of 𝒴_{n,m} is equal to the eccentricity of 0 in 𝒵_{n,m}. Every Yoke graph 𝒴_{n,m} is naturally embedded in the dYoke graph 𝒵_{n,m} as an induced subgraph on the vertices with no negative entries. Note that for every two vertices v, u 𝒴_{n,m}, the difference v u v_{0} u_{0}, …, v_{m 1} u_{m 1} is in 𝒵_{n,m}.

Definition 4.1. For every u 𝒴_{n,m} let φ_{u} 𝒴_{n,m} 𝒵_{n,m} be the map (on vertices) defined by φ_{u} v v u.

Observation 4.2. For every u 𝒴_{n,m}, φ_{u} is a graph isomorphism between 𝒴_{n,m} and the subgraph induced by φ_{u} 𝒴_{n,m} (in 𝒵_{n,m}).

The following lemma is essential for the proof of Lemma 4.4. We start with a given z 𝒵_{n,m} such that z_{i} 0 for some 1 i m, and a geodesic P between z and 0. We show that P can be transformed into a geodesic P^{}in which the ith 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 4.3. Let z 𝒵_{n,m} such that z_{i} 0 for some i with 1 i m and let P z x^{0} x^{1} x^{d} 0 be a geodesic between z and 0. Then a geodesic P^{}z y^{0} y^{1} y^{d} 0 exists such that:

(1) either y_{i}^{t} 0 for 0 t d or y_{i}^{t} 0 for 0 t d (P^{}can be constructed either way);

(2) y_{j}^{t} 0 t d x_{j}^{t} 0 t d for every j i where 0 j m 1.

Proof. We prove the existence of P^{}such that y_{i}^{t} 0 for 0 t d. The proof for the case y_{i}^{t} 0 follows by symmetric arguments. Let Q w^{0} w^{1} w^{l} be a path in 𝒵_{n,m}. Define O_{i} Q 0 t l w_{i}^{t} 1 . If O_{i} P 0, then set P^{}P. Otherwise, assume that O_{i} P 0. We show that there exists a geodesic Q z w^{0} w^{1} w^{d} 0 with the following properties:

(1) O_{i} Q O_{i} P .

(2) w_{j}^{t} 0 t d x_{j}^{t} 0 t d for every j i where 0 j m 1.

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

Let f_{d} f_{1} be the word corresponding to P. Note that by the Shift Direction Lemma 3.2, either both \begin{matrix} \\ s \end{matrix}_{i 1} and \begin{matrix} \\ s \end{matrix}_{i} or both \begin{matrix} \\ s \end{matrix}_{i 1} and \begin{matrix} \\ s \end{matrix}_{i} appear in f_{d} f_{1}, since x_{i}^{0} 0, x_{i}^{d} 0 and O_{i} P 0. Assume without loss of generality that both\begin{matrix} \\ s \end{matrix}_{i 1} and\begin{matrix} \\ s \end{matrix}_{i} appear in f_{d} f_{1}.

Let t_{1} be the minimal index such that x_{i}^{t_{1}} 1 and therefore f_{t_{1}} \begin{matrix} \\ s \end{matrix}_{i 1}. Let t_{2} be the minimal index such that t_{1} t_{2} and f_{t_{2}} \begin{matrix} \\ s \end{matrix}_{i} (such t_{2} exists since x_{i}^{d} 0). If t_{2} t_{1} 1, then f_{t_{1}} and f_{t_{2}} relatively commute in f_{d} 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} f_{1} is in the form

( )  f_{d} … f_{t_{2}}w_{2}w_{1}f_{t_{1}} … 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 exists t with 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} \begin{matrix} \\ s \end{matrix}_{i 1},\begin{matrix} \\ s \end{matrix}_{i} for every t with 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} … w_{2}f_{t_{1}}f_{t_{2}}w_{1} … 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 4.4. Let v, u 𝒴_{n,m}. Then d_{𝒴_{n,m}} v, u d_{𝒵_{n,m}} v u, 0 , where d_{G} v, u is the distance between v and u in the graph G.

Proof. By Observation 4.2, 𝒴_{n,m} is isomorphic to the induced subgraph φ_{u} 𝒴_{n,m} of 𝒵_{n,m}, implying that d_{𝒴_{n,m}} v, u d_{𝒵_{n,m}} φ_{u} v , φ_{u} u d_{𝒵_{n,m}} v u, 0 .

Let P v u x^{0} x^{1} x^{d} 0 be a geodesic between v u and 0 in 𝒵_{n,m}. Note that if x_{i}^{0} 0 for some 1 i m, then, by Lemma 4.3, there exists a geodesic P^{}v u y^{0} y^{1} y^{d} 0 such that y_{i}^{t} 0 for 0 t d (the lemma is applied to x^{k} x^{k 1} x^{d} 0 , where k is the first index such that x_{i}^{k} 0). Similarly, if x_{i}^{0} 0 for some 1 i m, then there exists a geodesic P^{}v u y^{0} y^{1} y^{d} 0 such that y_{i}^{t} 0 for 0 t d.

Therefore, by its second property, Lemma 4.3 can be applied iteratively to all 1 i m, to construct a geodesic P^{}v u y^{0} y^{1} y^{d} 0 from the geodesic P that satisfies the following conditions for every i with 1 i m:

(1) If u_{i} 1 (implying that v u _{i} 0), then y_{i}^{t} 0 for 0 t d.

(2) If u_{i} 0 (implying that v u _{i} 0), then y_{i}^{t} 0 for 0 t d. Clearly, v y^{0} u y^{1} u y^{d} u u is a path between v and u in 𝒴_{n,m}. Therefore d_{𝒴_{n,m}} v, u d_{𝒵_{n,m}} v u, 0 . □

Theorem 4.5. diam 𝒴_{n,m} ecc_{𝒵_{n,m}} 0 .

Proof. By Lemma 4.4, diam 𝒴_{n,m} ecc_{𝒵_{n,m}} 0 , since

d_{𝒴_{n,m}} v, u d_{𝒵_{n,m}} v u, 0

for each pair of antipodes (vertices at maximal distance) v and u in 𝒴_{n,m}. On the other hand, for every z 𝒵_{n,m} there exist v, u 𝒴_{n,m} such that v u z. Let z 𝒵_{n,m}. Construct v, u 𝒴_{n,m} as follows; for example,

(1) v_{0} z_{0} and u_{0} 0.

(2) For every i with 1 i m, v_{i} max 0, z_{i} and u_{i} max 0, z_{i} . Then, by Lemma 4.4, d_{𝒵_{n,m}} z, 0 d_{𝒵_{n,m}} v u, 0 d_{𝒴_{n,m}} v, u diam 𝒴_{n,m} , and therefore ecc_{𝒵_{n,m}} 0 diam 𝒴_{n,m} . This proves equality. □

5. The Eccentricity of 0 in 𝒵_{n,m}

In this section we compute the eccentricity of 0 in 𝒵_{n,m}. We prove that it is equal to the value of the diameter of 𝒴_{n,m} as it appears in Theorem 2.3.

Observation 5.1. If m 0, then 𝒵_{n,0} is merely a cycle graph on n vertices (n vertices connected in a closed chain). Therefore, ecc_{𝒵_{n,0}} 0 \frac{n}{2} \frac{n m 1}{2} , in accordance with Theorem 2.3 for the case m n. In the rest of this paper we consider only dYoke graphs in which m 0.

This section is composed of two subsections. In Subsection 5.1, we first introduce pivot paths and some related definitions. We then use them to compute the eccentricity of 0 when m n. In Subsection 5.2 we deal with the case n m.

5.1. Pivot Paths and the Case m n.

Definition 5.2 (Pivot). A pivot of a vertex v 𝒵_{n,m} is an integer p with 1 p m 1 such that _{i 0}^{p} v_{i} is divisible by n ( _{i j}^{k} v_{i} is defined as 0 whenever k j). We call 1 and m 1 the outer pivots of v (they are pivots of every v 𝒵_{n,m}), and every other pivot, if it exists, is called an inner pivot. Denote the set of pivots of v by Piv v .

For example, in 𝒵_{3,8}, Piv 0, 1, 1, 0, 1, 1, 1, 1, 1, 2 1, 0, 2, 3, 7, 9 .

Definition 5.3 (Wall). Let P be a path from v to 0 in 𝒵_{n,m} and let f_{d} f_{1} be the word corresponding to P. An inner wall of P is an integer p with 0 p m such that s_{p} does not appear in f_{d} f_{1}. If\begin{matrix} \\ s \end{matrix}_{0} does not appear in f_{d} f_{1}, then 1 is the left outer wall of P. Similarly, if \begin{matrix} \\ s \end{matrix}_{m} does not appear in f_{d} f_{1}, then m 1 is the right outer wall of P. We say that an integer p with 1 p m 1 is a wall of P if it is either an inner wall or an outer wall of P.

Definition 5.4 (Pivot Path). We say that a path P from v to 0 in 𝒵_{n,m} is a p-pivot path (or simply a pivot path) of v, if P is a shortest path with a wall p (not necessarily a geodesic) from v to 0. Denote the length of a p-pivot path of v by σ_{p} v .

Clearly, p-pivot paths of v exist if and only if p Piv v .

Observation 5.5. Every inner pivot p of v 𝒵_{n,m} induces a path from v to 0 of length _{i 1}^{p} i v_{i} _{i p 1}^{m} m 1 i v_{i} . It is a path in which the entries v_{1}, …, v_{p} and v_{p 1}, …, v_{m} 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}. Therefore

σ_{p} v _{i 1}^{p} i v_{i} _{i p 1}^{m} m 1 i v_{i} _{i 1}^{p} i _{i 1}^{m p} i.

The proof of the Shift Direction Lemma 3.2 can be slightly modified so that the lemma applies to pivot paths.

Lemma 5.6 (Pivot Shift Direction Lemma). Let f_{d} f_{1} be the word corresponding to a pivot path in 𝒵_{n,m}. For every i with 0 i m, all of the instances of s_{i} in f_{d} f_{1} shift in the same direction.

Lemma 5.7. Every geodesic between every vertex and 0 in 𝒵_{n,m} is a pivot path.

Proof. Let w f_{d} f_{1} be the word corresponding to a geodesic P from v 𝒵_{n,m} to 0. Assume to the contrary that P has no walls. By the Shift Direction Lemma 3.2, exactly one of \begin{matrix} \\ s \end{matrix}_{i},\begin{matrix} \\ s \end{matrix}_{i} appears in w for every i with 0 i m. Both\begin{matrix} \\ s \end{matrix}_{0} and\begin{matrix} \\ s \end{matrix}_{m} appear in w, since it has no outer walls. Therefore both\begin{matrix} \\ s \end{matrix}_{i 1} and\begin{matrix} \\ s \end{matrix}_{i} appear in w where 1 i m is minimal such that\begin{matrix} \\ s \end{matrix}_{i} is in w. A contradiction to f_{d} f_{1} v _{i} 0. □

Fact 5.8. Let m, p, q be integers such that 0 p m and 0 q m and p \frac{m}{2} q \frac{m}{2} . Then _{i 0}^{p} i _{i 0}^{m p} i _{i 0}^{q} i _{i 0}^{m q} i.

Observation 5.9. If n 1, then Piv v 1, …, m 1 for every v 𝒵_{n,m}. Therefore, by Observation 5.5 and Fact 5.8, ecc_{𝒵_{1,m}} 0 _{i 1}^{\frac{m}{2}}i _{i 1}^{\frac{m}{2}}i. Let v 𝒵_{1,m} such that v_{i} 1 for every i with 1 i m. Clearly, σ_{1} v σ_{m 1} v _{2}^{m 1} and σ_{p} v _{i 1}^{p} i _{i 1}^{m p} i

for 0 p m. Therefore, by Lemma 5.7 and Fact 5.8, d v, 0 _{i 1}^{\frac{m}{2}}i _{i 1}^{\frac{m}{2}}i. This proves that ecc_{𝒵_{1,m}} 0 _{2}^{\frac{m}{2} 1} _{2}^{\frac{m}{2} 1} , in accordance with Theorem 2.3 for the case 1 n m. In the rest of this paper we consider only dYoke graphs in which n 1.

Definition 5.10 (P -interval). Let P be a pivot path of v and let p_{1}, …, p_{t} with 1 p_{1} … p_{t} m 1 be the set of inner walls of P. Write p_{0} 1, p_{t 1} m 1 and P iv P p_{0}, p_{1}, …, p_{t}, p_{t 1} . Note that Piv P Piv v . We call every p Piv P a pivot of P. Piv P induces t 1 intervals p_{k} 1, p_{k 1} for 0 k 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 I.

Lemma 5.11. Let f_{d} f_{1} be the word corresponding to a pivot path P of v and let I be a P -interval. Then, if i, i 1 I and j, j 1 I, the instances of s_{i} and s_{j} in f_{d} f_{1} shift in the same direction.

Proof. By the Pivot Shift Direction Lemma 5.6, exactly one of \begin{matrix} \\ s \end{matrix}_{i},\begin{matrix} \\ s \end{matrix}_{i} appears in f_{d} f_{1}, for i, i 1 I. Assume to the contrary, without loss of generality, that both \begin{matrix} \\ s \end{matrix}_{i} and\begin{matrix} \\ s \end{matrix}_{j}, appear in f_{d} f_{1} for i j in I. Let k I such that i k and k is minimal such that s_{k} appears shifting right in f_{d} f_{1}. Therefore both \begin{matrix} \\ s \end{matrix}_{k 1} and \begin{matrix} \\ s \end{matrix}_{k} appear in f_{d} f_{1}. Note that 1 k m. A contradiction to f_{d} f_{1} v _{k} 0. □

Definition 5.12 (d_{I} P ). By Lemma 5.11, all of the unit shifts between entries in the same P -interval I are in the same direction throughout P. If the direction of these shifts is left (right), we say that P shifts left (right) in I. Denote the number of unit shifts between entries in some interval I 0, m 1 within a pivot path P by d_{I} P .

Lemma 5.13. Let I p_{1} 1, p_{2} be a P -interval of some pivot path P of v 𝒵_{n,m}. If I contains one of the buckets, assume also that no step in P shifts a unit from an empty bucket (i.e. \begin{matrix} \\ s \end{matrix}_{m} …, 0 …, n 1 and\begin{matrix} \\ s \end{matrix}_{0} 0, … n 1, … do not appear in P). Then

(1) If P shifts left in I, then d_{I} P _{i I} iv_{i}.

(2) If P shifts right in I, then d_{I} P _{i I} m 1 i v_{i}.

Proof. Note that, by Lemma 5.11, P shifts either right or left in I. Assume that P shifts left in I (the proof of the second case follows by symmetric arguments). Note that every left unit shift in P between entries in I reduces the value of the sum _{i I} iv_{i} exactly by 1, since a unit is never shifted left from an empty right bucket. Therefore

i I iv_{i} 0 and d_{I} P  _{i I} iv_{i}.  □

Lemma 5.14. Let I p_{1} 1, p_{2} be a P -interval of some pivot path P of v 𝒵_{n,m}.

(1) Assume that p_{2} m 1 and that P shifts left in I. If _{i j}^{m 1} v_{i} 0 for every j I, then there is no left unit shift in P from an empty right bucket.

(2) Assume that p_{1} 1 and that P shifts right in I. If _{i 0}^{j} v_{i} 0 for every j 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 _{i 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 _{i 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.

Assume 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 I, since, in this case, a left unit shift between entries in I cannot decrease the sum _{i 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. The assumption that _{i j}^{m 1} v_{i} 0 implies that _{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 _{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. This proves the claim. □

Lemma 5.15. If Piv v  1, m 1 for some v 𝒵_{n,m}, then σ_{m 1} v  _{i 0}^{m 1} iv_{i},

σ_{1} v _{i 0}^{m 1} m 1 i v_{i} and d v, 0 \frac{n m 1}{2} .

Proof. Note that, by Convention 2.2, 0 v_{0}, v_{m 1} n and _{i 0}^{m 1} v_{i} n since Piv v 1, m 1 . The assumption Piv v 1, m 1 also implies that both _{i 0}^{j} v_{i} 0 and _{i j}^{m 1} v_{i} 0 for 0 j m 1. Therefore σ_{m 1} v _{i 0}^{m 1} iv_{i} and σ_{1} v _{i 0}^{m 1} m 1 i v_{i} by Lemmas 5.13 and 5.14.

Clearly _{i 0}^{m 1} iv_{i} _{i 0}^{m 1} m 1 i v_{i} m 1 _{i 0}^{m 1} v_{i} n m 1 . Therefore, by

Lemma 5.7, d v, 0 min σ_{1} v , σ_{m 1} v  \frac{σ_{1} v σ_{m 1} v}{2}  \frac{n m 1}{2} .  □

Lemma 5.16. For every dYoke graph 𝒵_{n,m} we have ecc_{𝒵_{n,m}} 0 \frac{n m 1}{2} .

Proof. Let u 𝒵_{n,m} be defined as follows: u_{0} u_{m 1} \frac{n}{2} . If n is even, then u_{i} 0 for all 1 i m and if n is odd, then u_{\frac{m 1}{2}} 1 and u_{i} 0 for all other 1 i m. In all of these

cases, Piv u  1, m 1 . Therefore, by Lemma 5.15, σ_{m 1} u  _{i 0}^{m 1} iu_{i}  \frac{n m 1}{2}
and σ_{1} u  _{i 0}^{m 1} m 1 i u_{i}  \frac{n m 1}{2} . It follows that ecc_{𝒵_{n,m}} 0 d u, 0
min σ_{m 1} u , σ_{1} u  \frac{n m 1}{2} .  □

Theorem 5.17. If m n, then ecc_{𝒵_{n,m}} 0 \frac{n m 1}{2} .

Proof. By Lemma 5.16, it is sufficient to show that ecc_{𝒵_{n,m}} 0 \frac{n m 1}{2} . Let v 𝒵_{n,m}. By Lemma 5.15, we can assume that v has some inner pivot p Piv v . By Observation 5.5 and Fact 5.8, d v, 0 _{i 0}^{p} i _{i 0}^{m p} i _{2}^{m 1} . Since m n, _{n}^{m 1}

\frac{n m 1}{2} and therefore _{2}^{m 1}  \frac{n m 1}{2} .  □

5.2. The Case n m. In this subsection we calculate the eccentricity of 0 in 𝒵_{n,m} in the case n m. Throughout this subsection we assume that 2 n m. For v 𝒵_{n,m} we introduce the following notations:

(1) p_{l} v max p Piv v p \frac{m}{2} .

(2) p_{r} v min p Piv v p \frac{m}{2} .

(3) I_{c} v p_{l} v 1, p_{r} v .

(4) h v min p \frac{m}{2} p Piv v .

(5) η_{n,m} \begin{matrix}\frac{n}{2}, & if 2 m n , \\ \frac{n 1}{2} , & if 2 m n . \end{matrix}

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

Definition 5.18. Let μ 𝒵_{n,m} 𝒵_{n,m} be the automorphism of 𝒵_{n,m} defined by μ v _{i} v_{i} for 0 i m 1.

Observation 5.19. Let v 𝒵_{n,m} such that _{i I_{c}} v_{i} n. Recall that, by Convention 2.2, the buckets are identified with non-negative integers. Therefore I_{c} 1, m and i I_{c} μ v _{i} n.

The outline of this subsection is as follows. We first construct two candidates for an antipode of 0 in Definitions 5.20 and 5.21 and compute their distance from 0 in Lemma 5.22. Then we prove that the maximal value of the two distances, is an upper bound on the distance of an arbitrary vertex v in 𝒵_{n,m} from 0. We split this proof into three cases. Note that by Observation 5.19, we can assume that _{i I_{c}} v_{i} 0, n , since 0 is a fixed point of μ.

(1) h v η_{n,m} (Lemma 5.24).

(2) h v η_{n,m} and _{i I_{c} v} v_{i} n (Lemma 5.27).

(3) h v η_{n,m} and _{i I_{c} v} v_{i} 0 (Lemma 5.30).

Definition 5.20 (u_{n,m}^{0}). Let u 𝒵_{n,m} such that u_{i} 1 for all i with 1 i m and u_{0} \frac{m n}{2} mod n. Denote this vertex by u_{n,m}^{0} and write d_{n,m}^{0} d u_{n,m}^{0}, 0 .

For example, u_{3,5}^{0} 2, 1, 1, 1, 1, 1, 2 and u_{3,6}^{0} 2, 1, 1, 1, 1, 1, 1, 1 .

Definition 5.21 (u_{n,m}^{1}). Let n and m be two integers such that 2 n m and 2 m n . Let u 𝒵_{n,m} such that u_{i} 0 for i \frac{m 1}{2} , u_{i} 1 for all i with 1 i m and u_{0} \frac{m n}{2} mod n. Denote this vertex by u_{n,m}^{1} and write d_{n,m}^{1} d u_{n,m}^{1}, 0 .

For example, u_{2,5}^{1} 1, 1, 1, 0, 1, 1, 1 and u_{3,6}^{1} 2, 1, 1, 1, 0, 1, 1, 2 .

Lemma 5.22.

(1) d_{n,m}^{0}  _{2}^{\frac{m n}{2} 1}  _{2}^{\frac{m n}{2} 1} .
(2) d_{n,m}^{1}  _{2}^{\frac{m n}{2} 1}  _{2}^{\frac{m n}{2} 1}  \frac{m 1}{2} (for n m such that 2 m n ).
Proof. (1) By Lemma 5.13, σ_{p} u_{n,m}^{0}  _{i 0}^{p} i _{i 0}^{m p} i _{2}^{p 1}  _{2}^{m p 1} for every inner
pivot p of u_{n,m}^{0}. Note that p_{l} u_{n,m}^{0}  \frac{m n}{2} and p_{r} u_{n,m}^{0}  \frac{m n}{2} , implying that

p_{r} \frac{m}{2} p_{l} \frac{m}{2} . Note also, that the length of an outer pivot path is at

least _{2}^{m 1} . Therefore, and by Lemma 5.7 and Fact 5.8, d_{n,m}^{0} σ_{p_{r}} u_{n,m}^{0}
_{2}^{p_{r} 1}  _{2}^{m p_{r} 1}  _{2}^{\frac{m n}{2} 1}  _{2}^{\frac{m n}{2} 1} .

(2) Note that p_{l} u_{n,m}^{1}  \frac{m n}{2} and p_{r} u_{n,m}^{1}  \frac{m n}{2} . Therefore, in this case,

p_{r} \frac{m}{2} p_{l} \frac{m}{2} and by Definition 5.21, σ_{p_{r}} u_{n,m}^{1} σ_{p_{l}} u_{n,m}^{1} , since the entry

equal to 0 in I_{c} is indexed by \frac{m 1}{2} . This implies that d_{n,m}^{1} σ_{p_{r}} u_{n,m}^{1}
_{2}^{\frac{m n}{2} 1}  _{2}^{\frac{m n}{2} 1}  \frac{m 1}{2} . □

Definition 5.23 (d_{n,m}). Define

d_{n,m} \begin{matrix}d_{n,m}^{0}, & if 2 m n , \\ max d_{n,m}^{0}, d_{n,m}^{1} , & if 2 m n . \end{matrix}

Lemma 5.24. Let v 𝒵_{n,m} such that h v η_{n,m}. Then d v, 0 d_{n,m}^{0} d_{n,m}.

Proof. Let p^{}be an inner pivot of v for which p^{}\frac{m}{2} h v . By Observation 5.5, d v, 0 _{i 1}^{p^{}}i _{i 1}^{m p^{}}i. Note that if 2 m n , then h u_{n,m}^{0} η_{n,m}, and if 2 m n , then h u_{n,m}^{0} η_{n,m} 1. Therefore h v h u_{n,m}^{0} . By the proof of Lemma 5.22, d_{n,m}^{0} _{i 1}^{p} i _{i 1}^{m p} i for p Piv u_{n,m}^{0} for which p \frac{m}{2} h u_{n,m}^{0} . Therefore, by Fact 5.8, d v, 0 d_{n,m}^{0}, since p^{}\frac{m}{2} p \frac{m}{2} . □

The following lemma generalizes the part in Lemma 5.15 which states that if Piv v 1, m 1 for some v 𝒵_{n,m}, then d v, 0 \frac{n m 1}{2} .

Lemma 5.25. Let v 𝒵_{n,m} such that _{i I_{c}} v_{i} n. Then d v, 0 _{i 1}^{p_{l}} i _{i 1}^{m p_{r}} i \frac{n m 1}{2} .

Proof. _{i 1}^{p_{l}} i _{i 1}^{m p_{r}} i is an upper bound on the number of steps needed to set to 0 every v_{i} not in I_{c}. We can therefore assume that v_{i} 0 for every i I_{c} and prove that d v, 0 \frac{n m 1}{2} . Since _{i 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 _{i I_{c}} v_{i} n implies that _{i j}^{p_{r}} v_{i} 0 for every j I_{c} and _{i p_{l} 1}^{j} v_{i} 0 for every j I_{c}. Therefore, by Lemmas 5.13

and 5.14, d v, 0 min σ_{p_{l}} v , σ_{p_{r}} v  \frac{_{i Ic} iv_{i} _{i Ic} m 1 i v_{i}}{2}  \frac{n m 1}{2} .  □

Observation 5.26. If 2 m n and v u_{n,m}^{0}, then _{i I_{c}} iv_{i} _{i I_{c}} m 1 i v_{i}. Moreover, if v u_{n,m}^{1}, then _{i I_{c}} iv_{i} _{i I_{c}} m 1 i v_{i} 1. Therefore, the following is implied by the proofs of Lemmas 5.22 and 5.25.

(1) If 2 m n , then d_{n,m}^{0}  i 1^{\frac{m n}{2}} i _{i 1}^{m \frac{m n}{2}} i \frac{n m 1}{2} .

(2) d_{n,m}^{1} _{i 1}^{\frac{m n}{2}}i _{i 1}^{m \frac{m n}{2}} i \frac{n m 1}{2} .

Lemma 5.27. Let v 𝒵_{n,m} such that h v η_{n,m} and _{i I_{c} v} v_{i} n. Then d v, 0 d_{n,m}.

Proof. Assume that 2 m n . By Observation 5.26, d_{n,m} d_{n,m}^{0}  i 1^{\frac{m n}{2}} i _{i 1}^{m \frac{m n}{2}} i

\frac{n m 1}{2} . By Lemma 5.25, d v, 0 _{i 1}^{p_{l}} i _{i 1}^{m p_{r}} i \frac{n m 1}{2} . Note that both p_{l} \frac{m n}{2} and

p_{r} \frac{m n}{2} , since h v η_{n,m}. Therefore d_{n,m} d v, 0  i p_{l} 1^{\frac{m n}{2}} i _{i \frac{m n}{2} 1}^{p_{r}} m 1 i 0.

Otherwise assume that 2 m n . By Observation 5.26, d_{n,m} d_{n,m}^{1} _{i 1}^{\frac{m n}{2}}i

_{i 1}^{m \frac{m n}{2}} i \frac{n m 1}{2} . By Lemma 5.25, d v, 0 _{i 1}^{p_{l}} i _{i 1}^{m p_{r}} i \frac{n m 1}{2} . Note that both p_{l} \frac{m n}{2} and p_{r} \frac{m n}{2} , since h v η_{n,m}. Therefore d_{n,m} d v, 0 _{i p_{l} 1}^{\frac{m n}{2}}i _{i \frac{m n}{2} 1}^{p_{r}} m 1 i 0. □

Lemma 5.28. Let v 𝒵_{n,m} such that I_{c} v 1, m and _{i I_{c} v} v_{i} 0. Then

d v, 0 _{i 1}^{p_{l}} i _{i 1}^{m p_{r}} i \frac{γ}{2} \frac{γ}{2}

where γ I_{c} v .

Proof. As in the beginning of the proof of Lemma 5.25, we can assume that v_{i} 0 for every i I_{c} and prove that d v, 0 \frac{γ}{2} \frac{γ}{2} .

Let P be any p_{l}- or p_{r}-pivot path of v. I_{c} is clearly a P -interval, since _{i I_{c}} v_{i} 0 and I_{c} v 1, m . Assume without loss of generality, that P shifts left in I_{c}. By Lemma 5.13, d_{I_{c}} P _{i 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 _{i I_{c}} v_{i} 0. I_{c} contains at most \frac{γ}{2} entries equal to 1 and the same number of entries equal to 1. The maximum value of _{i I_{c}} iv_{i} is obtained when the first \frac{γ}{2} entries in I_{c} are equal to 1 and the last \frac{γ}{2}

entries are equal to 1. Therefore _{i I_{c}} iv_{i}  \frac{γ}{2} \frac{γ}{2} .  □

Fact 5.29. Let a and b be two positive integers. Then _{i 1}^{a} i _{i 1}^{b} i \frac{a b}{2} \frac{a b}{2} .

Lemma 5.30. Let v 𝒵_{n,m} such that h v η_{n,m} and _{i I_{v}} v_{i} 0. Then d v, 0 d_{n,m}.

Proof. If both p_{l} and p_{r} are outer pivots, then both buckets are non-empty and _{i I_{v}} v_{i} n, since, in this case, v has no pivots other than p_{l} and p_{r}. Contradicting the assumption i I_{v} v_{i} 0. Assume that one of p_{l}, p_{r} , say p_{l}, is an outer pivot (and that the other pivot, p_{r}, is an inner pivot). Let μ be the automorphism of 𝒵_{n,m} in Definition 5.18. Note that by Convention 2.2, if a bucket of v 𝒵_{n,m} is non-empty (and positive), then it is also non-empty (and positive) in μ v . Moreover, I_{c} v I_{c} μ v . This implies that _{i I_{c} μ v} μ v _{i} n. Therefore, since 0 is a fixed point of μ, by Lemma 5.27, d v, 0 d μ v , 0 d_{n,m} as required.

Otherwise I_{c} v 1, m . By Lemma 5.28, d v, 0 _{i 1}^{p_{l}} i _{i 1}^{m p_{r}} i \frac{γ}{2} \frac{γ}{2} where γ I_{c} v . Let p \frac{m n}{2} so that d_{n,m}^{0} _{i 1}^{p} i _{i 1}^{m p} i. Note that p \frac{m}{2} η_{n,m}. By assumption, p_{l} p p_{r}. Therefore

d_{n,m} d v, 0 d_{n,m}^{0} d v, 0 _{i p_{l} 1}^{p} i _{i m p_{r} 1}^{m p} i \frac{γ}{2} \frac{γ}{2} .

_{i p_{l} 1}^{p} i _{i m p_{r} 1}^{m p} i _{i 1}^{p p_{l}} i _{i 1}^{p_{r} p} i. Let a p p_{l}, let b p_{r} p and note that a b γ.

Therefore, by Fact 5.29, d_{n,m} d v, 0  _{i 1}^{a} i _{i 1}^{b} i \frac{γ}{2} \frac{γ}{2} 0.  □

Theorem 5.31. Let n, m be two integers where 2 n m. If 2 m n or n \frac{m 1}{2} , then

ecc_{𝒵_{n,m}} 0 d_{n,m}^{0} {\frac{m n}{2} 1 \atop 2} {\frac{m n}{2} 1 \atop 2} .

Otherwise,

ecc_{𝒵_{n,m}} 0 d_{n,m}^{1} d_{n,m}^{0} n \frac{m 1}{2} .

Proof. Note that if 2 m n , then, by Lemma 5.22, d_{n,m}^{1} d_{n,m}^{0} n \frac{m 1}{2} . Therefore, the theorem merely states that ecc_{𝒵_{n,m}} 0 d_{n,m} when n m. By Lemma 5.22, ecc_{𝒵_{n,m}} 0 d_{n,m}.

Let v 𝒵_{n,m}. By Observation 5.19, we can assume that _{i I_{c}} v_{i} 0, n , since 0 is a fixed point of the automorphism μ in Definition 5.18. Therefore, by Lemmas 5.24, 5.27 and 5.30, d v, 0 d_{n,m} and ecc_{𝒵_{n,m}} 0 d_{n,m}. □

At this point, we can combine our results to prove the main theorem of this paper.

Proof of Theorem 2.3. By Theorem 4.5, for every Yoke graph 𝒴_{n,m}, the diameter of 𝒴_{n,m} is equal to the eccentricity of 0 in the corresponding dYoke graph 𝒵_{n,m}.

In Observations 5.1, 5.9 and Theorems 5.17, 5.31, the eccentricity of 0 in 𝒵_{n,m} is shown to be equal to the value of the diameter of 𝒴_{n,m} as stated in this theorem. □

6. Additional Problems

A simpler version of the calculation of ecc_{𝒵_{n,m}} 0 can be used to calculate ecc_{𝒴_{n,m}} 0 and show that ecc_{𝒴_{n,m}} 0 ecc_{𝒵_{n,m}} 0 . Therefore a direct proof that 0 is an antipode in 𝒴_{n,m} might provide a shorter proof for the diameter of 𝒴_{n,m}.

Question 6.1. Is it possible to show, without using 𝒵_{n,m}, that 0 is an antipode in 𝒴_{n,m}?

It stands out that the three examples of flip graphs that motivated the definition of Yoke graphs and this paper, are all Yoke graphs that belong to the case m n.

Question 6.2. Are there any ”interesting” examples of Yoke graphs for the case n m?

7. Acknowledgments

This work is part of the author’s Ph.D. thesis written under the supervision of Prof. Ron M. Adin and Prof. Yuval Roichman. The author would like to thank Dr. Luie Jennings, Dr. Menachem Shlossberg and Dr. Arnon Netzer for many helpful discussions and suggestions.

References

[1] R.M. Adin, M. Firer and Y. Roichman. Triangle-free triangulations. Adv. in Appl. Math. 45 (2010), 77–95.

[2] P. Bose and F. Hurtado, Flips in planar graphs. Comput. Geom. 42 (2009), 60–80.

[3] S. Elizalde and Y. Roichman, Arc permutations, J. Algebraic Combin. 39 (2014), 301–334.

[4] R. Fabila-Monroy, D. Flores-Peñaloza, C. Huemer, F. Hurtado, D.R. Wood and J. Urrutia. On the chromatic number of some flip graphs. Discrete Math. Theoret. Computer Sci. 11 (2009), 47–56.

[5] R.H. Jennings, Geodesics in a graph of perfect matchings, Sém. Lothar. Combin. 74 (2017): B74e.

[6] R.H. Jennings, Ph.D. Thesis, Bar-Ilan University, in preparation.

[7] 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.

[8] 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.

[9] Y. Khachatryan, Words, Groups and Graphs. M.Sc. Thesis, Bar-Ilan University, 2015.

[10] 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.

[11] H. Parlier and S. Zappa, Distances in domino flip graphs. Amer. Math. Monthly 124-8 (2017), 710–722.

[12] L. Pournin. The diameter of associahedra. Adv. in Math. 259 (2014), 13–42.

[13] The Sage Developers, Sage Mathematics Software System, SageMath. 2017,

   http://www.sagemath.org.

[14] D.D. Sleator, R.E. Tarjan and W.P. Thurston, Rotation distance, triangulations, and hyperbolic geometry, J. Amer. Math. Soc. 1 (1988), 647–681.

Department of Mathematics, Bar-Ilan University, Israel

Email address: royh.jennings@gmail.com