# Surjective polymorphisms of
directed reflexive cycles

Isabelle Larivière  ,  Benoît Larose  and  David Emmanuel Pazmiño Pullas

###### Abstract.

A reflexive cycle is any reflexive digraph whose underlying undirected graph
is a cycle. Call a relational structure Słupecki if its surjective
polymorphisms are all essentially unary. We prove that all reflexive cycles of
girth at least 4 have this property.

##  1\. Introduction

Surjective polymorphisms of finite relational structures play a central role
in the study of the algorithmic complexity of quantified contraint
satisfaction problems (see for instance [1, 13, 8]). In this paper we focus on
the surjective polymorphisms of reflexive digraphs. These relational
structures are general enough to encode a wide range of computational problems
(see for instance [5]), and on the other hand support a rich categorical
structure: to each reflexive digraph one may naturally associate a simplicial
complex which gives some information on the nature of the polymorphisms of the
digraph [10]. For instance, it is known that if the $k$-th homotopy group of
the complex is non-trivial for some $k\geq 1$ but all of the proper retracts
of the digraph have trivial $k$-th homotopy group, then the digraph has only
trivial idempotent polymorphisms [6]. In particular, any digraph whose
simplicial complex triangulates a sphere has this property, among them
truncated Boolean lattices, the directed 3-cycle and all cycles of girth at
least 4.

Let us call a relational structure Słupecki if all its surjective
polymorphisms are essentially unary. Such structures are known to have Pspace-
complete QCSP [1]; since in particular their idempotent polymorphisms are
projections, if one considers the analogous problem with added unary
relations, the CSP is NP-complete. The following question follows naturally
from the previous discussion: Which reflexive digraphs are Słupecki ?  In a
companion paper [9] we investigate this and related questions; the present
paper focuses on cycles, which triangulate 1-spheres. By reflexive cycle, we
mean any reflexive digraph whose underlying undirected graph is a cycle; this
allows for any orientation of edges and symmetric edges as well. Our main
result is the following:

######  Theorem 1.1.

Let $n\geq 4$, and let $\mathbb{G}$ be a reflexive $n$-cycle. Then
$\mathbb{G}$ is Słupecki.

Some very special cases were known previously: directed cycles (a special case
of a result of Fearnley [4]), and alternating cycles of even length (i.e.
posets called crowns) (Demetrovics and Ronyai [3]).

The strategy is as follows. Let $\mathbb{G}$ be an $n$-cycle with $n\geq 4$.
Suppose there exists an onto polymorphism of $\mathbb{G}$ which is not
essentially unary. Then it follows easily from the relational description of
the Słupecki clone (Lemma 3.2) that there exists an onto homomorphism from
$\prod_{i}\mathbb{Q}_{i}$ onto $\mathbb{G}$ where the $\mathbb{Q}_{i}$ are
induced subpaths of $\mathbb{G}$ of length at most $n-2$. This property
motivates the following definition: we say that the $n$-cycle $\mathbb{G}$
satisfies the path condition if there exists no homomorphism from a product of
subpaths of $\mathbb{G}$ of length at most $n-2$ onto $\mathbb{G}$ (Definition
3.1); obviously a cycle with the path condition is Słupecki (Lemma 3.3). So
the rest of the paper consists of (1) characterising which cycles fail the
path condition, and then (2) showing these are also Słupecki. To achieve (1),
which is the most technically involved result of this paper, we first prove
that if $\mathbb{G}$ fails the path condition, then in fact there exists a
homomorphism from a product of subpaths of $\mathbb{G}$ of length at most
$n-2$ to $\mathbb{G}$ whose image misses an arc of $\mathbb{G}$, i.e. is onto
a subpath $\mathbb{P}$ of $\mathbb{G}$ of length $n-1$ (Theorem 3.8). This
turns the problem into a purely combinatorial question on words since
existence of a homomorphism to a path is purely metric (Theorem 3.9). We thus
obtain a description of cycles failing the path condition (Theorem 4.2). It
follows from this characterisation that these cycles contain a self-dual path
$\mathbb{P}$ of length $n-1$ that contains at least two symmetric edges. We
then invoke a criterion from our companion paper [9] to prove that any such
cycle is Słupecki (Theorem 5.4.)

Acknowledgments. We wish to thank Hubie Chen and Barnaby Martin for useful
discussions. We acknowledge the help of Francis Clavette, Marc Scattolin and
Jakob Thibodeau for computations.

##  2\. Preliminaries: notation, definitions, etc.

###  2.1. Reflexive digraphs

A digraph $\mathbb{G}=\langle G;E\rangle$ consists of a non-empty set $G$ of
vertices and a binary relation $E$ on $G$; the pairs in $E$ are called the
arcs or edges of $\mathbb{G}$. It is reflexive if $(x,x)\in E$ for all $x\in
E$. When we consider digraphs $\mathbb{G}$, $\mathbb{H}$, etc. we denote their
set of vertices by $G$, $H$, etc. We sometimes write $u\rightarrow v$ to mean
that $(u,v)$ is an arc of a digraph. Consider the simple graph obtained from
the digraph $\mathbb{G}$ as follows: it has the same set of vertices $G$, and
two vertices $x$ and $y$ are adjacent if one of $(x,y)$ or $(y,x)$ is an arc
of $\mathbb{G}$. We say $\mathbb{G}$ is connected if this graph is connected.
We say that a digraph $\mathbb{H}$ is embedded in a digraph $\mathbb{G}$ if it
is isomorphic to an induced subdigraph of $\mathbb{G}$.

In this paper, all digraphs are assumed to be reflexive.

Let $\mathbb{G}$ and $\mathbb{H}$ be digraphs. A map $f:G\rightarrow H$ is a
homomorphism if it preserves edges, i.e. if $(x,y)$ is an arc of $\mathbb{G}$
then $(f(x),f(y))$ is an arc of $\mathbb{H}$. The product
$\mathbb{G}\times\mathbb{H}$ of two digraphs $\mathbb{G}$ and $\mathbb{H}$ is
the usual product of relational structures, i.e. the digraph with set of
vertices $G\times H$ and arcs $((g_{1},h_{1}),(g_{2},h_{2}))$ where
$(g_{1},g_{2})$ and $(h_{1},h_{2})$ are arcs of $\mathbb{G}$ and $\mathbb{H}$
respectively; notice that $\mathbb{G}\times\mathbb{H}$ is reflexive if both
$\mathbb{G}$ and $\mathbb{H}$ are reflexive. For every positive integer $k$,
the product of $k$ digraphs is defined is the obvious way; $\mathbb{G}^{k}$ is
the product of $\mathbb{G}$ with itself $k$ times. A $k$-ary polymorphism of
$\mathbb{G}$ is a homomorphism from $\mathbb{G}^{k}$ to $\mathbb{G}$; it is
idempotent if $f(x,\dots,x)=x$ for all $x\in G$. It is essentially unary if
there exists some $1\leq i\leq k$ and a homomorphism
$g:\mathbb{G}\rightarrow\mathbb{G}$ such that $f(x_{1},\dots,x_{k})=g(x_{i})$
for all $x_{j}\in G$.

######  Definition 2.1.

We say that the digraph $\mathbb{G}$ is Słupecki if all its surjective
polymorphisms are essentially unary.

######  Definition 2.2.

Let $k\geq 0$. A path of length $k$ is a digraph with vertex set
$\\{0,1,\dots,k\\}$ where for each $0\leq i\leq k-1$, one or both of the arcs
$\\{(i,i+1),(i+1,i)\\}$ is present, and there are no other arcs.

######  Definition 2.3.

Let $n\geq 3$. An $n$-cycle is a digraph with vertex set $\\{0,1,\dots,n-1\\}$
where for each $0\leq i<n-1$, one or both of the arcs $\\{(i,i+1),(i+1,i)\\}$
is present, one or both of the arcs $\\{(n-1,0),(0,n-1)\\}$ is present, and
there are no other arcs. The integer $n$ is called the girth of the cycle.

###  2.2. Words

It will be convenient for us to view paths (and cycles) as words on the
alphabet $\mathcal{A}=\\{+,-,*\\}$, where $*$ stands for a symmetric edge. As
usual, if $k$ is a positive integer, a word $W$ on $\mathcal{A}$ of length $k$
is a finite sequence $W=x_{1}\cdots x_{k}$ where $x_{i}\in\mathcal{A}$; the
integer $k$ is the length of $W$, denoted $|W|$. There is a unique word on
$\mathcal{A}$ of length 0, the empty word, and we denote it by $\epsilon$. As
usual, if $X=x_{1}\cdots x_{k}$ and $Y=y_{1}\cdots y_{l}$ are words on
$\mathcal{A}$, the concatenation of $X$ and $Y$ is the word $XY=x_{1}\cdots
x_{k}y_{1}\cdots y_{l}$. If $X=\epsilon$ then $XY=YX=Y$. If $n$ is a positive
integer and $X$ is a word, then $X^{n}$ is the concatenation of $n$ copies of
$X$, and we declare $X^{0}=\epsilon$. We say that the word $X=x_{1}\cdots
x_{k}$ is a subword of the word $Y$ if there exist words $W_{0},\dots,W_{k}$
such that $Y=W_{0}x_{1}W_{1}x_{2}\dots x_{k}W_{k}$, i.e. $X$ is obtained from
$Y$ by removing some symbols. The empty word is a subword of every word. The
word $X$ is a substring of the word $Y$ if there exist words $A$ and $B$ such
that $Y=AXB$; if $A$ is empty, $X$ is a prefix of $Y$, and if $B$ is empty,
$X$ is a suffix of $Y$. In the rest of this paper, unless otherwise stated,
all words are on $\mathcal{A}$.

The next definition interprets words as paths and vice-versa.

######  Definition 2.4.

Let $k$ be a positive integer.

  1. (1)

Let $W=x_{1}\cdots x_{k}$ be a non-empty word on $\mathcal{A}$. The path
associated to $W$, denoted $P(W)$, is the digraph with vertex set
$\\{0,\dots,k\\}$ where $(i,i+1)$ is an edge if $x_{i}=+$, $(i+1,i)$ is an
edge if $x_{i}=-$, and both $(i,i+1)$ and $(i+1,i)$ are edges if $x_{i}=*$. We
let $P(\epsilon)$ be the one-element path (with vertex set $\\{0\\}$).

  2. (2)

Given a path $\mathbb{P}$ of length $k$, define the word
$w(\mathbb{P})=x_{1}x_{2}\cdots x_{k}$ as follows: $x_{i}=*$ if both $(i,i+1)$
and $(i+1,i)$ are edges of $\mathbb{P}$; otherwise, $x_{i}=+$ if $(i,i+1)$ is
an edge of $\mathbb{P}$ and $x_{i}=-$ if $(i+1,i)$ is an edge of $\mathbb{P}$.
If $\mathbb{P}$ has length 0 then $w(\mathbb{P})=\epsilon$.

Figure 1. The path $\mathbb{P}=P(W)$ where $W=-*++-$.

We now define an ordering and an involution on the set of words on
$\mathcal{A}$.

######  Definition 2.5.

Let $U$ and $V$ be words of length $k$ and $l$ respectively.

We say that a homomorphism $f:P(U)\rightarrow P(V)$ is end-point preserving if
$f(0)=0$ and $f(k)=l$; and we write $U\leq V$ if there exists an end-point
preserving homomorphism from $P(V)$ onto $P(U)$.

It is a simple exercise to verify that this defines a partial ordering on the
set of words, i.e. it is reflexive, antisymmetric and transitive. In this
ordering, the empty word $\epsilon$ is a minimal element, it is covered by
$*$, which lies below $+$ and $-$ which are incomparable.

######  Definition 2.6.

Let $W$ be a word. If $W=\epsilon$ then $\overline{W}=\epsilon$; otherwise, if
$W=x_{1}\cdots x_{k}$ let
$\overline{W}=\overline{x_{k}}\cdots\overline{x_{1}}$ where $\overline{+}$ is
$-$, $\overline{-}$ is $+$ and $\overline{*}$ is $*$.

Intuitively, the involution of a word $W$ is the word $w(P^{\prime})$ where
$P^{\prime}$ is the path $P(W)$ traversed backwards. For example,
$\overline{+*-+-}$ is $+-+*-$. We shall say that a path $\mathbb{P}$ is self-
dual if $w(\mathbb{P})=\overline{w(\mathbb{P})}$.

######  Definition 2.7.

Let $\mathbb{G}$ be a digraph, let $x$ and $y$ be vertices of $\mathbb{G}$ and
let $W$ be a word of length $k$. We write $x\,Wy$ if there exists a
homomorphism of $P(W)$ to $\mathbb{G}$ mapping 0 to $x$ and $k$ to $y$.

It will also be convenient for us to denote cycles by words on $\mathcal{A}$:
the word $W$ lists the succession of arcs of the cycle starting from some
fixed vertex.

######  Definition 2.8.

Let $W=x_{1}\cdots x_{k}$ be a non-empty word. The cycle associated to $W$,
denoted $C(W)$, is the digraph with vertex set $\\{0,\dots,k-1\\}$ where for
each $1\leq i\leq k$, $(i-1,i)$ is an edge if $x_{i}=+$, $(i+1,i)$ is an edge
if $x_{i}=-$, and both $(i,i+1)$ and $(i+1,i)$ are edges if $x_{i}=*$, where
the indices are considered modulo $k$.

Figure 2. The cycle $\mathbb{G}=C(W)$ where $W=+*+-**$.

Notice that, up to isomorphism, there are several different words that
represent a given cycle, depending on the chosen starting point and the
orientation. We shall feel free to write $\mathbb{G}=C(W)$ for any of these
words.

Furthermore we shall often abuse notation; for instance, we may write
$\mathbb{P}\leq\mathbb{Q}$ where $\mathbb{P}$ and $\mathbb{Q}$ are paths,
meaning of course that $w(\mathbb{P})\leq w(\mathbb{Q})$; or if $\mathbb{G}$
is a cycle, $\mathbb{S}$ is a path, we may write
$\mathbb{G}=(\mathbb{S}**)^{2}\,\mathbb{S}+$ instead of
$\mathbb{G}=C((w(\mathbb{S})**)^{2}w(\mathbb{S})+)$, and so on.

The next lemma gathers some useful consequences of the definitions.

######  Lemma 2.9.

Let $X,Y,W$ be words and let $a,b\in\mathcal{A}$.

  1. (1)

Let $\mathbb{P}$ and $\mathbb{Q}$ be paths. If there exists an end-point
preserving map from $\mathbb{P}$ onto $\mathbb{Q}$ then there exists one which
is monotone, i.e. a map $f$ satisfying $f(i)\leq f(j)$ whenever $i\leq j$.

  2. (2)

If $\mathbb{P}\geq\mathbb{Q}$, and $\mathbb{P}=aX$ and $\mathbb{Q}=bY$ where
$a\geq b$ then there exists an end-point preserving monotone map from
$\mathbb{P}$ onto $\mathbb{Q}$ that sends $a$ onto $b$.

  3. (3)

If $X$ is a subword of $Y$ then $X\leq Y$; if $X\leq Y$ then $|X|\leq|Y|$.

  4. (4)

$X\leq Y$ if and only if $\overline{X}\leq\overline{Y}$;
$\overline{XY}=\overline{Y}\,\overline{X}$;

  5. (5)

if $aX\geq bY$ then $X\geq Y$; and if $a\ngeq b$ then $X\geq bY$.

  6. (6)

let $f:\mathbb{G}\rightarrow\mathbb{H}$ be a homomorphism and let $x,y\in G$.
If $x\,Wy$ then $f(x)\,Wf(y)$.

  7. (7)

if $X\leq A$ and $Y\leq B$ then $XY\leq AB$.

###### Proof.

(1) We use induction on $|\mathbb{P}|+|\mathbb{Q}|$: the result is trivial if
$|\mathbb{P}|+|\mathbb{Q}|=0$. Let $f$ be an end-point preserving homomorphism
from $\mathbb{P}$ onto $\mathbb{Q}$. (i) Suppose first that $0$ is the only
vertex of $\mathbb{P}$ mapped to $0$ by $f$, then $f(1)=1$. Let
$\mathbb{P}^{\prime}$ is the subpath of $\mathbb{P}$ induced by the vertices
other than 0; then by induction hypothesis we have a monotone map from
$\mathbb{P}^{\prime}$ onto the subpath of $\mathbb{Q}$ induced by the vertices
other than 0, and we can extend it to a monotone map from $\mathbb{P}$ onto
$\mathbb{Q}$. (ii) Otherwise, there exists an $x>0$ such that $f(x)=0$; let
$\mathbb{P}^{\prime}$ be the subpath of $\mathbb{P}$ induced by $\\{i:i\geq
x\\}$. By induction hypothesis there exists a monotone map $g$ from
$\mathbb{P}^{\prime}$ onto $\mathbb{Q}$. Setting $h(t)=0$ if $t<x$ and
$h(t)=g(t)$ if $t\geq x$ defines a monotone homomorphism from $\mathbb{P}$
onto $\mathbb{Q}$.

(2) By (1) there exists a monotone map $f$ from $\mathbb{P}$ onto
$\mathbb{Q}$. Let $x>0$ such that $f(x)=1$. Define a new map $g$ as follows:
$g(0)=0$, $g(t)=1$ if $1\leq t\leq x$ and $g(t)=f(t)$ for $t\geq x$. Since
$a\geq b$, $g$ is a homomorphism, and it is clearly monotone and end-point
preserving.

Statements (3)-(7) are also easy.

∎

##  3\. The path condition

In this section, we introduce a property that guarantees a cycle is Słupecki,
and prove a combinatorial characterisation that will allow us, in the next
section, to describe explicitly those cycles that fail this property.

######  Definition 3.1.

We say that the $n$-cycle $\mathbb{G}$ satisfies the path condition if one
cannot find paths $\mathbb{Q}_{i}$ of length $n-2$ that embed in $\mathbb{G}$
and a surjective homomorphism
$f:\prod_{i}\mathbb{Q}_{i}\twoheadrightarrow\mathbb{G}$.

Let $\theta\subseteq G^{n}$ be an $n$-ary relation on the non-empty set $A$,
and let $f:A^{k}\rightarrow A$ be a $k$-ary operation on $A$. We say that $f$
preserves $\theta$ if, whenever $(x^{1}_{j},\dots,x^{n}_{j})\in\theta$ for
$j=1,\dots,k$, we have that
$(f(x^{1}_{1},\dots,x^{1}_{k}),\dots,f(x^{n}_{1},\dots,x^{n}_{k}))\in\theta$.
The following fact can be found in [11].

######  Lemma 3.2 ([11], Lemma 4.1).

Let $A$ be an $n$-element set, $n\geq 2$. Then the operations on $A$
preserving the relation

$\theta=\\{(a_{1},\dots,a_{n}):|\\{a_{1},\dots,a_{n}\\}|<n\\}$

are precisely the essentially unary operations and the non-surjective
operations on $A$.

######  Theorem 3.3.

If a cycle satisfies the path condition then it is Słupecki.

###### Proof.

Suppose that the cycle $\mathbb{G}$ is not Słupecki; by the previous lemma,
there exists a polymorphism $f:\mathbb{G}^{k}\rightarrow\mathbb{G}$ that does
not preserve the Słupecki relation $\theta$. Then there exist $k$ tuples in
$\theta$ that $f$ maps to some tuple outside $\theta$. For each tuple in
$\theta$, there exists a proper subset of $G$ containing its coordinates;
taking a largest one, it is a path of length $n-2$ (obtained from $\mathbb{G}$
by removing a single vertex.) Since $f$ maps the $k$ columns to a tuple whose
coordinates are all vertices of $\mathbb{G}$, in particular, the restriction
of $f$ to the product of the $k$ paths is onto $\mathbb{G}$. ∎

Our next goal is to show that, if an $n$-cycle $\mathbb{G}$ does not satisfy
the path condition, then there exists a homomorphism of a product of subpaths
of $\mathbb{G}$ of length $n-2$ onto a subpath of $\mathbb{G}$ of length $n-1$
(Lemma 3.8). This will allow us to reformulate the path condition is a purely
combinatorial way (Theorem 3.9).

We require some basic facts about discrete homotopy of reflexive digraphs; all
details can be found in [10], see also [6]. The one-way infinite fence
$\mathbb{F}$ is the following (infinite) reflexive digraph: its base set is
the set of non-negative integers, and $(n,m)$ is an arc if $n=m$ or $n$ is
even and $|n-m|=1$. Let $\mathbb{G}$ be a digraph and $u,v\in G$. We say that
$p$ is a path in $\mathbb{G}$ from $u$ to $v$ if $p$ a homomorphism from
$\mathbb{F}$ to $\mathbb{G}$ such that there exists an $N\geq 0$ with $f(0)=u$
and $f(t)=v$ for all $t\geq N$. This corresponds in a straightforward way to
the intuitive notion of a path in $\mathbb{G}$ from $u$ to $v$111These paths
in $\mathbb{G}$ are not directed paths, but rather sequences of vertices that
are paths in the underlying undirected reflexive graph.; in particular, if $f$
is path in $\mathbb{G}$ from $u$ to $v$ and $g$ is a path in $\mathbb{G}$ from
$v$ to $w$, then we can define a path $fg$ from $u$ to $w$ in the natural way,
and we can also define a path $p^{-1}$ in $\mathbb{G}$ from $v$ to $u$ (see
[10]). If $p$ is a path in $\mathbb{G}$ from $u$ to $v$, and
$f:\mathbb{G}\rightarrow\mathbb{H}$ is a homomorphism, then clearly the
composition of $f$ with $p$ is path in $\mathbb{H}$ from $f(u)$ to $f(v)$,
which we denote by $f(p)$. It is immediate to verify that $f(pq)=f(p)f(q)$,
$f(p^{-1})=f(p)^{-1}$ and $(pq)^{-1}=q^{-1}p^{-1}$.

Let $a\in\mathbb{G}$. Then $\mathbb{F}(\mathbb{G},a)$ denotes the (infinite)
digraph whose vertices are all paths in $\mathbb{G}$ from $a$ to $a$, where
$(f,g)$ is an arc if, whenever $(s,t)$ is an arc of $\mathbb{F}$ then
$(f(s),g(t))$ is an arc of $\mathbb{G}$. Two paths in
$\mathbb{F}(\mathbb{G},a)$ are homotopic if they are in the same connected
component. It turns out that the composition of paths induces a group
structure on the connected components of $\mathbb{F}(\mathbb{G},a)$, and we
denote this group by $\sigma_{1}(\mathbb{G},a)$. If $\mathbb{G}$ is connected,
the choice of $a$ is immaterial; and it can be shown that
$\sigma_{1}(\mathbb{G})$ is isomorphic to the fundamental group of the
triangulation of the following simplicial complex associated to $\mathbb{G}$:
its vertices are the vertices of $\mathbb{G}$, and its simplices are the
subsets of $G$ that are the homomorphic image of some totally ordered set
(i.e. a chain) in $\mathbb{G}$. Notice in particular that
$\sigma_{1}(\mathbb{G})$ is trivial whenever $\mathbb{G}$ is a product of
paths.

Our strategy to prove Lemma 3.8 is simple. Given an $n$-cycle $\mathbb{G}$, we
construct a (two-way infinite) path $\widehat{\mathbb{G}}$ which admits a
homomorphism $\pi$ onto $\mathbb{G}$, such that, for any homomorphism
$f:\mathbb{K}\rightarrow\mathbb{G}$ where $\mathbb{K}$ is connected and has
trivial fundamental group, there exists a homomorphism
$\widehat{f}:\mathbb{K}\rightarrow\widehat{\mathbb{G}}$ such that
$\pi\circ\widehat{f}=f$: the path $\widehat{\mathbb{G}}$ is the natural analog
of the universal covering space of the cycle $\mathbb{G}$. The homomorphism
$f$ will be onto precisely when the image of $\widehat{f}$ has size at least
$n-1$; hence, there exists a homomorphism from $\mathbb{K}$ onto $\mathbb{G}$
if and only if there is one from $\mathbb{K}$ onto some subpath of
$\mathbb{G}$ of length $n-1$.

Let $\mathbb{G}$ be an $n$-cycle and let $a\in G$. Let $p$ be a path from $u$
to $v$ in $\mathbb{G}$. Define $\alpha(p)$ to be the number of pairs $(t,t+1)$
in $\mathbb{F}$ such that $(f(t),f(t+1))=(a-1,a)$ minus the number of pairs
$(t,t+1)$ in $\mathbb{F}$ such that $(f(t),f(t+1))=(a,a-1)$. Intuitively, this
corresponds to the “winding number” of the path $p$.

Our first goal is to show that $\alpha$ is invariant under homotopy. To prove
this, we will use the notion of non-refinable edge from [12]. We simply
rephrase Maróti and Zádori’s Lemma 2.10 for our purposes (the proof they give
is still valid in the more general context of $Hom(\mathbb{A},\mathbb{G})$
even though they formulate it only in the case of
$Hom(\mathbb{G},\mathbb{G})$; see section 5 for a definition of these
digraphs.)

Let $(p,q)$ be an edge of $\mathbb{F}(\mathbb{G},a)$. Let $Neq(p,q)$ denote
the (finite) set of all $t\in F$ such that $p(t)\neq q(t)$. The edge $(p,q)$
is non-refinable if there is no non-empty proper subset $A$ of $Neq(p,q)$ such
that changing the value of $q$ to that of $p$ on $A$ yields an element of
$\mathbb{F}(\mathbb{G},a)$. Call an edge $(u,v)$ of $\mathbb{F}$ critical for
$(p,q)$ if $(q(u),p(v))$ is not an edge of $\mathbb{G}$.

######  Lemma 3.4 (Based on Lemma 2.10 of [12]).

Let $\mathbb{G}$ be a digraph and let $a\in G$.

  1. (1)

If $p,q\in\mathbb{F}(\mathbb{G},a)$ are homotopic then there exists a path of
non-refinable edges from $p$ to $q$;

  2. (2)

An edge $(p,q)$ is non-refinable if and only if $|Neq(p,q)|\leq 1$.

###### Proof.

(1) It clearly suffices to prove the result when $p\rightarrow q$. If $(p,q)$
is non-refinable, we are done. Otherwise, there exists
$r\in\mathbb{F}(\mathbb{G},a)$ obtained by changing the value of $q$ on
certain, but not all, values in $Neq(p,q)$ to that of $p$. Notice in
particular that $r(t)\in\\{p(t),q(t)\\}$ for all $t$ and hence $p\rightarrow
r\rightarrow q$; secondly, it is clear that $Neq(r,p)$ and $Neq(r,q)$ are
proper non-empty subsets of $Neq(p,q)$. By repeating the argument, this
process must terminate and we obtain the desired path.

(2) Necessity is immediate. Now suppose that $|Neq(p,q)|>1$. Consider the
digraph $\mathbb{D}$ whose set of vertices is $V=Neq(p,q)$ and whose edges are
the edges critical for $(p,q)$. Since this digraph is not strongly connected
(it is a subgraph of $\mathbb{F}$ which is acyclic), we can find a non-empty,
non-trivial strong component $A$ of $\mathbb{D}$ such that no critical edge
goes from $V\setminus A$ to $A$; we can thus change the value of $q$ on $A$ to
that of $p$ to obtain an $r\in\mathbb{F}(\mathbb{G},a)$; $r$ is a homomorphism
by definition of critical edge and choice of $A$, and $r$ satisfies the
“boundary” requirements of $\mathbb{F}(\mathbb{G},a)$ because $0\not\in
Neq(p,q)$ so $r(0)=a$; and $p(t)=q(t)=a$ for all $t\geq N$ for some $N$, so
the same holds for $r$. ∎

######  Lemma 3.5.

Let $p,q\in\mathbb{F}(\mathbb{G},a)$. If $p$ and $q$ are homotopic then
$\alpha(p)=\alpha(q)$.

###### Proof.

By the last lemma, it suffices to prove that, if $p\rightarrow q$ in
$\mathbb{F}(\mathbb{G},a)$ and $p$ and $q$ differ in exactly one place, then
$\alpha(p)=\alpha(q)$. Let $\\{c,d\\}=\\{a-1,a\\}$. The result is clear if the
edges of $\mathbb{F}$ mapped by $p$ and $q$ onto $\\{c,d\\}$ are the same.
Hence we may assume there exists a unique edge $e$ of $\mathbb{F}$ that one of
$p,q$ maps onto $\\{c,d\\}$ but not the other. Let $e=(u,v)$ and suppose that
$(p(u),p(v))=(c,d)$ (all the other cases are identical.) Then $p(u)\rightarrow
q(v)$ and $p(v)\rightarrow q(v)$ implies that $q(v)\in\\{c,d\\}$ (keeping in
mind that $\mathbb{G}$ is a cycle). Suppose first that $q(v)=c$. Then
$q(u)=p(u)=c$. By definition of $\mathbb{F}$, there exists $w$ a neighbour of
$v$ distinct from $u$; by the same transitivity argument as above we get that
$p(w)\in\\{c,d\\}$, and of course $q(w)=p(w)$. If $p(w)=d$ then both $p$ and
$q$ traverse $(c,d)$ exactly once on $\\{u,v,w\\}$, and if $p(w)=c$ then $p$
traverses both $(c,d)$ and $(d,c)$ once while $q$ traverses neither; in both
cases we get that $\alpha(p)=\alpha(q)$. Suppose now that $q(v)=d$. Then
$c=p(u)\rightarrow q(u)\rightarrow q(v)=d$ implies that $q(u)\in\\{c,d\\}$,
hence by hypothesis $q(u)=d$. Repeating the argument above using the neighbour
$w^{\prime}$ of $u$ distinct from $v$ (notice that $u\neq 0$ since one of
$p(u)$ or $q(u)$ is different from $a$) will complete the proof. ∎

######  Definition 3.6.

Let $\mathbb{G}$ be an $n$-cycle, and let $a\in G$. The universal covering
space $\widehat{\mathbb{G}}$ of $\mathbb{G}$ is the (infinite) reflexive
digraph with vertex set $G\times\mathbb{Z}$, and whose arcs are all pairs
$((x,i),(y,i))$ such that $(x,y)\in E(\mathbb{G})$ and
$\\{x,y\\}\neq\\{a-1,a\\}$, together with the arcs $((a-1,i),(a,i+1))$ if
$(a-1,a)\in E(\mathbb{G})$ and $((a,i+1),(a-1,i))$ if $(a,a-1)\in
E(\mathbb{G})$, and this for all $i\in\mathbb{Z}$.

Notice that, in the previous definition, the choice of $a$ is immaterial, i.e.
the resulting digraphs will all be isomorphic. We chose this way of defining
the universal covering space to make the following proof easier. It is clear
by construction that the map $\pi:\widehat{\mathbb{G}}\rightarrow\mathbb{G}$
defined by $\pi(x,i)=x$ is a homomorphism onto $\mathbb{G}$.

######  Lemma 3.7.

Let $\mathbb{K}$ be a connected digraph with $\sigma_{1}(\mathbb{K})=0$, and
let $f:\mathbb{K}\rightarrow\mathbb{G}$. Then there exists a map
$\widehat{f}:\mathbb{K}\rightarrow\widehat{\mathbb{G}}$ such that
$\pi\circ\widehat{f}=f$.

###### Proof.

Choose a vertex $u\in K$ and let $f(u)=a$. Let $v\in K$.

Claim. If $p$ and $q$ are any paths from $u$ to $v$ in $\mathbb{K}$, then
$\alpha(f(p))=\alpha(f(q))$.

Proof of Claim. Consider the discrete homotopy groups
$\sigma_{1}(\mathbb{K},u)$ and $\sigma_{1}(\mathbb{G},a)$; $f$ induces a group
homomorphism from the first to the second. Since $\sigma_{1}(\mathbb{K},u)$ is
trivial, for any two paths $p,q$ from $u$ to $v$ we have that $pq^{-1}$ is
homotopic to the constant path at $u$. Applying $f$, we obtain that
$f(pq^{-1})$ is homotopic to the constant path at $a$; in particular, since
$\alpha$ is preserved under homotopy by Lemma 3.5,
$0=\alpha(f(pq^{-1}))=\alpha(f(p)f(q^{-1}))=\alpha(f(p)f(q)^{-1})$. Since
clearly $\alpha(f(p)f(q)^{-1})=\alpha(f(p))-\alpha(f(q))$ the claim follows.

By the claim, if we set $\widehat{f}(v)=(f(v),\alpha(f(p)))$ for any path $p$
from $u$ to $v$, this function is well-defined; clearly
$\pi\circ\widehat{f}=f$, so it remains to prove $\widehat{f}$ is a
homomorphism. This is in fact straightforward: let $v\rightarrow w$ be an arc
in $\mathbb{K}$. Let $p$ be any path from $u$ to $v$, and let $p^{\prime}$ be
the path from $u$ to $w$ which is $p$ followed by the arc $(v,w)$. Let
$\alpha=\alpha(f(p))$ and let $\alpha^{\prime}=\alpha(f(p^{\prime}))$. Then
$\widehat{f}(v)=(f(v),\alpha)$ and $\widehat{f}(w)=(f(w),\alpha^{\prime})$.
Notice that $\alpha\neq\alpha^{\prime}$ precisely when
$\\{f(v),f(w)\\}=\\{a-1,a\\}$. Thus if $\alpha=\alpha^{\prime}$ we are done.
Otherwise, we have that either $(f(v),f(w))=(a-1,a)$ and then
$\alpha^{\prime}=\alpha+1$ or $(f(v),f(w))=(a,a-1)$ and then
$\alpha^{\prime}=\alpha-1$; in either case $(\widehat{f}(v),\widehat{f}(w))$
is an arc.

∎

The next result shows that the path condition can be reformulated as a problem
of determining if there exists a homomorphism from products of subpaths of
$\mathbb{G}$ onto a subpath of $\mathbb{G}$ rather than $\mathbb{G}$ itself;
we then describe a simple combinatorial criterion to determine if such a
homomorphism exists (Theorem 3.9).

######  Lemma 3.8.

Let $\mathbb{G}$ be an $n$-cycle. Then the following are equivalent:

  1. (1)

$\mathbb{G}$ fails the path condition;

  2. (2)

there exist paths $\mathbb{Q}_{i}$ of length $n-2$ that embed in $\mathbb{G}$,
a path $\mathbb{P}$ of length $n-1$ that embeds in $\mathbb{G}$ and a
surjective homomorphism $f:\prod_{i}\mathbb{Q}_{i}\rightarrow\mathbb{P}$.

###### Proof.

$(2)\Rightarrow(1)$ is immediate. $(1)\Rightarrow(2)$: suppose there exists a
surjective homomorphism $f:\mathbb{K}\rightarrow\mathbb{G}$ where $\mathbb{K}$
is a product of subpaths of $\mathbb{G}$ of length $n-2$. By Lemma 3.7, we
have a homomorphism $\widehat{f}:\mathbb{K}\rightarrow\widehat{\mathbb{G}}$
such that $\pi\circ\widehat{f}=f$. In particular, the image of $\widehat{f}$
is connected, and hence is a path, and has length at least $n-1$. It now
suffices to observe that any path can be retracted to a subpath sending the
endpoints of the longer path to the endpoints of the shorter one; the path of
length $n-1$ is a subpath of $\mathbb{G}$ by construction of
$\widehat{\mathbb{G}}$. ∎

######  Theorem 3.9.

Let $\mathbb{G}$ be an $n$-cycle, and let
$\mathbb{Q}_{1},\dots,\mathbb{Q}_{l}$ denote its induced subpaths of length
$n-2$. The following are equivalent:

  1. (1)

$\mathbb{G}$ satisfies the path condition;

  2. (2)

for every induced subpath $\mathbb{P}$ of $\mathbb{G}$ of length $n-1$, there
exists a word $W$ such that $W\geq\mathbb{Q}_{i}$ for all $i$ but
$W\not\geq\mathbb{P}$.

Before we launch into the proof, we shall require some facts about extending
partial maps to paths. The next result is a consequence of Theorem 42 in [2],
see also Theorems 19 and 20 in [7] as well as the comment that follows them.

######  Lemma 3.10.

Let $\mathbb{P}$ be a path. Let $\mathbb{K}$ be a digraph, let $X\subseteq K$
and let $g:X\rightarrow P$ be any map. There exists a homomorphism from
$\mathbb{K}$ to $\mathbb{P}$ whose restriction to $X$ is $g$ if and only if,
for every $x,y\in X$, and any word $W$, if $xWy$ in $\mathbb{K}$ then
$g(x)Wg(y)$ in $\mathbb{P}$.

###### Proof.

Necessity is immediate by Lemma 2.9 (6). Now suppose there exists no
homomorphism from $\mathbb{K}$ to $\mathbb{P}$ whose restriction to $X$ is
$g$. Consider the relational structure $\mathbb{P}^{c}$ consisting of the path
$\mathbb{P}$ together with all singleton unary relations $\\{p\\}$, $p\in P$;
let $\tau$ denote the signature of this structure. Consider the
$\tau$-structure $\mathbb{K}^{c}$ consisting of the digraph $\mathbb{K}$ where
each element $x\in X$ is constrained by the unary relation $\\{g(x)\\}$. Then
$\mathbb{K}^{c}$ does not admit a homomorphism to $\mathbb{P}^{c}$. It follows
from the results mentioned above that $\mathbb{P}^{c}$ has path duality, hence
there exists some $\tau$-path $\mathbb{Q}^{c}$ that admits a homomorphism $h$
to $\mathbb{K}^{c}$ but no homomorphism to $\mathbb{P}^{c}$. Because
$\mathbb{P}$ is reflexive, it is easy to see that such a $\tau$-path consists
of a directed path with endpoints constrained by some unary relations; let’s
denote the path by $\mathbb{Q}$, its endpoints by $u$ and $v$ which are
constrained by the unary relations $\\{a\\}$ and $\\{b\\}$ respectively; let
$h:\mathbb{Q}^{c}\rightarrow\mathbb{K}^{c}$ be the homomorphism. Since $h$ is
a $\tau$-homomorphism we must have that $x=h(u)$ and $y=h(v)$ belong to $X$
and $g(x)=a$, $g(y)=b$. If $W$ denotes the word $w(\mathbb{Q})$ where
$\mathbb{Q}$ is the underlying path of $\mathbb{Q}^{c}$, then we have that
$xWy$; but $g(x)Wg(y)$ does not hold, as desired. ∎

###### Proof.

(Theorem 3.9) (1) $\Rightarrow$ (2): suppose that there exists an induced
subpath $\mathbb{P}$ of $\mathbb{G}$ of length $n-1$ such that, for every word
$W\geq\mathbb{Q}_{i}$ for all $1\leq i\leq l$ we have $W\geq\mathbb{P}$. For
each $i$ let $a_{i},b_{i}$ denote the endpoints of $\mathbb{Q}_{i}$, let
$X=\\{\alpha,\beta\\}\subseteq\prod_{i}\mathbb{Q}_{i}$ where
$\alpha=(a_{1},\dots,a_{l})$ and let $\beta=(b_{1},\dots,b_{l})$; and let
$g:X\rightarrow\mathbb{P}$ be defined by $g(\alpha)=a$ and $g(\beta)=b$ where
$a$ and $b$ are the endpoints of $\mathbb{P}$. Let $W$ be a word such that
$\alpha W\beta$ in $\prod_{i}\mathbb{Q}_{i}$; composing with the projection
maps this implies that $W\geq\mathbb{Q}_{i}$ for all $i$ and so
$W\geq\mathbb{P}$ by hypothesis; this means that $aWb$ in $\mathbb{P}$, and
the last lemma implies that there exists a homomorphism from
$\prod_{i}\mathbb{Q}_{i}$ to $\mathbb{P}$ that extends $g$. Since
$\prod_{i}\mathbb{Q}_{i}$ is connected, so is its image which contains the
endpoints of $\mathbb{P}$, so this map is onto, so $\mathbb{G}$ fails the path
condition.

(2) $\Rightarrow$ (1): suppose that $\mathbb{G}$ fails the path condition.
Then by Lemma 3.8 there exists an induced subpath $\mathbb{P}$ of $\mathbb{G}$
of length $n-1$, induced subpaths $\mathbb{Q}_{j}$ of $\mathbb{G}$ of length
$n-2$ and a homomorphism from $\mathbb{Q}=\prod_{j}\mathbb{Q}_{j}$ onto
$\mathbb{P}$. Let $a$ and $b$ denote the endpoints of $\mathbb{P}$, and let
$\alpha,\beta\in\mathbb{Q}$ such that $f(\alpha)=a$ and $f(\beta)=b$. Let
$a_{j},b_{j}$ denote the coordinates of $\alpha$ and $\beta$ in
$\mathbb{Q}_{j}$ respectively, and let $\mathbb{R}_{j}$ denote the induced
subpath of $\mathbb{Q}_{j}$ from $a_{j}$ to $b_{j}$. Notice that depending on
which of $a_{j}$ or $b_{j}$ appears first in the path $\mathbb{Q}_{j}$, we
have that $\mathbb{Q}_{j}\geq\mathbb{R}_{j}$ or
$\mathbb{Q}_{j}\geq\overline{\mathbb{R}_{j}}$. But because the set of paths
$\mathbb{Q}_{1},\dots,\mathbb{Q}_{l}$ is closed under taking duals, i.e. for
every $i$ there exists $s$ such that
$\overline{\mathbb{Q}_{i}}=\mathbb{Q}_{s}$, if the word $W$ satisfies
$W\geq\mathbb{Q}_{i}$ for all $i$ then $W\geq\mathbb{R}_{j}$ for all $j$.
Hence $\alpha W\beta$ in $\mathbb{Q}$, and thus $f(\alpha)Wf(\beta)$ in
$\mathbb{P}$, i.e. $W\geq\mathbb{P}$.

∎

##  4\. Cycles that fail the path condition: a characterisation

######  Definition 4.1.

We say that the cycle $\mathbb{G}$ is almost symmetric if $\mathbb{G}$
contains exactly one non-symmetric edge.

The main theorem of this section is the following:

######  Theorem 4.2.

Let $n\geq 3$. The $n$-cycle $\mathbb{G}$ fails the path condition if and only
if $\mathbb{G}$ is almost symmetric or there exists a self-dual path
$\mathbb{S}$ and a positive integer $k$ such that
$\mathbb{G}=(\mathbb{S}**)^{k}\,\mathbb{S}+$.

We first make an easy but important observation.

######  Lemma 4.3.

Let $W,A,B$ be words such that $W\geq A+B$ and $W\geq A-B$. Then $W\geq A+-B$
or $W\geq A-+B$.

###### Proof.

Using Lemma 2.9 (1) it easy to see that $W\geq A+B$ implies we can write
$W=U_{1}+U_{2}$ with $U_{1}\geq A$ and $U_{2}\geq B$; similarly we can write
$W=V_{1}-V_{2}$ with $V_{1}\geq A$ and $V_{2}\geq B$. If $|V_{1}|<|U_{1}|$
then $W=V_{1}-Z+U_{2}$ for some word $Z$, and thus $W\geq A-+B$; otherwise
$|U_{1}|<|V_{1}|$ and a similar argument shows that $W\geq A+-B$.

∎

The next two lemmas prove the easy direction.

######  Lemma 4.4.

Let $\mathbb{G}$ be an almost symmetric cycle of girth at least 3. Then
$\mathbb{G}$ fails the path condition.

###### Proof.

Let $n$ denote the girth of $\mathbb{G}$; let $\mathbb{P}=(*)^{n-1}$, let
$\mathbb{Q}=(*)^{n-3}\,-$ and let $\mathbb{R}=(*)^{n-3}\,+$. Clearly
$\mathbb{P}$ is an induced subpath of $\mathbb{G}$ of length $n-1$ and
$\mathbb{Q},\mathbb{R}$ are induced subpaths of $\mathbb{G}$ of length $n-2$.
Let $W\geq\mathbb{Q}$ and $W\geq\mathbb{R}$. By Lemma 4.3 we have that
$W\geq(*)^{n-3}-+$ or $W\geq(*)^{n-3}+-$; in any case
$W\geq(*)^{n-1}=\mathbb{P}$. It follows by Theorem 3.9 that $\mathbb{G}$ fails
the path condition. ∎

######  Lemma 4.5.

Let $\mathbb{S}$ be a self-dual path, let $k$ be a positive integer. Then the
cycle $\mathbb{G}=(\mathbb{S}**)^{k}\,\mathbb{S}+$ fails the path condition.

###### Proof.

Let $n$ denote the girth of $\mathbb{G}$. Clearly
$\mathbb{P}=(\mathbb{S}**)^{k}\,\mathbb{S}$ is an induced subpath of
$\mathbb{G}$ of length $n-1$. It is easy to see that the paths
$\mathbb{Q}=\mathbb{S}+(\mathbb{S}**)^{k-1}\mathbb{S}$ and
$\mathbb{R}=\mathbb{S}-(\mathbb{S}**)^{k-1}\mathbb{S}$ are induced subpaths of
$\mathbb{G}$ of length $n-2$ (for $\mathbb{R}$, read the word for $\mathbb{G}$
“backwards”). Let $W\geq\mathbb{Q}$ and $W\geq\mathbb{R}$. By Lemma 4.3, we
have that $W\geq\mathbb{S}+-(\mathbb{S}**)^{k-1}\mathbb{S}$ or
$W\geq\mathbb{S}-+(\mathbb{S}**)^{k-1}\mathbb{S}$; in any case we have that
$W\geq\mathbb{S}**(\mathbb{S}**)^{k-1}\mathbb{S}$, i.e. $W\geq\mathbb{P}$. It
follows by Theorem 3.9 that $\mathbb{G}$ fails the path condition.

∎

###  4.1. A necessary condition to fail the path condition

Our goal in this subsection is to prove the following technical result:

######  Theorem 4.6.

Let $\mathbb{G}$ be a cycle that fails the path condition. Then there exists
words $A$ and $B$ such that $\mathbb{G}=C(A**B+)=C(A+B**)=C(A-B**)$.

Let $\mathbb{G}$ be an $n$-cycle and let $\mathbb{P}_{i}$ be its subpaths of
length $n-2$. According to Theorem 3.9, $\mathbb{G}$ satisfies the path
condition if we can find, for each of its induced subpaths $\mathbb{P}$ of
length $n-1$, a word $W\ngeq\mathbb{P}$ such that $W\geq\mathbb{P}_{i}$ for
all $i$. It turns out that there is a uniform way of constructing, for each
path $\mathbb{P}$, a word $W(\mathbb{P})$ that will in most cases satisfy the
desired condition; furthermore, this construction will help us finding a
characterisation for the cycles that fail the path condition. The next
definition describes the construction.

######  Definition 4.7.

Let $x,y\in\mathcal{A}$, and let $N$ be a positive integer.

  1. (1)

Let

$[x,y]=\begin{cases}max\\{x,y\\}&\mbox{ if $x$ and $y$ are comparable},\\\
yx&\mbox{ otherwise.}\end{cases}$

  2. (2)

Let $p=(+)^{N}$ and $m=(-)^{N}$.

  3. (3)

Let

$\widehat{x}=\begin{cases}m&\mbox{ if $x$ is $+$},\\\ p&\mbox{ if $x$ is
$-$},\\\ \epsilon&\mbox{ if $x$ is $*$}.\end{cases}$

  4. (4)

For any non-empty word $X=x_{1}\cdots x_{r}$, let

$W_{N}(X)=\widehat{x_{1}}[x_{1},{x_{2}}]\widehat{x_{2}}\dots\widehat{x_{r-1}}[x_{r-1},{x_{r}}]\widehat{x_{r}}.$

Remark. In the following, we will assume $N$ is a fixed integer, much larger
than $n$ where $n$ is the girth of the cycle $\mathbb{G}$ in question, and we
shall omit the index $N$ as much as possible.

The following lemma follows directly from the definitions.

######  Lemma 4.8.

Let $x,y\in\mathcal{A}$, and let $A,B,X$ be words. Then

  1. (1)

$\widehat{x}\ngeq x$,

  2. (2)

$[x,y]\geq x$ and $[x,y]\geq y$ but $[x,y]\ngeq xy$.

∎

######  Lemma 4.9.

Let $x,y,z\in\mathcal{A}$ with $x\neq*$, and let $a,b$ be integers such that
$a+b\leq n$.

  1. (1)

$*^{a}\,\overline{x}\,*^{b}\leq\widehat{x}$;

  2. (2)

$*^{a}\,z\leq\widehat{x}\,[x,y]$;

  3. (3)

$z\,*^{a}\ \leq[y,x]\,\widehat{x}$;

  4. (4)

$yz\not\leq[y,z]\,\widehat{z}$.

###### Proof.

(1) is immediate by the definitions. (2) follows from (1) if $z$ is $*$ or
$\overline{x}$; otherwise $z=x$, and then notice that $*^{a}\leq\widehat{x}$
and $x\leq[x,y]$. (3) is identical to (2). An easy case-by-case analysis
yields (4). ∎

######  Lemma 4.10.

Let $X=x_{1}\dots x_{r}$ be a non-empty word on $\mathcal{A}$, and write
$X=x_{1}A=Bx_{r}$.

  1. (1)

$W(X)\geq A$, $W(X)\geq B$, but $W(X)\not\geq X$;

  2. (2)

$W_{N+1}(X)\geq W_{N}(X)$;

  3. (3)

If $x_{1}\in\\{+,-\\}$ then $W_{N+1}(X)\geq\overline{x_{1}}\,W_{N}(X)$; if
$x_{r}\in\\{+,-\\}$ then $W_{N+1}(X)\geq W_{N}(X)\,\overline{x_{r}}$.

###### Proof.

(1) The first two inequalities are immediate by Lemma 4.8 (2). Now we prove
that $W(X)\not\geq X$ by induction on $r$. If $r=1$ this is Lemma 4.8 (1). Let
$Y=X\,x_{r+1}$; then $W(Y)=W(X)\,[x_{r},x_{r+1}]\,\widehat{x_{r+1}}$. Suppose
for a contradiction that $W(Y)\geq Y$; by induction hypothesis, and using
Lemma 2.9 (1), if $W(X)\not\geq X$ then we must have
$[x_{r},x_{r+1}]\,\widehat{x_{r+1}}\geq x_{r}\,x_{r+1}$, which contradicts
Lemma 4.9 (4).

(2) is immediate.

(3) Simply observe that $W_{N}(X)$ is of the form
$\widehat{x_{1}}\,Y\,\widehat{x_{r}}$ and that
$\overline{x}\widehat{x}=\overline{x}^{N+1}$ if $x\neq*$. ∎

######  Lemma 4.11.

Let $X=x_{1}\dots x_{r}$ be a non-empty word on $\mathcal{A}$, let $A,B$ be
any words on $\mathcal{A}$ and let $z\in\mathcal{A}$.

  1. (1)

$W(X*)=W(X)\,x_{r}$ and $W(*X)=x_{1}\,W(X)$;

  2. (2)

$W(A\,*^{k}\,B)=W(A*)\,*^{k-1}\,W(*B)$ for all $k>0$;

  3. (3)

$W_{N+1}(A*B)\geq W_{N}(AB)$;

  4. (4)

$W(A\,z\,B)\geq W(A*B)$;

  5. (5)

If $A$ and $B$ are non-empty and $B\geq A$ then there exists $M\geq N$ such
that
$W_{M}(B)\geq W_{N}(A)$.

###### Proof.

(1) is immediate. We prove (2) by induction on $k$. Suppose first that $k=1$:
if $A$ or $B$ is empty the result is trivial. Otherwise, write $A=Ca$ and
$B=bD$ and then

$W(A*B)=W(A)[a,*]\,\widehat{*}\,[*,b]W(B)=W(A)\,ab\,W(B)=W(A*)W(*B)$

the last equality following from (1). Now suppose the result holds for $k$.
Then using the result for $k=1$ we get

$W(A*^{k+1}B)=W(A*\,(*^{k}B))=W(A*)W(*^{k+1}B)$

and using the induction hypothesis we conclude that this is

$W(A*)W(*\,*^{k}B)=W(A*)W(**)*^{k-1}W(*B)=W(A*)*^{k-1}W(*B).$

(3) By (2) we have that $W_{N+1}(A*B)=W_{N+1}(A*)W_{N+1}(*B)$. If $A$ or $B$
is empty the inequality is easy, so assume that $A=Ca$ and $B=bD$ for some
$a,b\in\mathcal{A}$. Then by (1) we get that
$W_{N+1}(A*B)=W_{N+1}(A)\,ab\,W_{N+1}(B)$; and directly from the definition we
have that $W_{N}(AB)=W_{N}(A)[a,b]W_{N}(B)$. If $a$ and $b$ are comparable,
then the inequality follows from Lemma 4.10 (2). Otherwise,
$W_{N}(AB)=W_{N}(A)[a,b]W_{N}(B)=W_{N}(A)\,ba\,W_{N}(B)=W_{N}(A)\,\overline{a}\overline{b}\,W_{N}(B)$
and the inequality now follows from Lemma 4.10 (3).

(4) If $A$ or $B$ is empty the result is easy, so assume that $A=Ca$ and
$B=bD$ for some $a,b\in\mathcal{A}$. Then
$W(AzB)=W(A)[a,z]\,\widehat{z}\,[z,b]W(B)\geq W(A)\,ab\,W(B)=W(A*B)$ by (1),
(2) and Lemma 4.8 (2).

(5) It is not hard to see, using Lemma 2.9, that $B\geq A$ precisely when $B$
contains a subword from which $A$ can be obtained by replacing certain $+$ and
$-$ by $*$. From this, it follows easily that there exists a word $D$ with the
following properties: (i) $D$ is obtained from $B$ by replacing some $+$ and
$-$ by $*$; (ii) $D$ contains $A$ as a subword; (iii) no symbol other than $*$
appears in $D$ outside the subword $A$. It follows from (4) that $W(B)\geq
W(D)$. Now starting from $D$, repeatedly use (3), removing a $*$ at each step,
until the subword $A$ is reached.

∎

Remark. In the following, given words $X,Y$ with $X\neq\epsilon$, we shall
write $Y\leq W(X)$ to mean that there exists some $N$ such that $Y\leq
W_{N}(X)$. Notice that this may lead to counter-intuitive statements such as
$\widehat{x}\,W(X)\leq W(X)$ when $x$ is the first symbol of $X$ (see Lemma
4.10 (3)).

######  Definition 4.12.

For a word $X$, let $X^{\prime}$ denote the subword of $X$ obtained by
deleting all the occurrences of $*$.

Notice that for any word $X$ we have that
$\overline{X^{\prime}}={\overline{X}}^{\prime}$.

######  Definition 4.13.

Let $X,Y$ be non-empty words on $\mathcal{A}$. A word $Z$ is a shuffle of $X$
and $Y$ if it has length $|X|+|Y|$ and contains $X$ and $Y$ as subwords.
Denote by $\langle X,Y\rangle$ the set of all shuffles of $X$ and $Y$ that
start with the first symbol of $X$ and end with the last symbol of $Y$. We
denote by $\langle s,Y\rangle$ any set of the form $\langle*^{a},Y\rangle$,
and similarly for $\langle X,s\rangle$.

######  Lemma 4.14.

Let $X$ be a non-empty word on $\\{+,-\\}$.

  1. (1)

If $Y\in\langle s,X\rangle$ then $Y\leq W(X*)$;

  2. (2)

If $Y\in\langle X,s\rangle$ then $Y\leq W(*X)$.

###### Proof.

(1) Write $X=x_{1}\dots x_{r}$. By Lemma 4.9 (2),
$*^{a}x_{i}\leq\widehat{x_{i}}[x_{i},x_{i+1}]$ for all $1\leq i<r$ and
$*^{a}x_{r}\leq\widehat{x_{r}}[x_{r},*]$; concatenating yields the desired
inequality. The proof of (2) is the same, using Lemma 4.9 (3) instead. ∎

######  Proposition 4.15.

Let $X,Y$ be words on $\mathcal{A}$ such that $Y^{\prime}\not\geq X^{\prime}$.
Then $Y\leq W(X^{\prime})$ and in particular $Y\leq W(X)$.

###### Proof.

Since $W(X^{\prime})\leq W(X)$ by Lemma 4.11 (5) it suffices to prove that
$Y\leq W(X^{\prime})$. Write $X^{\prime}=x_{1}\dots x_{r}$ and
$Y^{\prime}=y_{1}\dots y_{k}$. Suppose first that $k<r$. By Lemma 4.9 (2) we
have for any $a\leq n$ that $*^{a}y_{i}\leq\widehat{x_{i}}[x_{i},x_{i+1}]$ for
all $i$ and $*^{a}\leq\widehat{x_{k+1}}$; since $Y$ is obtained from
$Y^{\prime}$ by inserting $*$’s, it follows that $Y\leq W(X^{\prime})$.

Now we prove the result for $k\geq r-1$ by induction on $k-(r-1)$. If
$k-(r-1)=0$ the previous case holds, so now assume that $k\geq r$ and the
result holds for smaller values. Since $X^{\prime}$ is not a prefix of
$Y^{\prime}$, there exists words $G$, $D$, $E$ and $x,y\in\mathcal{A}$
distinct such that $X^{\prime}=GxD$ and $Y^{\prime}=GyE$; notice that
$\overline{x}=y$ and $\overline{y}=x$.

(i) Suppose first that $G=\epsilon$: then
$*^{a}\,\overline{x}\,*^{b}\leq\widehat{x}$ for any $a+b\leq n$ by Lemma 4.9
(1), and by induction hypothesis any word $Z$ with $Z^{\prime}=E$ will satisfy
$Z\leq W(X^{\prime})$. Hence
$Y=*^{a}\,\overline{x}\,*^{b}\,Z\leq\widehat{x}W(X^{\prime})\leq
W(X^{\prime})$.

(ii) Now suppose that $G$ is non-empty. Since $Y^{\prime}=GyE$, $Y$ is of the
form $K*^{a}y*^{b}L$ with $K\in\langle s,G\rangle$ and $L^{\prime}=E$. First
we have that $K\leq W(G*)$ by Lemma 4.14; secondly
$*^{a}\overline{x}*^{b}\leq\widehat{x}$ for all $a+b\leq n$, by Lemma 4.9 (1),
and thirdly, by induction hypothesis, we have that $L\leq W(xD)$ for any word
$L$ such that $L^{\prime}=E$. Since $\widehat{x}W(xD)\leq W(xD)$,
concatenating the above we get $Y\leq W(G*)\widehat{x}W(xD)\leq W(G*)W(xD).$
By Lemma 4.10 (1), if $z$ is the last symbol in G then
$W(G*)W(xD)=W(G)zW(xD)\leq W(G)[z,x]W(xD)=W(GxD)=W(X^{\prime})$ and we are
done.

∎

The next result states that words $X$ and $Y$ such that
$X^{\prime}=Y^{\prime}$ are comparable precisely when their stars align.

######  Lemma 4.16.

Let $X,Y$ be words on $\mathcal{A}$ such that
$X^{\prime}=Y^{\prime}=c_{1}\dots c_{r}$. Write
$X=*^{x_{0}}c_{1}\dots*^{x_{r-1}}c_{r}*^{x_{r}}$ and
$Y=*^{y_{0}}c_{1}\dots*^{y_{r-1}}c_{r}*^{y_{r}}$. Then $X\geq Y$ if and only
if $x_{i}\geq y_{i}$ for all $0\leq i\leq r$.

###### Proof.

Clearly if $x_{i}\geq y_{i}$ for all $i$ we have $X\geq Y$. For the other
direction suppose that $X\geq Y$: by Lemma 2.9 (1) and the fact that an edge-
preserving map cannot send a star to a non-star, it is easy to see that the
monotone map from $X$ onto $Y$ restricted to $X^{\prime}$ is an isomorphism
onto $Y^{\prime}$, and hence must preserve the intervals of $*$’s; the result
follows immediately. ∎

######  Proposition 4.17.

Let $X$ be a word on $\mathcal{A}$ with $X^{\prime}$ is non-empty. If $Y$ is a
word on $\mathcal{A}$ such that $Y^{\prime}=X^{\prime}$ but $Y\not\geq X$ then
$Y\leq W(X)$.

###### Proof.

By Lemma 4.16, if $X^{\prime}=Y^{\prime}$ but $Y\not\geq X$ then the following
holds:

Claim. There exists words $X_{g},Y_{g},X_{d},Y_{d}$ and integers $a>b$ such
that $X=X_{g}*^{a}X_{d}$ and $Y=Y_{g}*^{b}Y_{d}$ where $X_{g},Y_{g}\in\langle
s,X^{\prime}_{g}\rangle$ or are both empty, and $X_{d},Y_{d}\in\langle
X^{\prime}_{d},s\rangle$ or are both empty.

Since $X^{\prime}\neq\epsilon$, at least one of $X^{\prime}_{g}$ or
$X^{\prime}_{d}$ is non-empty: suppose without loss of generality that
$X^{\prime}_{d}\neq\epsilon$. Then by Lemma 4.14 we have that $Y_{d}\leq
W(*X^{\prime}_{d})$. Suppose first that $X^{\prime}_{g}$ is empty. Then
$Y=*^{b}\,Y_{d}\leq*^{a-1}W(*X^{\prime}_{d})\leq*^{a-1}W(*X_{d})=W(*)*^{a-1}W(*X_{d})=W(*^{a}X_{d})=W(X)$
by Lemma 4.11 (2) and (5). On the other hand if $X^{\prime}_{g}$ is non-empty,
then by Lemma 4.14 $Y_{g}\leq W(X^{\prime}_{g}*)$, so
$Y=Y_{g}\,*^{b}\,Y_{d}\leq
W(X^{\prime}_{g}*)\,*^{a-1}W(*X^{\prime}_{d})=W(X^{\prime}_{g}\,*^{a}\,X^{\prime}_{d})\leq
W(X_{g}*^{a}X_{d})=W(X)$ by Lemma 4.11 (2) and (5).

∎

Let $\mathbb{G}$ be an $n$-cycle that fails the path condition. By Theorem 3.9
there exists a subpath $\mathbb{P}$ of $\mathbb{G}$ of length $n-1$ and a
subpath $\mathbb{Q}$ of $\mathbb{G}$ of length $n-2$ such that
$\mathbb{Q}\not\leq W(\mathbb{P})$. The next result uses the previous two
propositions to give a sharper description of such cycles.

######  Proposition 4.18.

Let $\mathbb{G}=C(\mathbb{P}\,e)=C(\mathbb{Q}\,xy)$ be an $n$-cycle, where
$\mathbb{P},\mathbb{Q}$ are words on $\mathcal{A}$ and $x,y,e\in\mathcal{A}$.
If $\mathbb{Q}\not\leq W(\mathbb{P})$ then (i) $xy=**$, (ii) $e\in\\{+,-\\}$,
and (iii) there exist words $A,B$ such that $\mathbb{P}^{\prime}=AB$ and
either $\mathbb{Q}^{\prime}=AeB$ or $\mathbb{Q}^{\prime}=A\overline{e}B$.

###### Proof.

By Propositions 4.15 and 4.17 we must have that
$\mathbb{Q}^{\prime}>\mathbb{P}^{\prime}$; in particular, $\mathbb{Q}$ must
contain the edge $e$ outside $\mathbb{P}$, and $e\neq*$; (iii) also follows.
Now
$|\mathbb{Q}^{\prime}|\leq|\mathbb{G}^{\prime}|=|\mathbb{P}^{\prime}|+1\leq|\mathbb{Q}^{\prime}|$
implies $xy=**$. ∎

For the remainder of this subsection, $\mathbb{G}$ is an $n$-cycle failing the
path condition, as witnessed by a subpath $\mathbb{P}$ of $\mathbb{G}$ of
length $n-1$; $\mathbb{Q}$ is a subpath of $\mathbb{G}$ of length $n-2$ such
that $\mathbb{Q}\not\leq W(\mathbb{P})$.

######  Lemma 4.19.

There exist words $A,B,C,D,T,U$, $z\in\\{+,-\\}$ and an integer $k\geq 0$ such
that $\mathbb{P}=ATB$ and $\mathbb{Q}=CUD$ with

  1. (1)

$A^{\prime}=C^{\prime}$, $B^{\prime}=D^{\prime}$, $T^{\prime}=z^{k}$,
$U^{\prime}=z^{k+1}$,

  2. (2)

if $A^{\prime}\neq\epsilon$ then its last symbol is $\overline{z}$; if
$B^{\prime}\neq\epsilon$ then its first symbol is $\overline{z}$;

  3. (3)

$A,C$ do not end with a $*$; $B,D$ do not start with a $*$.

###### Proof.

By Proposition 4.18 we can find words $X,Y$ such that $\mathbb{P}^{\prime}=XY$
and $\mathbb{Q}^{\prime}=XzY$. Choose $X$ the shortest possible in such a
decomposition; if it is non-empty then clearly it must end with
$\overline{z}$. Now let $W$ be the longest suffix of $Y$ that starts with
$\overline{z}$ (if no such word exits then $W=\epsilon$). Then clearly
$\mathbb{P}^{\prime}=Xz^{k}W$ and $\mathbb{Q}^{\prime}=Xz^{k+1}W$ where $k\geq
0$. To complete the proof it suffices to insert the stars in the appropriate
places. ∎

######  Proposition 4.20.

In the above decomposition, $C\geq A$ and $D\geq B$.

###### Proof.

We prove the result by contradiction: we show that, if $\mathbb{P}$ and
$\mathbb{Q}$ admit the decomposition of Lemma 4.19 and $C\not\geq A$ or
$D\not\geq B$ then $\mathbb{Q}\leq W(\mathbb{P})$; by symmetry it suffices to
consider the case $C\not\geq A$. In that case $A\neq\epsilon$ so $A=A_{1}a$
with $a=\overline{z}$ by Lemma 4.19 (2) and (3).

  1. (1)

$C\leq W(A)$ by Proposition 4.17.

  2. (2)

$U\leq\widehat{a}$ by repeated applications of Lemma 4.9 (1) with
$x=a=\overline{z}$.

  3. (3)

$D\leq W(*B)$; indeed, if $D=\epsilon$ the result is trivial. Otherwise by
Lemma 4.19 (3) we have that $D\in\langle D^{\prime},s\rangle=\langle
B^{\prime},s\rangle$ so $D\leq W(*B^{\prime})\leq W(*B)$ by Lemma 4.14 (2) and
Lemma 4.11 (5).

Now if we concatenate the above we get that $\mathbb{Q}=CUD\leq
W(A)\widehat{a}\,W(*B)\leq W(A)W(*B)$ by Lemma 4.10 (3). If $B=\epsilon$ the
result follows easily; otherwise by Lemma 4.19 (2) and (3) we have $B=aB_{1}$;
by Lemma 4.11 (1) and (5) we get

$W(A)W(*B)=W(A)a\,W(B)=W(A)[a,a]W(B)=W(AB)\leq W(ATB)=W(P).$

∎

Knowing that $\mathbb{P}$ contains exactly two more $*$’s than $\mathbb{Q}$,
and that $C\geq A$ and $D\geq B$ by Proposition 4.20, a simple counting
argument using Lemma 4.16 shows that $T$ contains at least two more $*$’s than
$U$, and in particular $|T|\geq|U|+1$ so it is not empty.)

######  Lemma 4.21.

$U\not\leq W(T)$.

###### Proof.

By the argument used in (3) of the proof of Proposition 4.20 we have that
$C\leq W(A*)$ and $D\leq W(*B)$. Let us now suppose that neither $A$ nor $B$
is empty (otherwise the argument is quite similar): let $A=A_{1}a$ and
$B=bB_{1}$, and let $u$ and $v$ denote the first and last symbol of $T$. If
$U\leq W(T)$, we get by Lemma 4.11 (1) that

$\displaystyle\mathbb{Q}=CUD\leq W(A*)W(T)W(*B)$
$\displaystyle=W(A)aW(T)bW(B)$ $\displaystyle\leq W(A)[a,u]W(T)[v,b]W(B)$
$\displaystyle=W(ATB)=W(\mathbb{P}),$

a contradiction.

∎

We can now refine Lemma 4.19:

######  Lemma 4.22.

There exist words $\underline{A},\underline{B},\underline{C},\underline{D}$ on
$\mathcal{A}$, $z\in\\{+,-\\}$ and an integer $t\geq 2$ such that

  1. (1)

$\mathbb{P}=\underline{A}*^{t}\underline{B}$ and
$\mathbb{Q}=\underline{C}z\underline{D}$;

  2. (2)

$\underline{A}^{\prime}=\underline{C}^{\prime}$,
$\underline{B}^{\prime}=\underline{D}^{\prime}$;

  3. (3)

$\underline{C}\leq W(\underline{A}*)$ and $\underline{D}\leq
W(*\underline{B})$;

  4. (4)

there exist integers $a,b$ and words ${}_{A}X,{{}_{B}X},X_{C},X_{D}$ such that
$\underline{A}={{}_{A}X}*^{a}$, $\underline{C}={{}_{C}X}*^{a}$,
$\underline{B}=*^{b}X_{B}$, $\underline{D}=*^{b}X_{D}$ where
${{}_{A}X},{{}_{C}X}$ do not end with $*$ and $X_{B},X_{D}$ do not start with
$*$(in other words, $\underline{A}$ and $\underline{C}$ end with the same
number of $*$’s and $\underline{B}$ and $\underline{D}$ start with the same
number of $*$’s);

  5. (5)

If $t=2$, then $\underline{A}=\underline{C}$ and
$\underline{B}=\underline{D}$.

###### Proof.

Let $U=*^{u_{0}}z\dots*^{u_{k}}z*^{u_{k+1}}$ and
$T=*^{t_{0}}z\dots*^{t_{k-1}}z*^{t_{k}}$. Recall that
$\sum_{i=0}^{k}t_{i}>\sum_{i=0}^{k+1}u_{i}$ by the comments just prior to
Lemma 4.21.

Claim 1. There exist indices $l\leq r$ such that $u_{l}<t_{l}$ and
$u_{r+1}<t_{r}$.

Proof of Claim 1. We use induction on $k$. If $k=0$ the result is immediate.
Now suppose that $k\geq 1$ and the result holds for smaller values. Since
$\sum_{i=0}^{k}t_{i}>\sum_{i=0}^{k}u_{i}$ and
$\sum_{i=0}^{k}t_{i}>\sum_{i=1}^{k+1}u_{i}$, there exist indices $l$ and $r$
such that $u_{l}<t_{l}$ and $u_{r+1}<t_{r}$; it remains to show that there are
such indices such that $l\leq r$. If $u_{0}<t_{0}$ or $u_{k+1}<t_{k}$ we are
done, so assume that $u_{0}\geq t_{0}$ and $u_{k+1}\geq t_{k}$. It follows
that $\sum_{i=1}^{k-1}t_{i}>\sum_{i=1}^{k}u_{i}$ and we can use the induction
hypothesis to conclude.

Claim 2. For any indices satisfying the conditions of Claim 1, $l=r$.

Proof of Claim 2. We prove this by contradiction: suppose that $u_{l}<t_{l}$
and $u_{r+1}<t_{r}$ and $l<r$: we shall deduce that $U\leq W(T)$,
contradicting Lemma 4.21. Since $l<r$, we can write
$T=T_{l}*^{t_{l}}T_{c}*^{t_{r}}T_{r}$ and
$U=U_{l}*^{u_{l}}U_{c}*^{u_{r}}U_{r}$ where for some $m\geq 0$ we have
$T^{\prime}_{c}=z^{m}$, $U^{\prime}_{c}=z^{m+1}$,
$T^{\prime}_{l}=U^{\prime}_{l}$ and $T^{\prime}_{r}=U^{\prime}_{r}$;
furthermore $U_{l}$ does not end with $*$, $U_{r}$ doesn’t start with $*$, and
$U_{c}$ starts and ends with $z$.

  1. (1)

$U_{l}\leq W(T_{l}*)$: same argument as used in (3) of the proof of
Proposition 4.20;

  2. (2)

$U_{r}\leq W(*T_{r})$: same comment.

  3. (3)

$U_{c}\leq W(*T_{c}*)$: indeed, for some $a_{i}$ we have

$U_{c}=(z*^{a_{1}})(z*^{a_{2}})\cdots(z*^{a_{m}})z\leq(z\widehat{z})^{m}z=z(\widehat{z}z)^{m-1}\widehat{z}z=W(*z^{m}*)=W(*T^{\prime}_{c}*)\leq
W(*T_{c}*)$

using Lemma 4.11 (5) for the last inequality.

If we concatenate the above, and using the fact that
$*^{u_{l}}\leq*^{t_{l}-1}$ and $*^{u_{r+1}}\leq*^{t_{r}-1}$ we get

$\displaystyle U=U_{l}*^{u_{l}}U_{c}*^{u_{r}}U_{r}$ $\displaystyle\leq
W(T_{l}*)*^{t_{l}-1}W(*T_{c}*)*^{t_{r}-1}W(*T_{r})$
$\displaystyle=W(T_{l}*^{t_{l}}T_{c}*^{t_{r}}T_{r})=W(T)$

using Lemma 4.11 (2) twice.

By Claims 1 and 2 there is an index $j$ such that $u_{j}<t_{j}$ and
$u_{j+1}<t_{j}$. Then we can write $U=U_{l}*^{u_{j}}z*^{u_{j+1}}U_{r}$ and
$T=T_{l}*^{t_{j}}T_{r}$. By Claim 2 we have $u_{i}\geq t_{i}$ for all $i\leq
j-1$ and $u_{i+1}\geq t_{i}$ for all $i\geq j+1$; since $T$ contains at least
two stars more than $U$ it follows that we can write $t_{j}=u_{j}+u_{j+1}+t$
for some $t\geq 2$. Clearly $T^{\prime}_{l}=U^{\prime}_{l}$ and
$T^{\prime}_{r}=U^{\prime}_{r}$. Let $\underline{A}=AT_{l}*^{u_{j}}$,
$\underline{B}=*^{u_{j+1}}T_{r}B$, $\underline{C}=CU_{l}*^{u_{j}}$ and
$\underline{D}=*^{u_{j+1}}U_{r}D$. It is immediate that
$\underline{A}^{\prime}=\underline{C}^{\prime}$ and
$\underline{B}^{\prime}=\underline{D}^{\prime}$. Notice that (4) is satisfied
by construction and Lemma 4.19.

Since $U_{l}$ does not end with a star, we use the argument in (3) of the
proof of Proposition 4.20 to get that $CU_{l}\leq W(AT_{l}*)$ and thus

$\underline{C}=CU_{l}*^{u_{j}}\leq
W(AT_{l}*)*^{u_{j}}=W(AT_{l}*^{u_{j}+1})=W(\underline{A}*)$

using Lemma 4.11 (2). The argument for the other inequality is identical.

Finally we prove (5): suppose $t=2$. One verifies easily, using Proposition
4.20 and Lemma 4.16 that $\underline{A}\leq\underline{C}$ and
$\underline{B}\leq\underline{D}$. For any word $X$ let
$\sigma(X)=|X|-|X^{\prime}|$, i.e. the number of stars in $X$. Since
$\mathbb{G}=C(\mathbb{P}e)=C(\mathbb{Q}{*}{*})$ we have that
$\sigma(\mathbb{P})=\sigma(\mathbb{Q})+2$. By Lemma 4.16,
$\underline{A}\leq\underline{C}$ and $\underline{B}\leq\underline{D}$ implies
$\sigma(\underline{A})\leq\sigma(\underline{C})$ and
$\sigma(\underline{B})\leq\sigma(\underline{D})$. Then
$\sigma(\mathbb{P})=\sigma(\underline{A})+\sigma(\underline{B})+2\leq\sigma(\underline{C})+\sigma(\underline{D})+2=s(\mathbb{Q})+2$
so $\sigma(\underline{A})=\sigma(\underline{C})$ and
$\sigma(\underline{B})=\sigma(\underline{D})$; applying Lemma 4.16 again we
get $\underline{A}=\underline{C}$ and $\underline{B}=\underline{D}$. ∎

We require the following extension of Lemma 4.10 (1): not only do we have
$W(X)\not\geq X$, but this holds if we replace any number of $*$’s in $W(X)$
by any choice of $+$’s and $-$’s.

######  Lemma 4.23.

Let $X$ be a non-empty word, let $Y$ be a word with a subword $Z$ on
$\\{+,-\\}$ such that replacing every symbol of $Z$ by $*$ in $Y$ yields the
word $W(X)$. Then $Y\geq W(X)$ and $Y\not\geq X$.

###### Proof.

The first inequality is immediate. To prove the second statement we use
induction on the length of $X$. Since every $*$ of $W(X)$ can only appear as
$[*,*]$, if $X$ does not contain consecutive $*$’s then $W(X)$ contains no
$*$’s and the result is trivial (in particular if $|X|=1$). If $Z=\epsilon$
then $Y=W(X)$ and the result holds by Lemma 4.10 (1), so we suppose that
$Z\neq\epsilon$. So write $X=A**B$ where the middle $**$ corresponds to a
symbol in the subword $Z$. By Lemma 4.11 (2) we have that
$W(A**B)=W(A*)*W(*B)$. Thus $Y=Y_{1}zY_{2}$ where $z\in\\{+,-\\}$, and $Y_{1}$
(respectively $Y_{2}$) is obtained from $A*$ (respectively $*B$) by replacing
various $*$’s by any choice of $+$’s and $-$’s. By induction hypothesis, we
have that $Y_{1}\not\geq A*$ and $Y_{2}\not\geq*B$. By Lemma 2.9 (1), if
$Y_{1}zY_{2}\geq A**B$ and $Y_{1}\not\geq A*$ then we must have
$zY_{2}\geq**B$ which implies $Y_{2}\geq*B$ by Lemma 2.9 (5), a contradiction.
∎

######  Definition 4.24.

Let $\mathbb{Q}$ be any subpath of $\mathbb{G}$ of length $n-2$ such that
$\mathbb{Q}\not\leq W(\mathbb{P})$. Then Lemma 4.22 gives a representation of
$\mathbb{P}$ and $\mathbb{Q}$ that identifies a substring of $*$’s in the word
$W(\mathbb{P})$ as follows: we have that
$W(\mathbb{P})=W(\underline{A}*^{t}\underline{B})=W(\underline{A}*)*^{t-1}W(*\underline{B})$
by Lemma 4.11 (2). Let $p(\mathbb{Q})=\\{i:|W(\underline{A}*)|+1\leq
i\leq|W(\underline{A}*)|+(t-1)\\}$. Let $s(\mathbb{Q})=z$ (in the
representation given in Lemma 4.22).

######  Proposition 4.25.

Let $\mathbb{G}$ be an $n$-cycle failing the path condition, as witnessed by
the subpath $\mathbb{P}$ of length $n-1$. Then there exist subpaths
$\mathbb{Q},\mathbb{R}$ of $\mathbb{G}$ of length $n-2$, words $A,B,C,D,E,F$
on $\mathcal{A}$ and an integer $t\geq 2$ such that

  1. (1)

$\mathbb{G}=C(\mathbb{P}e)=C(\mathbb{Q}**)=C(\mathbb{R}**)$ for some
$e\in\\{+,-\\}$,

  2. (2)

$p(\mathbb{Q})\subseteq p(\mathbb{R})$,

  3. (3)

$\mathbb{P}=A*^{2}B=C*^{t}D$,

  4. (4)

$\mathbb{Q}=A+B$ and $\mathbb{R}=E-F$,

  5. (5)

$C$ and $E$ end with the same number of $*$’s;
$D$ and $F$ start with the same number of $*$’s;

  6. (6)

$A^{\prime}=C^{\prime}=E^{\prime}$ and $B^{\prime}=D^{\prime}=F^{\prime}$.

###### Proof.

Claim 1. There exist $\mathbb{Q},\mathbb{R}\not\leq W(\mathbb{P})$ such that
$s(\mathbb{Q})\neq s(\mathbb{R})$, $p(\mathbb{Q})\subseteq p(\mathbb{R})$ and
$|p(\mathbb{Q})|=1$.

Proof of Claim 1. It follows immediately from Lemma 4.22 and Definition 4.24
that, if $Y$ is obtained from $W(\mathbb{P})$ by replacing a $*$ whose
position is in $p(\mathbb{Q})$ by $s(\mathbb{Q})$, then $\mathbb{Q}\leq Y$.
Suppose for a contradiction that our claim is false. We define a word $Y$ by
replacing $*$’s in $W(\mathbb{P})$ as follows: for every $\mathbb{Q}\not\leq
W(\mathbb{P})$ such that $|p(\mathbb{Q})|=1$, change the $*$ in that position
by $s(\mathbb{Q})$ (this is well-defined, by hypothesis). The remaining
subword of $*$’s of $W(\mathbb{P})$ is replaced by an alternation $(+-)^{r}$.
We claim that $Y\geq\mathbb{Q}$ for every $\mathbb{Q}\not\leq W(\mathbb{P})$.
Indeed, this is clear if $p(\mathbb{Q})$ contains $p(\mathbb{R})$ with
$|p(\mathbb{R})|=1$ since in that case $s(\mathbb{Q})=s(\mathbb{R})$.
Otherwise, $p(\mathbb{Q})$ is an interval of size at least 2 and hence must
contain positions of $*$’s that we replaced by $+$ and $-$. By Lemma 4.23,
this contradicts the failure of the path condition witnessed by $\mathbb{P}$.

We get (1) from Claim 1 and Proposition 4.18. Since $|p(\mathbb{Q})|=1$, it
means that $t=2$ in the representation for $\mathbb{P}$ and $\mathbb{Q}$; then
all the statements of our proposition follow from Lemma 4.22 except
$A^{\prime}=C^{\prime}$ and $B^{\prime}=D^{\prime}$. We have that

$W(\mathbb{P})=W(A*)*W(*B)=W(C*)*^{t-1}W(*D)$

and since $p(\mathbb{Q})\subseteq p(\mathbb{R})$ we have that
$W(A*)=W(C*)*^{s}$ and $W(*B)=*^{r}W(*D)$ for some $s,r\geq 0$. The result
will then follow from the next two claims:

Claim 2. Let $Y$ be a proper, non-empty prefix of $X$. Then $|W(Y*)|<|W(X*)|$.

Proof of Claim 2. This is straightforward and left to the reader.

Claim 3. Let $X$ and $Y$ be words such that one is a prefix of the other, and
let $s\geq 0$. If $W(X*)=W(Y*)*^{s}$ then $X^{\prime}=Y^{\prime}$. If $X$ and
$Y$ are such that one is a suffix of the other and $W(*X)=*^{s}W(*Y)$ then
$X^{\prime}=Y^{\prime}$.

Proof of Claim 3. We prove the first statement, the argument for the other is
identical. We may suppose neither $X$ nor $Y$ is empty; we use induction on
$s$. If $s=0$ then $X=Y$ by the previous claim. Suppose the result holds for
some fixed $s\geq 0$. If $W(X*)=W(Y*)*^{s+1}$ then $|W(Y*)|<|W(X*)|$ so $Y$ is
a proper prefix of $X$ by the last claim. We also have that $W(X*)$ ends with
a $*$ which means that $X=X_{1}*$ for some $X_{1}$. Then
$W(Y*)*^{s+1}=W(X_{1}**)=W(X_{1}*)*$ by Lemma 4.11 (2). Thus
$W(X_{1}*)=W(Y*)*^{s}$ where $Y$ is a prefix of $X_{1}$ so by induction
hypothesis we have that $Y^{\prime}=X_{1}^{\prime}=X^{\prime}$ and we are
done.

∎

######  Definition 4.26.

Let $W$ be a word on $\\{+,-,*\\}$. Define the height $h(W)$ of $W$ as the
number of $+$ in $W$ minus the number of $-$ in $W$.

Clearly $h(UV)=h(U)+h(V)$, $h(\overline{W})=-h(W)$ and $h(U^{\prime})=h(U)$
for any words $U,V,W$. In particular, if a word $W$ is self-dual then
$h(W)=0$.

######  Lemma 4.27.

If $W,Z$ are words such that $C(W)=C(Z)$ then $h(W)=\pm h(Z)$;
furthermore, if $h(W)\neq 0$ then the following are equivalent:

  1. (1)

$h(W)\neq h(\overline{Z})$;

  2. (2)

$h(W)=h(Z)$;

  3. (3)

there exist words $U$ and $V$ such that $W=UV$ and $Z=VU$.

###### Proof.

The first statement is clear. Now suppose $h(Z)\neq 0$. Then (3) implies (2)
and (2) implies (1) are immediate. Now suppose that $h(W)\neq
h(\overline{Z})$. Since $Z$ represents the same cycle as $W$, either $Z$ or
$\overline{Z}$ is a “rotation” of $W$, i.e. of the form $VU$ where $W=UV$. But
since $h(\overline{Z})\neq h(W)$, $\overline{Z}$ cannot be obtained this way,
so the result follows. ∎

######  Lemma 4.28.

Let $A,B,E,F$ be words such that $A^{\prime}=E^{\prime}$ and
$B^{\prime}=F^{\prime}$.
If $C(A+B**)=C(E-F**)$, then $B**A=\overline{E}**\,\overline{F}$.

###### Proof.

We have that $h(A)=h(E)$ and $h(B)=h(F)$. Since $h(A+B**)=h(A)+h(B)+1\neq
h(A)+h(B)-1=h(E-F**)$, by Lemma 4.27 we must have $h(A)+h(B)+1=-(h(A)+h(B)-1)$
so $h(A)+h(B)=0$; in particular the cycle has non-zero height and we can apply
the second part of Lemma 4.27: there exist words $U,V$ such that $B**A+=UV$,
and $\overline{E}**\,\overline{F}+=VU$. Suppose for a contradiction that
$|U||V|\geq 1$; then both $U^{\prime}$ and $V^{\prime}$ are non-empty and end
with a $+$. Applying ′ to both sides of these equalities we get

  1. (i)

$B^{\prime}A^{\prime}+=U^{\prime}V^{\prime}$,

  2. (ii)

$\overline{A^{\prime}}\overline{B^{\prime}}+=V^{\prime}U^{\prime}$.

and it follows from (i) that we must have $|U^{\prime}|\leq|B^{\prime}|$ or
$|V^{\prime}|\leq|A^{\prime}|$. The argument is identical in both cases, so
assume $|U^{\prime}|\leq|B^{\prime}|$: by (i) there exists words $B_{1}$,
$B_{2}$ such that $U^{\prime}=B_{1}+$ and $B^{\prime}=B_{1}+B_{2}$. Then by
(ii) we get

$V^{\prime}U^{\prime}=\overline{A^{\prime}}\overline{B_{2}}-\overline{B_{1}}+$

and comparing the lengths of the suffixes we conclude that $V^{\prime}$ must
end with $-$, a contradiction.

∎

We can now give the proof of the main result of this section:

Proof of Theorem 4.6:

Consider the decomposition of paths $\mathbb{P}$, $\mathbb{Q}$ and
$\mathbb{R}$ given by Proposition 4.25: we prove that we have $t=2$. Indeed,
there exist words $A_{1},B_{1},C_{1},D_{1},E_{1},F_{1}$ and integers
$a,b,e,f\geq 0$ such that $A=A_{1}*^{a}$, $E=E_{1}*^{e}$, $C=C_{1}*^{e}$,
$B=*^{b}B_{1}$, $F=*^{f}F_{1}$, $D=*^{f}D_{1}$, and $A_{1},C_{1},E_{1}$ do not
end with $*$ and $B_{1},D_{1},F_{1}$ do not start with $*$. Then
$A**B=A_{1}*^{a+2+b}B_{1}=C_{1}*^{e+t+f}D_{1}$, and since
$A^{\prime}_{1}=A^{\prime}=C^{\prime}=C^{\prime}_{1}$ we conclude that
$a+2+b=e+t+f$.

On the other hand, we have that $C(A+B**)=C(E-F**)$ and
$A^{\prime}=E^{\prime}$, $B^{\prime}=F^{\prime}$ so Lemma 4.28 gives us that
$B**A=\overline{E}**\overline{F}$. Thus
$*^{b}B_{1}**A_{1}*^{a}=*^{e}\overline{E_{1}}**\overline{F_{1}}*^{f}$, so
$b=e$ and $a=f$. Then $t=2$.

It follows from Lemma 4.22 (5) that $C=E$ and $D=F$; since $A**B=C**D$ and
$p(\mathbb{Q})\subseteq p(\mathbb{R})$ by Proposition 4.25 (2), we have that
$|W(A*)|=|W(C*)|$ so $A=C$ by Claim 2 in Proposition 4.25. We conclude that
$A=C=E$ and $B=D=F$.

Now suppose that $e=+$ in the decomposition: then
$\mathbb{G}=C(A+B**)=C(A-B**)=C(A**B+)$ and we are done. If $e=-$, then
$\mathbb{G}=C(A+B**)=C(A-B**)=C(A**B-)$; reading the words “backwards”, we get
the desired decomposition using $\overline{B}$ and $\overline{A}$ instead of
$A$ and $B$.

∎

###  4.2. Proof of Theorem 4.2

We now proceed to finish the proof of Theorem 4.2. We require a few more
lemmas. Yes. Sorry.

######  Lemma 4.29.

Let $A$ and $B$ be words such that $C(A-B**)=C(A**B+)$. Then $\overline{A}=A$
and $\overline{B}=B$.

###### Proof.

Since $h(A-B**)=h(A)+h(B)-1\neq h(A)+h(B)+1=h(A**B+)$, by Lemma 4.27 we must
have $h(A)+h(B)+1=h(A**B+)=h(\overline{A}**\overline{B}+)=-h(A)-h(B)+1$, so
$h(A)+h(B)=0$; in particular the cycle has non-zero height and we can apply
the second part of Lemma 4.27: there exist words $U,V$ such that

  1. (i)

$\overline{A}**\overline{B}+=UV$,

  2. (ii)

$A**B+=VU$.

Suppose for a contradiction that $|U||V|\geq 1$; then both $U$ and $V$ end
with a $+$, and it follows from (ii) that we must have $|V|\leq|A|$ or
$|U|\leq|B|$. Suppose first that $|U|\leq|B|$: it follows from (ii) that there
exist words $B_{1}$, $B_{2}$ and $b\in\\{+,-,*\\}$ such that $B=B_{1}bB_{2}$
and $U=B_{2}+$. Then $V=A**B_{1}b$ so concatenating we get

$UV=B_{2}+A**B_{1}\,b$

But from (i) we get

$UV=\overline{A}**\overline{B_{2}}\,\overline{b}\,\overline{B_{1}}+$

and comparing the suffixes of length $|B_{1}|+2$ we obtain $b=+$ and
$\overline{b}=*$, a contradiction. Now suppose that $|V|\leq|A|$: then by (ii)
there exist words $A_{1}$ and $A_{2}$ such that $A=A_{1}+A_{2}$ and
$V=A_{1}+$; then $U=A_{2}**B+$ and concatenating we get that

$UV=A_{2}**B+A_{1}+$

But from (i) we get

$UV=\overline{A_{2}}-\overline{A_{1}}**\overline{B}+$

and comparing the prefixes of length $|A_{2}|+1$ we obtain $*=-$ another
contradiction. ∎

######  Lemma 4.30.

Let $A,B$ be words on $\\{+,-,*\\}$ such that $A**\,B=B**\,A$. Then there
exist integers $k,l\geq 0$ such that one of the following holds:

  1. (1)

$A=(*)^{k}$ and $B=(*)^{l}$, or

  2. (2)

there exists a word $S$ such that $A=(S**)^{k}\,S$ and $B=(S**)^{l}\,S$;
furthermore, if $\overline{A}=A$ or $\overline{B}=B$ then $\overline{S}=S$.

###### Proof.

We prove the result by induction on $|A|+|B|$. If $|A|=|B|$ then clearly $A=B$
and we may take $k=l=0$ and $S=A=B$. Thus by symmetry of the statement we may
now suppose without loss of generality that $|A|<|B|$.

  1. (i)

Suppose first that $|B|=|A|+1$. We get that $B=A\,*=*\,A$. It follows easily
that $A=(*)^{k}$ and $B=(*)^{k+1}$ for some $k$.

  2. (ii)

Suppose that $|B|=|A|+2$. We get that $B=A\,**=**\,A$. It is easy to see that
in this case $A=(*)^{k}$ and $B=(*)^{k+2}$ for some $k$.

(Notice that, in particular, the above proves the statement for $|A|+|B|\leq
2$.)

  3. (iii)

Now suppose that $|B|>|A|+2$; then considering the prefixes in $A**\,B=B**\,A$
we can write $B=A\,**\,W$ for some non-empty word $W$. Then we get
$A**\,A\,**\,W=A\,**\,W**\,A$ and considering suffixes we conclude that
$A\,**\,W=W**\,A$. Since $|W|<|B|$, by induction hypothesis we have that
either both $A$ and $W$ are of the form $(*)^{q}$ and thus $B$ also, or
otherwise there exists some word $S$ such that $A=(S**)^{k}\,S$ and
$W=(S**)^{l}\,S$. Then
$B=A\,**\,W=(S**)^{k}\,S\,**\,(S**)^{l}\,S=(S**)^{k+l+1}\,S$ and we are done.

To prove the second statement in (2), simply compare prefixes in
$(S**)^{q}\,S$ and
$\overline{(S**)^{q}\,S}=\overline{S}\,\overline{(S**)^{q}}$.

∎

Proof of Theorem 4.2: One direction has been proved in Lemmas 4.4 and 4.5. Let
$\mathbb{G}$ be a cycle that fails the path condition; we must show it has the
desired form. By Theorem 4.6, there exist words $A$ and $B$ such that
$\mathbb{G}=C(A**B+)=C(A+B**)=C(A-B**)$. By Lemma 4.28 (with $E=A$ and $F=B$)
we get that $B**A=\overline{A}**\overline{B}$; by Lemma 4.29 we get that
$\overline{A}=A$ and $\overline{B}=B$; together these give $A**B=B**A$ so we
conclude using Lemma 4.30. ∎

##  5\. Cycles without the path condition are Słupecki

In a companion paper [9], we prove a criterion that guarantees that under
certain technical conditions, a reflexive digraph is Słupecki; in particular
it applies to any reflexive digraph that triangulates a sphere. Since cycles
clearly triangulate a circle, we can apply this criterion:

######  Theorem 5.1.

[9] Let $\mathbb{G}$ be an $n$-cycle with $n\geq 4$. If for every $p\geq 2$
and every onto polymorphism $f:\mathbb{G}^{p}\rightarrow\mathbb{G}$ there
exists an embedding $e:\mathbb{G}\hookrightarrow\mathbb{G}^{p}$ such that the
restriction of $f$ to $e(\mathbb{G})$ is onto then $\mathbb{G}$ is Słupecki. ∎

We now apply Theorem 5.1 to show that the remaining cycles, those that do not
satisfy the path condition, are Słupecki: once an arbitrary onto polymorphism
is fixed, the copy of $\mathbb{G}$ in $\mathbb{G}^{p}$ on which $f$ is onto is
built by glueing together various paths.

######  Lemma 5.2.

If $\mathbb{G}=C(W)$ is an $n$-cycle with $h(W)=1$ then $Aut(\mathbb{G})$ is
trivial.

###### Proof.

The automorphisms of $\mathbb{G}$ are certainly automorphisms of the
undirected cycle and thus are either rotations or reflections. Choose an
orientation and denote by $\tau_{k}$ the rotation sending $0$ to $k$
“clockwise”. Suppose for a contradiction that $Aut(\mathbb{G})$ is non-
trivial; if it contains some $\tau_{k}$ with $1<k<n$ then because $\tau_{n}$
is also an automorphism, applying Bézout’s lemma, $Aut(\mathbb{G})$ contains
the rotation $\tau_{d}$ where $d$ is the gcd of $k$ and $n$; this implies that
the word $W$ can be written as $V^{m}$ where $dm=n$. But $1=h(W)=mh(V)$
implies $m=1$ so $d=n$, a contradiction. Otherwise, $Aut(\mathbb{G})$ contains
a non-trivial reflection $\sigma$; obviously $\sigma$ cannot preserve an
oriented edge, and hence it is easy to see that, if $U$ is a substring of $W$
of maximum length such that $\sigma(U)\cap U=\emptyset$, then
$h(W)=h(U)-h(U)=0$. ∎

######  Lemma 5.3.

Let $s$ be a positive integer.

  1. (1)

$(-+)^{s}-\geq W$ for every word $W$ on $\mathcal{A}$ of length at most $s+1$
except $(+)^{s+1}$;

  2. (2)

$(+-)^{s}\geq W$ for every word $W$ on $\mathcal{A}$ of length at most $s$,
and every $W$ of length $s+1$ containing at least one $*$ except those of the
form $W=(-)^{r}\,*\,(+)^{l}$.

###### Proof.

We shall use the obvious fact that any word $W$ of length at most $k$ is below
both $(+-)^{k}$ and $(-+)^{k}$.

(1) Clearly $(-+)^{s}-\not\geq(+)^{s+1}$. For the other direction, we may
assume $W$ has length $s+1$ and is non-constant. We can then insert at most
$s-1$ symbols from $\\{+,-\\}$ in $W$ to obtain an alternating word of length
at most $2s$; if it has length at most $2s-1$ then we can, if need be, add $-$
at one or both ends; in the case it has length $2s$, since it is alternating
it starts or ends with a $-$ and thus we can add $-$ at the other end and we
are done.

(2) It is easy to see that $(+-)^{s}\not\geq(-)^{r}\,*\,(+)^{l}$ if $r+l=s$.
For the other statement, we can assume $W$ has length $s+1$ and is not of the
form $W=(-)^{r}\,*\,(+)^{l}$. Write $W=W_{1}*W_{2}$ where $|W_{1}|=a$ and
$|W_{1}|=b$ with $a+b=s$. Without loss of generality (the other case is dealt
with using the dual of statement (1)), $W_{2}$ is non-empty and not equal to
$(+)^{b}$. By (1) we have that
$W_{1}*W_{2}\leq(+-)^{a}*(-+)^{b-1}-=(+-)^{a}(*-)(+-)^{b-1}\leq(+-)^{s}$.

∎

Observe that cycles that fail the path condition satisfy a simple necessary
condition: by Theorem 4.2, clearly every such cycle $\mathbb{G}$ of girth at
least 4 is of the form $\mathbb{G}=C(\mathbb{P}+)$ for some self-dual path
$\mathbb{P}$ of length at least 3 which contains at least two $*$’s.

######  Theorem 5.4.

Let $\mathbb{P}$ be a self-dual path such that $|P|\geq 3$ and
$|\mathbb{P}|-|\mathbb{P}^{\prime}|\geq 2$. Then the cycle
$\mathbb{G}=C(\mathbb{P}\,+)$ is Słupecki.

###### Proof.

First notice that since $\mathbb{P}$ is self-dual, $h(\mathbb{P})=0$ so
$Aut(\mathbb{G})$ is trivial by Lemma 5.2. Let $(a,b)$ be the arc of
$\mathbb{G}$ corresponding to the $+$ (see Figure 3). We split the proof in
two cases, according to the parity of $|\mathbb{P}|$, although the structure
of both proofs is the same.

Figure 3. The cycle $\mathbb{G}=C(\mathbb{P}\,+)$ (clockwise, from $b$), with
$|\mathbb{P}|$ even (left) and $|\mathbb{P}|$ odd (right).

  1. (1)

$|\mathbb{P}|$ is odd. Then $\mathbb{P}=\mathbb{T}\,*\,\overline{\mathbb{T}}$
for some path $\mathbb{T}$; let $\\{u,v\\}$ be the vertices incident to the
symmetric edge corresponding to the middle $*$, see Figure 3. Let $t$ denote
the length of $\mathbb{T}$.

Claim 0o. Let $Z=(+-)^{t}$. Then $x\,Z\,y$ for all $x,y\in G$.

Proof of Claim 0o. The cycle has girth $2t+2$, hence the (usual graph)
distance on the cycle from $x$ to $y$ is at most $t+1$. Apply Lemma 5.3 (2):
if the usual graph distance between $x$ and $y$ is $t$ or less we are done;
otherwise $x$ and $y$ are antipodal; since $\mathbb{P}$ contains at least
three $*$, there is a word from $x$ to $y$ of length $t+1$ which contains at
least two $*$ and we are done in this case also.

Claim 1o. For all $x\in G$, either $x\mathbb{T}u$ or $x\mathbb{T}v$.

Proof of Claim 1o. Immediate.

Claim 2o. Let $\\{c,d\\}$ be a symmetric edge of $\mathbb{G}$ such that
$x\mathbb{T}c$ or $x\mathbb{T}d$ for all $x\in G$. Then $\\{c,d\\}=\\{u,v\\}$.

Proof of Claim 2o. Let $c^{\prime}$ and $d^{\prime}$ denote the respective
antipodes of $c$ and $d$ on the cycle; by hypothesis the subpath $\mathbb{Y}$
of $\mathbb{G}$ of length $t$ that connects $d^{\prime}$ and $c$ satisfies
$\mathbb{Y}\leq\mathbb{T}$ and similarly for the subpath $\mathbb{Z}$ of
$\mathbb{G}$ of length $t$ that connects $c^{\prime}$ and $d$. Hence the map
$h:G\rightarrow G$ that sends the path $b\mathbb{T}v$ to the path
$d^{\prime}\mathbb{Y}c$ and the path $a\mathbb{T}u$ to the path
$c^{\prime}\mathbb{Z}d$ is either a bijective endomorphism, or its composition
with the reflection exchanging $c^{\prime}$ and $d^{\prime}$ is. In any case,
we obtain an automorphism of $\mathbb{G}$ mapping the edge $\\{u,v\\}$ to the
edge $\\{c,d\\}$. Since $Aut(\mathbb{G})$ is trivial we are done.

Claim 3o. For any onto polymorphism $f$ from $\mathbb{G}^{p}$ onto
$\mathbb{G}$ we have
$f(\\{u,v\\}^{p})\subseteq\\{u,v\\}$.

Proof of Claim 3o. Since $\\{u,v\\}^{p}$ is a clique,
$f(\\{u,v\\}^{p})\subseteq\\{c,d\\}$ for some symmetric edge $\\{c,d\\}$ of
$\mathbb{G}$. Given any $x\in G$, there exists $\gamma\in G^{p}$ such that
$f(\gamma)=x$. By Claim 1o there exists some $\delta\in\\{u,v\\}^{p}$ such
that $\gamma\mathbb{T}\delta$ and so $x\mathbb{T}f(\delta)\in\\{c,d\\}$. We
conclude by applying Claim 2o.

Let $f$ be a surjective polymorphism from $\mathbb{G}^{p}$ onto $\mathbb{G}$.
Let $\alpha,\beta\in\mathbb{G}^{p}$ such that $f(\alpha)=a$ and $f(\beta)=b$.
By Claim 0o we have $\alpha((-+)^{t})\beta$, and since the longest substring
of $\mathbb{G}$ from $b$ to $a$ has length $2t+1>2t$, the image of
$\alpha((-+)^{t})\beta$ under $f$ must use the arc $(a,b)$; hence without loss
of generality we have that $(\alpha,\beta)$ is an arc in $\mathbb{G}^{p}$. By
Claim 1o there exist $\gamma,\delta\in\\{u,v\\}^{p}$ such that
$\alpha\mathbb{T}\gamma$ and $\beta\mathbb{T}\delta$, and hence
$a\mathbb{T}f(\gamma)$ and $b\mathbb{T}f(\delta)$; by Claim 3o and a simple
distance argument it follows that $f(\gamma)=u$ and $f(\delta)=v$. Because
$\\{u,v\\}^{p}$ is a clique $(\gamma,\delta)$ is a symmetric edge, and the
paths $\alpha\mathbb{T}\gamma$ and $\beta\mathbb{T}\delta$ must both be
isomorphic to $\mathbb{T}$ since their endpoints are mapped to $a$ and $u$,
and to $b$ and $v$ respectively, and so are mapped to the unique path of the
correct length between those. Hence we have found a copy of $\mathbb{G}$ in
$\mathbb{G}^{p}$ on which $f$ is onto, and we conclude using Theorem 5.1.

  2. (2)

$|\mathbb{P}|$ is even. Then $\mathbb{P}=\mathbb{T}\overline{\mathbb{T}}$ for
some path $\mathbb{T}$; let $u$ denote the middle vertex of the path
$\mathbb{P}$, see Figure 3. Let $t$ denote the length of $\mathbb{T}$. Notice
that $t\geq 2$ since $|P|\geq 3$.

Let $\mathbb{P}_{t}=(+)^{t-1}\,**(-)^{t-1}$.

Claim 0e. Let $Z=(-+)^{t-1}-$. If $\mathbb{G}\neq C(\mathbb{P}_{t}\,+)$ then
$x\,Z\,y$ for all $x,y\in G$; in any case $x\,(-+)^{t}\,y$ for all $x,y\in G$.

Proof of Claim 0e. Notice first that $(-+)^{t}\geq Z$, and so if we can prove
$x\,Z\,y$ for a pair $x,y$ then the second statement follows for the same
pair. The cycle has girth $2t+1$, hence the (usual graph) distance on the
cycle from $x$ to $y$ is at most $t$. Applying Lemma 5.3 (1) with $s=t-1$, we
can handle all cases except if there is a path from $x$ to $y$ that equals
$(+)^{t}$; since the arcs incident to $u$ are involutes of one another this
path cannot contain both of them, and since both $\mathbb{T}$ and
$\overline{\mathbb{T}}$ contain a $*$ this path in fact cannot use either of
these arcs. Similarly, the arcs incident to the arc $(a,b)$ are involutes of
one another, so the path cannot contain them both; it follows that unless
$x=a$, $y$ is the neighbour of $u$ at distance $t$ from $a$ and
$\mathbb{T}=(+)^{t-1}\,*$, we do have that $xZy$. For this lone case, we
observe that the remaining part of the cycle (which is $C(\mathbb{P}_{t}\,+)$)
gives $xYy$ where $Y=(+)^{t-1}\,**$, and clearly $(-+)^{t}=(-+)^{t-1}(-+)\geq
Y$.

Claim 1e. $x\mathbb{T}u$ for all $x\in G$.

Proof of Claim 1e. Immediate.

Claim 2e. If $x\mathbb{T}v$ for all $x\in G$ then $v=u$.

Proof of Claim 2e. Let $c$ and $d$ denote the two vertices at distance $t$
from $v$ on the cycle; by hypothesis the subpath $\mathbb{Y}$ of $\mathbb{G}$
of length $t$ that connects $c$ and $v$ satisfies $\mathbb{Y}\leq\mathbb{T}$
and similarly for the subpath $\mathbb{Z}$ of $\mathbb{G}$ of length $t$ that
connects $d$ and $v$. Hence the map $h:G\rightarrow G$ that sends the path
$b\mathbb{T}u$ to the path $c\mathbb{Y}v$ and the path $a\mathbb{T}u$ to the
path $d\mathbb{Z}v$ is either a bijective endomorphism, or its composition
with the reflection that fixes $v$ and exchanges $c$ and $d$ is. In any case,
we obtain an automorphism of $\mathbb{G}$ mapping $u$ to $v$; since
$Aut(\mathbb{G})$ is trivial we are done.

Claim 3e. For any polymorphism $f$ from $\mathbb{G}^{p}$ onto $\mathbb{G}$ we
have
$f(u,u,\dots,u)=u$.

Proof of Claim 3e. This follows from Claims 1e and 2e and the fact that $f$ is
onto.

Let $f$ be a surjective polymorphism from $\mathbb{G}^{p}$ onto $\mathbb{G}$.
Let $\alpha,\beta\in\mathbb{G}^{p}$ such that $f(\alpha)=a$ and $f(\beta)=b$.
Suppose first that $\mathbb{P}\neq\mathbb{P}_{t}$. By Claim 0e we have
$\alpha((-+)^{t-1}-)\beta$, and since the longest substring of $\mathbb{G}$
from $b$ to $a$ has length $2t>2t-1$, the image of $\alpha((-+)^{t-1}-)\beta$
under $f$ must use the arc $(a,b)$; in the case $\mathbb{P}=\mathbb{P}_{t}$,
we have that $\alpha((-+)^{t})\beta$; since the longest substring of
$\mathbb{G}$ from $a$ to $b$ starts with a $+$, a similar length argument
shows that the image of $\alpha((-+)^{t})\beta$ under $f$ must use the arc
$(a,b)$; hence without loss of generality we have that $(\alpha,\beta)$ is an
arc in $\mathbb{G}^{p}$, in all cases. Let $\gamma=(u,u,\dots,u)$. By Claim 1e
$\alpha\mathbb{T}\gamma$ and $\beta\mathbb{T}\gamma$, and by Claim 3e the
paths $\alpha\mathbb{T}\gamma$ and $\beta\mathbb{T}\gamma$ must both be
isomorphic to $\mathbb{T}$ since their endpoints are mapped to $a$ and $u$,
and to $b$ and $u$ respectively, and so are mapped to the unique path of the
correct length between those. Hence we have found a copy of $\mathbb{G}$ in
$\mathbb{G}^{p}$ on which $f$ is onto, and we conclude using Theorem 5.1.

∎

## References

  * [1] Ferdinand Börner, Andrei A. Bulatov, Hubie Chen, Peter Jeavons, and Andrei A. Krokhin.  The complexity of constraint satisfaction games and QCSP.  Inf. Comput., 207(9):923–944, 2009.
  * [2] Catarina Carvalho, Víctor Dalmau, and Andrei Krokhin.  Two new homomorphism dualities and lattice operations.  J. Logic Comput., 21(6):1065–1092, 2011.
  * [3] János Demetrovics and Lajos Rónyai.  Algebraic properties of crowns and fences.  Order, 6(1):91–99, 1989.
  * [4] Anne Fearnley.  The clone of operations preserving a cycle with loops.  Algebra Universalis, 60(1):91–106, 2009.
  * [5] Tomás Feder and Moshe Y. Vardi.  The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory.  SIAM J. Comput., 28(1):57–104 (electronic), 1999.
  * [6] Benoit Larose.  Taylor operations on finite reflexive structures.  Int. J. Math. Comput. Sci., 1(1):1–21, 2006.
  * [7] Benoît Larose.  Algebra and the complexity of digraph CSPs: a survey.  In The constraint satisfaction problem: complexity and approximability, volume 7 of Dagstuhl Follow-Ups, pages 267–285. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017.
  * [8] Benoît Larose, Petar Markovic, Barnaby Martin, Daniël Paulusma, Siani Smith, and Stanislav Zivný.  QCSP on reflexive tournaments.  In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors, 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), volume 204 of LIPIcs, pages 58:1–58:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [9] Benoit Larose and David Emmanuel Pazmiño Pullas.  Słupecki reflexive digraphs.  In preparation.
  * [10] Benoit Larose and Claude Tardif.  A discrete homotopy theory for binary reflexive structures.  Adv. Math., 189(2):268–300, 2004.
  * [11] Dietlinde Lau.  Function algebras on finite sets.  Springer Monographs in Mathematics. Springer-Verlag, Berlin, 2006.
  * [12] Miklós Maróti and László Zádori.  Reflexive digraphs with near unanimity polymorphisms.  Discret. Math., 312(15):2316–2328, 2012.
  * [13] Barnaby Martin.  Quantified constraints in twenty seventeen.  In Andrei A. Krokhin and Stanislav Zivný, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 327–346. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.