# Loop conditions with strongly connected graphs

Miroslav Olšák

###### Abstract

We prove that the existence of a term $s$ satisfying $s(r,a,r,e)=s(a,r,e,a)$
in a general algebraic structure is equivalent to an existence of a term $t$
satisfying $t(x,x,y,y,z,z)=t(y,z,z,x,x,y)$. As a consequence of a general
version of this theorem and previous results we get that each strongly
connected digraph of algebraic length one, which is compatible with an
operation $t$ satisfying an identity of the from $t(\ldots)=t(\ldots)$, has a
loop.

Partially supported by the Czech Grant Agency (GAČR) under grant no.
18-20123S, by the National Science Centre Poland under grant no.
UMO-2014/13/B/ST6/01812 and by the PRIMUS/SCI/12 project of the Charles
University.

##  1 Introduction

Under which structural and algebraic conditions does a graph compatible with
an algebra necessarily have a loop? This question has originated from the
algebraic approach to the fixed–template constraint satisfaction problems and
answers have provided strong results and useful tools in this area as well as
in universal algebra, see [4, 2] for recent surveys.

A. Bulatov’s algebraic refinement of the well–known Hell and Nesetril
dichotomy for undirected graphs [9] can be stated as follows.

######  Theorem 1.1 (basic loop lemma).

[8] If a finite undirected graph $\mathbb{G}$

  * •

contains a triangle and

  * •

is compatible with a Taylor term (that is, an operation satisfying a non-
trivial set of identities of the form $t(\hbox{some vars})=t(\hbox{some
vars})$),

then $\mathbb{G}$ contains a loop (that is an edge joining a vertex with
itself).

In 2010, M. Siggers observed that this structural result has an algebraic
equivalent statement.

######  Theorem 1.2.

[13] If $\mathbf{A}$ is a finite algebra with a Taylor term, then $\mathbf{A}$
has a 6-ary Siggers term $s$ satisfying $s(x,x,y,y,z,z)=s(y,z,z,x,x,y)$.

###### Proof.

Let $\mathbf{F}$ be the $\mathbf{A}$-free algebra generated by the set
$\\{x,y,z\\}$. Since $\mathbf{A}$ is finite, $\mathbf{F}$ is finite as well.
We consider a symmetric binary relation (graph) on $\mathbf{F}$ generated by
the pairs

$\begin{pmatrix}x\cr y\end{pmatrix},\begin{pmatrix}x\cr
z\end{pmatrix},\begin{pmatrix}y\cr z\end{pmatrix},\begin{pmatrix}y\cr
x\end{pmatrix},\begin{pmatrix}z\cr x\end{pmatrix},\begin{pmatrix}z\cr
y\end{pmatrix}.$

This graph has a triangle on $x,y,z$, so it has a loop $(l,l)$ by the loop
lemma. Let $s$ be the six-ary term that generates the loop from the generators
above. Then the following identity holds for the generators $x,y,z$.

$s(x,x,y,y,z,z)=l=s(y,z,z,x,x,y)$

However, since $\mathbf{F}$ is a free algebra, the identity holds in general.
∎

Notice that obtaining the structural result from the algebraic one is even
easier – if we have a Siggers term $s$, and an undirected triangle in a
compatible graph, we find the loop directly by applying the Siggers term to
the six edges of the triangle (we use both directions of each of three
undirected edge).

The loop lemma was improved by L. Barto and M. Kozik.

######  Theorem 1.3 (loop lemma).

[3] If a finite digraph $\mathbb{G}$

  * •

is weakly connected,

  * •

is smooth (has no sources and no sinks),

  * •

has algebraic length 1 (cannot be mapped to a non-trivial directed cycle) and

  * •

is compatible with a Taylor term,

then $\mathbb{G}$ contains a loop.

Consequently, one can improve Theorem 1.3 as follows.

######  Theorem 1.4.

[11] If $\mathbf{A}$ is a finite algebra with a Taylor term, then $\mathbf{A}$
has a 4-ary Siggers term $s$ satisfying $s(r,a,r,e)=s(a,r,e,a)$.

Since both algebraic results give a Taylor term, the following properties are
equivalent for a finite algebra $\mathbf{A}$:

  1. (i)

$\mathbf{A}$ has a Taylor term.

  2. (ii)

$\mathbf{A}$ has a 6-ary Siggers term $s(x,x,y,y,z,z)=s(y,z,z,x,x,y)$.

  3. (iii)

$\mathbf{A}$ has a 4-ary Siggers term $s(r,a,r,e)=s(a,r,e,a)$.

A natural question is whether the equivalence can be generalized to general
(infinite) algebras. A. Kazda found an example [10] of an algebra that has an
idempotent Taylor term (that is, a Taylor term t which additionally satisfies
t(x,….x)=x), but no 6-ary or 4-ary Siggers term. Therefore the remaining
question is whether the properties (ii) and (iii) are equivalent.

Recently, the author studied such conditions in general [12]. A _loop
condition_ is a condition of the form: There is a term $t$ satisfying
$t(\text{some variables})=t(\text{some variables})$. A consequence of results
in [12] is that the following statements are equivalent for every algebra
$\mathbf{A}$.

  1. (i)

$\mathbf{A}$ satisfies a non-trivial loop condition,

  2. (ii)

$\mathbf{A}$ has a 6-ary Siggers term $s(x,x,y,y,z,z)=s(y,z,z,x,x,y)$.

  3. (iii)

Every non-bipartite undirected graph compatible with an algebra $\mathbf{B}$
in the variety generated by $\mathbf{A}$ has a loop.

In this paper, we give a positive answer to the raised question by finding a
broader class of loop conditions that are equivalent. This allows us to give
an even stronger structural characterization of algebras satisfying some loop
condition in the following form.

######  Theorem 1.5.

Let $\mathcal{V}$ be a variety. Then the following are equivalent.

  1. (i)

$\mathcal{V}$ satisfies a non-trivial loop condition,

  2. (ii)

Let $\mathbb{G}$ be a graph compatible with $\mathbf{A}\in\mathcal{V}$. If
$\mathbb{G}$ has a strongly connected component with algebraic length one,
then $\mathbb{G}$ has a loop.

###  1.1 Outline

We start by providing a proper definition of the key concepts in Section 2
including a digraph associated to a loop condition. We also summarize there
the results of the paper [12].

In Section 3 we prove our main result: that all loop conditions with a
strongly connected digraph with algebraic length one are equivalent.

Then we give two examples of classical classes that satisfy such a condition
in Section 4.

In Section 5, we classify the strength of loop comditions with strongly
connected digraphs (of arbitrary algebraic lengths)

Finally, in Section 6 we discuss the case whithout strong connectedness. This
case seems to be much colorful, so we provide at least some counterexamples
and some partial results.

##  2 Preliminaries

We refer to [6, 7] for undefined notions and more background.

###  2.1 Digraphs, algebraic length

A _digraph_ $\mathbb{G}=(A,G)$ is a relational structure, where $A$ is the set
of nodes (vertices) and $G\subset A\times A$ is a binary relation, in other
words, the set of edges. We sometimes denote an edge $(x,y)\in G$ of a digraph
by

$x\buildrel\mathbb{G}\over{\rightarrow}y,\text{ or
}y\buildrel\mathbb{G}\over{\leftarrow}x.$

If both $(x,y),(y,x)\in G$, we write $x\buildrel\mathbb{G}\over{-}y$. If the
digraph is clear from the context, we may write just
$x\mathrel{\rightarrow}y,y\mathrel{\leftarrow}x$, or $x\mathrel{-}y$. A loop
in $\mathbb{G}$ is an edge $a\mathrel{\rightarrow}a$.

If the relation $G$ is symmetric, we also call $\mathbb{G}$ as undirected
graph.

Consider two digraphs $\mathbb{G}=(A,G)$ and $\mathbb{H}=(B,H)$. A digraph
homomorphism $f\colon\mathbb{G}\to\mathbb{H}$ is a mapping $A\to B$ such that
$f(a_{1})\buildrel\mathbb{H}\over{\rightarrow}f(a_{2})$ whenever
$a_{1}\buildrel\mathbb{G}\over{\rightarrow}a_{2}$.

Thorough the paper, we use the following basic digraphs:

  1. 1.

A clique $\mathbb{K}_{n}=(\\{0,\ldots,n-1\\},\neq)$,

  2. 2.

a symmetric cycle $\mathbb{C}_{n}$ on $\\{0,\ldots,n-1\\}$, where
$x\mathrel{-}y$ if $y\equiv x\pm 1\pmod{n}$,

  3. 3.

a directed cycle $\mathbb{D}_{n}$ on $\\{0,\ldots,n-1\\}$, where
$x\mathrel{\rightarrow}y$ if $y\equiv x+1\pmod{n}$,

  4. 4.

a directed path $\mathbb{Z}$ on integers $\\{\ldots,-2,-1,0,1,2,\ldots\\}$,
where $k\mathrel{\rightarrow}k+1$ for all integers $k$.

An _oriented walk_ of length $n$ is a sequence of vertices $x_{0},x_{1},\ldots
x_{n}$ such that for each $i$ we have $x_{i}\mathrel{\rightarrow}x_{i+1}$ or
$x_{i}\mathrel{\leftarrow}x_{i+1}$. A walk is called _directed_ if for all $i$
we have the forward edge $x_{i}\mathrel{\rightarrow}x_{i+1}$. If
$x_{0}=x_{n}$, we also talk about directed or oriented cycle. Notice that a
directed cycle as a walk of length $n$ on a digraph $\mathbb{G}$ corresponds
to a digraph homomorphism $\mathbb{D}_{n}\to\mathbb{G}$.

If every pair of vertices is connected by an oriented walk, we call the
digraph _weakly connected_. If every pair of vertices is connected by a
directed walk (in both ways), we call the digraph _strongly connected_.

_Algebraic length_ of an oriented walk is defined as the number of forward
edges minus the number of backward edges in the walk. The _algebraic length of
a digraph_ $\mathbb{G}$, denoted $al(\mathbb{G})$, is the greatest common
divisor of the algebraic lengths of all oriented cycles, or $\infty$ if all
oriented cycles have algebraic length zero. Note that our definition slightly
differs from the one from [3] on digraphs that are not weakly connected. On
the other hand, neither of papers is interested in that case. If $\mathbb{G}$
is weakly connected, then there is an oriented $\mathbb{G}$-cycle of length
$al(\mathbb{G})$.

There are also nice characterizations of these properties using digraph
homomorphism. The algebraic length of a digraph $\mathbb{G}$ is the biggest
$n$ such that there is a digraph homomorphism $\mathbb{G}\to\mathbb{D}_{n}$,
or $\infty$ if there is a digraph homomorphism $\mathbb{G}\to\mathbb{Z}$.
Conversely, a finite digraph $\mathbb{G}$ is strongly connected if and only if
there is a digraph homomorphism $\mathbb{D}_{n}\to\mathbb{G}$ for some $n$
that is surjective on edges. We finish this subsection with an even stronger
property of finite strongly connected digraphs with a given algebraic length.

######  Proposition 2.1.

Let $\mathbb{G}$ be a finite strongly connected digraph and let $S$ be the set
of all numbers $n$ such that there is a digraph homomorphism
$\mathbb{D}_{n}\to\mathbb{G}$ that is surjective on edges. Then $S$ contains
only the multiples of $al(\mathbb{G})$ but it contains any such a multiple
that is large enough.

###### Proof.

Let $d$ denote the greatest common divisor of elements of $S$. The set $S$ is
closed under addition: Any two directed cycles that covers all edges can be
joined at any node. Therefore, by Schur’s theorem, the set $S$ contains all
the multiples of $d$ that are large enough. Every number of $S$ expresses an
algebraic length of a directed cycle, so $al(\mathbb{G})\mid d$. It remains to
prove that $d\mid al(\mathbb{G})$.

To see that, take $k\in S$, the corresponding directed cycle $c_{k}$ and an
oriented cycle $c_{al}$ on $\mathbb{G}$ of algebraic length $al(\mathbb{G})$.
In $c_{al}$, we append one copy of $c_{k}$ and replace every backward edge by
$(k-1)$ forward edges taken from $c_{k}$. The result is a directed cycle $c$
that is surjective on edges and its length is equal to $al(\mathbb{G})+nk$ for
some $n$. Hence

$al(\mathbb{G})+nk\in S.$

Since $d\mid k$ and $d\mid al(\mathbb{G})+nk$, also $d\mid al(\mathbb{G})$ and
we are done. ∎

###  2.2 Compatible digraphs, pp-constructions

An $n$-ary operation $f\colon A^{n}\to A$ is said to be _compatible_ with an
$m$-ary relation $R\subset A^{m}$ if
$f(\mathbf{r}_{1},\mathbf{r}_{2},\ldots,\mathbf{r}_{n})\in R$ for any
$\mathbf{r}_{1},\mathbf{r}_{2},\ldots,\mathbf{r}_{n}\in R$. Here (and later as
well) we abuse notation and use $f$ also for the $n$-ary operation on $A^{m}$
defined coordinate-wise.

An algebra $\mathbf{A}=(A,f_{1},f_{2},\ldots)$ is said to be compatible with a
relational structure $\mathbb{A}=(A,R_{1},R_{2},\ldots)$ if all the operations
$f_{1},f_{2},\ldots$ are compatible with all the relations
$R_{1},R_{2},\ldots$.

We will extensively use a standard method for building compatible relations
from existing ones – primitive positive (_pp_ , for short) definitions. A
relation $R$ is _pp-definable_ from relations $R_{1},\ldots,R_{n}$ if it can
be defined by a first order formula using variables, existential quantifiers,
conjunctions, the equality relations, and predicates $R_{1},\ldots,R_{n}$.
Clauses in pp-definitions are also referred to as _constraints_. Recall that
if $R_{1},\ldots,R_{n}$ are compatible with an algebra, then so is $R$.

A pp-definition of a $k$-ary relation $R$ from a digraph $\mathbb{G}$ can be
described by a finite digraph $\mathbb{H}$ with $k$ distinguished vertices
$v_{1},\ldots,v_{k}$. We define $R(x_{1},\ldots,x_{k})$ by the existence of a
digraph homomorphism $\mathbb{H}\to\mathbb{G}$ that maps $v_{i}$ to $x_{i}$.
The edges of $\mathbb{H}$ correspond to the constraints in the pp-definition,
and the images of remaining vertices of $\mathbb{H}$ (other that
$v_{1},\ldots,v_{k}$) are existentialy quantified.

Using a more general technique, we can also construct a relation that is
compatible with a subalgebra of a power $\mathbf{A}^{k}$. We pp-define two
relations from some relations compatible with $\mathbf{A}$: a $k$-ary relation
$B$, and a $nk$-ary relation $R$. Then $B$ is compatible with $\mathbf{A}$, so
it forms a subuniverse of $\mathbf{A}^{k}$. The $nk$-ary relation $R$ is
perceived as an $n$-ary relation on elements of $\mathbf{A}^{k}$, so $R$ acts
as a $n$-ary relation on $B$ as well. Even in this perception, the relation
$R$ is still compatible with the subalgebra $\mathbf{B}\leq\mathbf{A}^{k}$ on
subuniverse $B$. This construction is a special case of pp-construction.

In our proof, we will use this construction in the following form. Consider
two finite (template) digraphs $\mathbb{V}=(V_{v},V_{e})$,
$\mathbb{E}=(E_{v},E_{e})$, and two digraph homomorphisms
$\phi_{0},\phi_{1}\colon\mathbb{V}\to\mathbb{E}$. Then we take a digraph
$\mathbb{G}=(A,G)$ compatible with an algebra $\mathbf{A}$, and construct a
digraph $\mathbb{H}=(B,H)$ where $B$ is the set of all the mappings
$\mathbb{V}\to\mathbb{G}$ and edges defined as follows: The is an edge
$v_{0}\buildrel\mathbb{H}\over{\rightarrow}v_{1}$ if there is a homomorphism
$e\colon\mathbb{E}\to\mathbb{G}$ such that $v_{0}=e\circ\phi_{0}$ and
$v_{1}=e\circ\phi_{1}$. Then $B$ is a subuniverse of $\mathbf{A}^{|V_{v}|}$,
and $H$ a compatible digraph with the appropriate algebra $\mathbf{B}$.

###  2.3 Loop conditions

A _variety_ $\mathcal{V}$ is a class of algebras closed under powers,
subalgebras and homomorphic images. In every variety, for any set $S$, we can
find the _free algebra $\mathbf{F}$ freely generated by $S$_ with the
following property: Let $t_{1}.t_{2}$ be any $n$-ary term operations, and
$s_{1},\ldots,s_{n}$ be distinct elements of $S$. If
$t_{1}(s_{1}\ldots,s_{n})=t_{2}(s_{1},\ldots,s_{n})$ in $\mathbf{F}$, then
$t_{1}(x_{1}\ldots,x_{n})=t_{2}(x_{1},\ldots,x_{n})$ for any
$x_{1},\ldots,x_{n}$ in any algebra from $\mathcal{V}$.

A _loop condition_ is given by a set of variables $V$ and two $n$-tuples

$x_{1},x_{2},\ldots,x_{n},y_{1},y_{2},\ldots,y_{n}\in V.$

An algebra (or variety) is said to satisfy such a condition if there is a term
$t$ in the algebra (variety) satisfying the identity

$t(x_{1},x_{2},\ldots,x_{n})=t(y_{1},y_{2},\ldots,y_{n}).$

To such a loop condition $C$, we assign a digraph

$\mathbb{G}_{C}=(V,\\{(x_{1},y_{1}),(x_{2},y_{2}),\ldots,(x_{n},y_{n})\\}$

$x$$y$$z$

$\longleftrightarrow$

$\longleftrightarrow$

$\longleftrightarrow$ $e$$r$$a$

$\longrightarrow$

$\longrightarrow$

$\longleftrightarrow$ ${}s({}$ ${}x{}$ , ${}x{}$ , ${}y{}$ , ${}y{}$ , ${}z{}$
, ${}z{}$ ${}){}$ ${}{\downarrow}{}$ ${}{\downarrow}{}$ ${}{\downarrow}{}$
${}{\downarrow}{}$ ${}{\downarrow}{}$ ${}{\downarrow}{}$ $={}$ ${}s({}$
${}y{}$ , ${}z{}$ , ${}z{}$ , ${}x{}$ , ${}x{}$ , ${}y{}$ ${}){}$ ${}s({}$
${}r{}$ , ${}a{}$ , ${}r{}$ , ${}e{}$ ${}){}$ ${}{\downarrow}{}$
${}{\downarrow}{}$ ${}{\downarrow}{}$ ${}{\downarrow}{}$ $={}$ ${}s({}$
${}a{}$ , ${}r{}$ , ${}e{}$ , ${}a{}$ ${}){}$

Figure 1: Graphs corresponding to the 6-ary and 4-ary Siggers terms

Since $\mathbf{A}$ satisfies a certain loop condition if and only if the
variety generated by $\mathbf{A}$ satisfies it, it suffices to focus on
varieties.

######  Proposition 2.2.

The following are equivalent for a variety $\mathbb{V}$ and a loop condition
$C$.

  1. 1.

$\mathcal{V}$ satisfies $C$.

  2. 2.

Let $\mathbf{F}$ be the free algebra freely generated by the set of variables
in $C$, and let $\mathbb{G}$ be a digraph compatible with $\mathbf{F}$
containing all the edges of $\mathbb{G}_{c}$. Then $\mathbb{G}$ have a loop.

  3. 3.

For any algebra $\mathbf{A}\in\mathcal{V}$ and any digraph $\mathbb{G}$
compatible with $\mathbf{A}$, if there is a digraph homomorphism
$\mathbb{G}_{C}\to\mathbb{G}$, then $\mathbb{G}$ has a loop.

The proof of the proposition is just a direct generalization of the proof of
Theorem 1.2. For a general proof, we refer the reader to [12].

It is apparent from the proposition that a validity of a loop condition $C$ in
a variety (algebra) is determined by the digraph $\mathbb{G}_{C}$. Based on
that tight connection between a loop condition and its digraph, we sometimes
assign digraph attributes (strongly connected, algebraic length) to a loop
condition, meaning the attributes of the corresponding digraph. For a general
finite digraph $\mathbb{G}$ we also talk about the $\mathbb{G}$ loop condition
– that refers to any loop condition $C$ such that
$\mathbb{G}_{C}\simeq\mathbb{G}$.

A loop condition is called _trivial_ if it is satisfied in every algebra,
equivalently if its digraph contains a loop. Otherwise, the loop condition is
called _non-trivial_.

A simple reason for implication between loop conditions, directly obtained
from item (iii) of Proposition 2.2, is the following theorem.

######  Proposition 2.3.

If there is a digraph homomorphism $\mathbb{G}\to\mathbb{H}$, then every
variety (algebra) satisfying the $\mathbb{G}$ loop condition satisfies the
$\mathbb{H}$ loop condition as well.

Nevertheless, this is not by far the only way for obtaining an implication
between loop conditions. It is proved in [12] that all non-trivial undirected
non-bipartite loop conditions are equivalent. If a variety (or an algebra)
satisfies a non-trivial loop condition, we call it _loop-producing_. Since any
finite loopless digraph can be homomorphically mapped to a large enough
clique, we get the following corollary of that result.

######  Proposition 2.4.

Let $\mathcal{V}$ be a variety. The following are equivalent.

  1. 1.

$\mathbb{V}$ is a loop-producing variety,

  2. 2.

Let $\mathbb{K}_{\omega}$ denote the infinite countable clique, and let
$\mathbf{F}$ be a $\mathcal{V}$-free algebra freely generated by the nodes of
$\mathbb{K}_{\omega}$. Then the graph generated by edges of
$\mathbb{K}_{\omega}$ has a loop.

  3. 3.

$\mathbb{V}$ has a 6-ary Siggers term $s(x,x,y,y,z,z)=s(y,z,z,x,x,y)$,

  4. 4.

$\mathbb{V}$ satisfies all undirected non-bipartite loop conditions,

  5. 5.

Whenever $\mathbf{A}\in\mathcal{V}$ is compatible with a digraph $\mathbb{G}$
such that there is homomorphism $\mathbb{C}_{2n+1}\to\mathbb{G}$ for some $n$,
then $\mathbb{G}$ has a loop.

Less formally, it suffices to test the loop-producing property on large
cliques, but then it can be applied to any symmetric cycle of odd length.

##  3 The proof of the loop condition collapse

In this section, we prove the following.

######  Theorem 3.1.

Let $\mathbb{G}$ be a strongly connected digraph with algebraic length 1, and
$\mathcal{V}$ be a loop-producing variety. Then $\mathcal{V}$ satisfies the
$\mathbb{G}$ loop condition.

From basic properties of loop conditions we then obtain the following
corollaries.

######  Corollary 3.1.

Let $\mathbf{A}$ be a loop-producing algebra compatible with a digraph
$\mathbb{G}$. If $\mathbb{G}$ has a strongly connected component with
algebraic length one, then $\mathbb{G}$ has a loop.

###### Proof.

It follows from Theorem 3.1 and Proposition 2.2, implication
$(1)\Rightarrow(3)$. ∎

######  Corollary 3.2.

All the non-trivial loop conditions that have a strongly connected component
of algebraic length one are equivalent.

###### Proof.

Any variety satisfying such a loop conditions is loop-producing by non-
triviality. Conversely, any loop-producing variety satisfy all the loop
conditions with algebraic length one by Theorem 3.1. Finally, all the non-
trivial loop conditions that have a strongly connected component of algebraic
length one are satisfied by Proposition 2.3. ∎

######  Corollary 3.3.

Any loop-producing variety has a 4-ary Siggers term $s(r,a,r,e)=s(a,r,e,a)$.

###### Proof.

This follows directly from Theorem 3.1 since the rare-area loop condition is
an example of a strongly connected loop condition with algebraic length one. ∎

###  3.1 Digraph definitions

We provide three concrete types of digraphs that will serve as intermediate
steps in the proof of Theorem 3.1.

######  Definition 3.2.

Given cycle lengths $a,b\geq 1$, we define the digraph
$\operatorname{DCP}(a,b)$ (directed cycle pair) as follows. The nodes are
$A_{0},\ldots,A_{a-1}$ and $B_{0},\ldots,B_{b-1}$ such that $A_{0}=B_{0}$
while all the other are different. Edges goes from $A_{i}$ to $A_{i+1}$ modulo
$a$ and from $B_{i}$ to $B_{i+1}$ modulo $b$.

$A_{1}$$A_{0}=B_{0}$$B_{1}$$B_{2}$$B_{3}$$B_{4}$ Figure 2: The digraph
$\operatorname{DCP}(2,5)$.

######  Definition 3.3.

For a given path length $k\geq 1$, number $l\geq 0$ of loop symbols, and cycle
size $c\geq 1$, the digraph $\operatorname{CCLW}(k,l,s)$ (cycle walks) is
defined as follows. Let $\mathcal{A}=\\{0,1,\ldots,c-1\\}$ and $\mathcal{L}$
be an alphabet of size $l$ not containing $\emptyset$. The nodes of
$\operatorname{CCLW}(k,l,c)$ are the sequences
$(a_{1},l_{1},a_{2},l_{2},\ldots.l_{k-1},a_{k})$ such that:

  * •

every $a_{i}\in\mathcal{A}$ and every
$l_{i}\in\mathcal{L}\cup\\{\emptyset\\}$,

  * •

loop symbols do not repeat, that is, if $l_{i}=l_{j}$, then $i=j$ or
$l_{i}=l_{j}=\emptyset$,

  * •

If $l_{i}\in\mathcal{L}$, then $a_{i}=a_{i+1}$. Otherwise $a_{i}\equiv
a_{i+1}\pm 1\pmod{c}$.

There is an edge $(n_{1},n_{2})\in\operatorname{CCLW}(k,l,s)$ if there is a
node $n$ in $\operatorname{CCLW}(k+1,l,s)$ such that $n_{1}$ is a prefix of
$n$ and $n_{2}$ is a suffix of $n$.

$\scriptstyle(4,3)$$\scriptstyle(0,1)$$\scriptstyle(1,0)$$\scriptstyle(1,2)$$\scriptstyle(2,3)$$\scriptstyle(3,4)$$\scriptstyle(4,0)$$\scriptstyle(0,4)$$\scriptstyle(4,3)$$\scriptstyle(3,2)$$\scriptstyle(2,1)$$\scriptstyle\operatorname{CCLW}(2,0,5)$$\scriptstyle(0,1)$$\scriptstyle(1,0)$$\scriptstyle(1,2)$$\scriptstyle(2,3)$$\scriptstyle(3,4)$$\scriptstyle(4,0)$$\scriptstyle(0,4)$$\scriptstyle(3,2)$$\scriptstyle(2,1)$$\scriptstyle(4,4)$$\scriptstyle(0,0)$$\scriptstyle(3,3)$$\scriptstyle(2,2)$$\scriptstyle(1,1)$$\scriptstyle\operatorname{CCLW}(2,1,5)$
Figure 3: Examples of digraphs of cycle walks. The loop symbol is ommited
since it is uniquely determined by adjacent items.

######  Definition 3.4.

For a given path length $k\geq 1$, number $l\geq 0$ of loop symbols, and
alphabet size $s\geq 1$, the digraph $\operatorname{CLQP}(k,l,s)$ (clique
paths) is defined as follows. Let $\mathcal{A}$ be an alphabet of size $s$ and
$\mathcal{L}$ be an alphabet of size $l$ not containing $\emptyset$. The nodes
of $\operatorname{CLQP}(k,l,s)$ are the sequences
$(a_{1},l_{1},a_{2},l_{2},\ldots.l_{k-1},a_{k})$ such that:

  * •

every $a_{i}\in\mathcal{A}$ and every
$l_{i}\in\mathcal{L}\cup\\{\emptyset\\}$,

  * •

loop symbols do not repeat, that is, if $l_{i}=l_{j}$, then $i=j$ or
$l_{i}=l_{j}=\emptyset$,

  * •

letters repeat if and only if they are connected by loop symbols, that is, for
any $i<j$: $a_{i}=a_{j}$ if and only if all
$l_{i},\ldots,l_{j-1}\in\mathcal{L}$.

There is an edge $(n_{1},n_{2})\in\operatorname{CLQP}(k,l,s)$ if there is a
node $n$ in $\operatorname{CLQP}(k+1,l,s)$ such that $n_{1}$ is a prefix of
$n$ and $n_{2}$ is a suffix of $n$.

Note that cycle walks and clique paths differ just in the third point where
cycle walks allows repetition of letters but are more restrictive on the local
behavior.

###  3.2 Proof outline

Let $\mathcal{V}$ be a fixed loop-producing variety. We begin by stating seven
lemmas.

######  Lemma 1.

The $\operatorname{CLQP}(1,0,3)$ loop condition is satisfied in $\mathcal{V}$.

######  Lemma 2.

For any $k\geq 1,s\geq 1$, the following implication between loop conditions
holds for $\mathcal{V}$:

$\operatorname{CLQP}(k,0,s)\Rightarrow\operatorname{CLQP}(k+1,s,1).$

######  Lemma 3.

For any $k\geq 2,l\geq 1,s\geq 1$, the following implication between loop
conditions holds for $\mathcal{V}$:

$\operatorname{CLQP}(k,l,s)\Rightarrow\operatorname{CLQP}(k,l-1,3s).$

######  Lemma 4.

For any $k\geq 1,l\geq 0,c\geq 1$, the following implication between loop
conditions holds for $\mathcal{V}$:

$\operatorname{CLQP}(k,l,1)\Rightarrow\operatorname{CCLW}(k,l,c).$

######  Lemma 5.

For any $k\geq 2,l\geq 1,c\geq 3$, $c$ odd, the following implication between
loop conditions holds for $\mathcal{V}$:

$\operatorname{CCLW}(k,l,c)\Rightarrow\operatorname{CCLW}(k,l-1,c).$

######  Lemma 6.

For any odd $c\geq 3$ there is some $k\geq 2$ such that the following
implication between loop conditions holds for $\mathcal{V}$:

$\operatorname{CCLW}(k,0,c)\Rightarrow\operatorname{DCP}(2,c).$

######  Lemma 7.

For any $p,b\geq 1$, $b$ odd, the following implication between loop
conditions holds for $\mathcal{V}$:

$\operatorname{DCP}(2^{p},2^{p+1}+b)\Rightarrow\operatorname{DCP}(2^{p+1},b).$

First, let us see how Theorem 3.1 follows from these lemmas. Using Lemma 2
once and Lemma 3 repeatedly yields the implication
$\operatorname{CLQP}(k,0,s)\Rightarrow\operatorname{CLQP}(k+1,0,3^{s})$ for
any $k,s\geq 1$. Since the $\operatorname{CLQP}(1,0,3)$ loop condition holds
in $\mathcal{V}$ by Lemma 1, for any $k\geq 1$ there is $s\geq 3$ such that
the $\operatorname{CLQP}(k,0,s)$ loop condition also holds in $\mathcal{V}$.

Therefore by Lemmas 2, 4, also the $\operatorname{CCLW}(k,l,c)$ loop condition
holds in $\mathcal{V}$ for any $k\geq 2,c\geq 1$ and some $l$ depending on
$k$. If $c$ is odd and at least 3, we can reduce the number of loop symbols
$s$ to zero by repeated application of Lemma 5. So the
$\operatorname{CLQP}(k,0,c)$ loop condition holds in $\mathcal{V}$ for any
$k\geq 2,c\geq 3$, $c$ odd. Thus by Lemma 6 also the $DCP(2,c)$ loop condition
holds for any odd $c\geq 3$.

Now, the $\operatorname{DCP}(2^{p},c)$ loop condition holds for any odd $c\geq
3$ and for any $p\geq 1$. This is done by induction on $p$ where the induction
step is given by Lemma 7. Finally, consider any strongly connected loopless
digraph $\mathbb{G}$ with algebraic length 1. Digraph $\mathbb{G}$ is a
homomorphic image of a directed $2^{p}$-cycle for large enough $p$. Also
$\mathbb{G}$ is a homomorphic image of a directed $c$-cycle where $c$ is odd
and large enough. Therefore $\mathbb{G}$ is a homomorphic image of
$\operatorname{DCP}(2^{p},c)$ for large enough $p,c$, so the $\mathbb{G}$ loop
condition is satisfied in $\mathcal{V}$.

It remains to check the validity of our 7 lemmas.

Lemma 1 is satisfied by Proposition 2.4 since $\operatorname{CLQP}(1,0,3)$ is
isomorphic to the undirected triangle. Lemma 2 also follows from an
isomorphism of the appropriate digraphs. Sequence
$(a_{1},\emptyset,a_{2},\emptyset,\ldots,a_{k})$ in
$\operatorname{CLQP}(k,0,s)$ can be identified with the sequence
$(x,a_{1},x,a_{2},\ldots,a_{k},x)$ in $\operatorname{CLQP}(k+1,s,1)$ where $x$
is the only letter in the apropriate alphabet.

Lemma 4 is simple as well. the $\operatorname{CCLW}(k,l,c)$ loop condition is
implied by $\operatorname{CLQP}(k,l,1)$ just because
$\operatorname{CLQP}(k,l,1)$ is a subdigraph of $\operatorname{CCLW}(k,l,c)$.

Lemmas 3, 5, 6, 7 deserve bigger attention.

###  3.3 Proof of Lemma 3

######  Lemma 3.

For any $k\geq 2,l\geq 1,s\geq 1$, the following implication between loop
conditions holds for $\mathcal{V}$:

$\operatorname{CLQP}(k,l,s)\Rightarrow\operatorname{CLQP}(k,l-1,3s).$

Assume that the $\operatorname{CLQP}(k,l,s)$ loop condition is satisfied in
$\mathcal{V}$. To show that the $\operatorname{CLQP}(k,l-1,3s)$ loop condition
is satisfied in $\mathcal{V}$, consider a digraph $\mathbb{G}$ compatible with
an algebra in $\mathcal{V}$ such that $\operatorname{CLQP}(k,l-1,3s)$ is a
subdigraph of $\mathbb{G}$. It suffices to show that $\mathbb{G}$ has to
contain a loop.

Let us construct another digraph $\mathbb{H}$, pp-constructed from
$\mathbb{G}$. Nodes of $\mathbb{H}$ are defined as the homomorphisms
$\operatorname{CLQP}(k,l-1,s)\to\mathbb{G}$.

To define the edges of $\mathbb{H}$, we investigate the digraph
$\operatorname{CLQP}(k,l,s)$ in more detail. Let $L_{1},\ldots,L_{l}$ be the
loop symbols of $\operatorname{CLQP}(k,l,s)$ and $\\{L_{1},\ldots,L_{l-1}\\}$
be the loop symbols of $\operatorname{CLQP}(k,l-1,s)$. Then we can view
$\operatorname{CLQP}(k,l-1,s)$ as an induced subgraph of
$\operatorname{CLQP}(k,l,s)$. There are no extra edges since $k\geq 2$. Let
$\mathbb{V}$ denote the digraph induced on all nodes of
$\operatorname{CLQP}(k,l,s)$ containing the symbol $L_{l}$. So the set of all
vertices is decomposed into $\operatorname{CLQP}(k,l-1,s)$ and $\mathbb{V}$.

Consider $v_{0},v_{1}\colon\operatorname{CLQP}(k,l-1,s)\to\mathbb{G}$, two
vertices of $\mathbb{H}$. By definition, there is an edge
$v_{0}\buildrel\mathbb{H}\over{\rightarrow}v_{1}$ if and only if there is a
digraph homomorphism $f\colon\mathbb{V}\to\mathbb{G}$ such that for any edge
$(x,y)$ in $\operatorname{CLQP}(k,l,s)$:

  * •

If $x\in\operatorname{CLQP}(k,l-1,s)$ and $y\in\mathbb{V}$, then
$v_{0}(x)\buildrel\mathbb{G}\over{\rightarrow}f(y)$.

  * •

If $y\in\operatorname{CLQP}(k,l-1,s)$ and $x\in\mathbb{V}$, then
$v_{1}(y)\buildrel\mathbb{G}\over{\leftarrow}f(x)$.

######  Claim 3.5.

There is an undirected triangle in $\mathbb{H}$.

To show the claim, let $\mathcal{A}_{s}$, $\mathcal{A}_{3s}$ be alphabets of
$\operatorname{CLQP}(k,l-1,s)$, $\operatorname{CLQP}(k,l-1,3s)$ respectively.
Fix three injective mappings
$u_{1},u_{2},u_{3}\colon\mathcal{A}_{s}\to\mathcal{A}_{3s}$ with pairwise
disjoint images. These mappings extend naturally to three homomorphisms
$\operatorname{CLQP}(k,l-1,s)\to\operatorname{CLQP}(k,l-1,3s)$, which are
vertices of $\mathbb{H}$ since $\operatorname{CLQP}(k,l-1,3s)$ is a subdigraph
of $\mathbb{G}$. We claim that these three nodes are pairwise adjacent. By
symmetry, it suffices to show that there is an edge $(u_{1},u_{2})$ in
$\mathbb{H}$. We define a homomorphism
$f\colon\mathbb{V}\to\operatorname{CLQP}(k,l-1,3s)$ as follows. A general node
of $\mathbb{V}$ of the form

$(a_{1},l_{1},\ldots,a_{i},l_{i}=L_{l},a_{i+1},l_{i+1},\ldots,a_{n})$

is mapped to the node

$(u_{1}(a_{1}),l_{1},\ldots,u_{1}(a_{i}),\emptyset,u_{2}(a_{i+1}),l_{i+1},\ldots,u_{2}(a_{n}))$

Such $f$ is a digraph homomorphism $\mathbb{V}\to\mathbb{G}$ satisfying the
required properties, so there is an edge
$u_{1}\buildrel\mathbb{H}\over{\rightarrow}u_{2}$.

Since the variety $\mathcal{V}$ is a loop-producing variety and digraph
$\mathbb{H}$ contains an undirected triangle, $\mathbb{H}$ contains a loop by
Proposition 2.4. By definition of $\mathbb{H}$, such a loop witnesses the
existence of a homomorphism $\operatorname{CLQP}(k,l,s)\to G$. So by the
$\operatorname{CLQP}(k,l,s)$ loop condition, there is a loop in $\mathbb{G}$.

###  3.4 Proof of Lemma 5

######  Lemma 5.

For any $k\geq 2,l\geq 1,c\geq 3$, $c$ odd, the following implication between
loop conditions holds for $\mathcal{V}$:

$\operatorname{CCLW}(k,l,c)\Rightarrow\operatorname{CCLW}(k,l-1,c).$

The approach is very similar to the proof of Lemma 3. However, we will repeat
the reasoning because of the slight differences.

Assume that the $\operatorname{CCLW}(k,l,c)$ loop condition is satisfied in
$\mathcal{V}$ and $\operatorname{CCLW}(k,l-1,c)$ is a subdigraph of a digraph
$\mathbb{G}$ compatible with an algebra in $\mathcal{V}$. We want to find a
loop in $\mathbb{G}$. We pp-construct a digraph $\mathbb{H}$. Its nodes are
all the digraph homomorphisms $\operatorname{CCLW}(k,l-1,c)\to\mathbb{G}$.

The edges of $\mathbb{H}$ are defined analogously to the previous case. We
decompose the nodes of $\operatorname{CCLW}(k,l,c)$ into two induced subraphs:
$\operatorname{CCLW}(k,l-1,c)$ and $\mathbb{V}$. There is an edge
$A\buildrel\mathbb{H}\over{\rightarrow}B$ if there is a digraph homomorphism
$f\colon\mathbb{V}\to\mathbb{G}$ such that the pair of homomorphisms $(A,f)$
preserves the edges from $\operatorname{CCLW}(k,l-1,c)$ to $\mathbb{V}$ and
the pair of homomorphisms $(B,f)$ preserves the edges in the other direction.

######  Claim 3.6.

Digraph $\mathbb{H}$ contains an undirected cycle of length $c$.

Indeed, let $\mathcal{A}$ denote the set $\\{0,1,\ldots,c-1\\}$. Let
$u_{i}\colon\mathcal{A}\to\mathcal{A}$ denote the mapping

$u_{i}(x)\equiv i+x\pmod{c}.$

Since these mappings are also endomorphisms of $\mathbb{C}_{n}$, these
mappings can be extended to homomorphisms
$\operatorname{CCLW}(k,l-1,c)\to\operatorname{CCLW}(k,l-1,c)$. So we can view
them as nodes of $\mathbb{H}$.

There are edges $u_{x}\buildrel\mathbb{H}\over{\rightarrow}u_{y}$ for $y=x\pm
1\pmod{c}$. To verify it, we construct a homomorphism
$\mathbb{V}\to\operatorname{CCLW}(k,l-1,c)$ testifying that. An element of
$\mathbb{V}$

$(a_{1},l_{1},\ldots,a_{i},l_{i}=L_{l},a_{i+1},l_{i+1},\ldots,a_{n}),$

where $L_{l}$ denotes the one extra loop symbol, is mapped to

$(u_{x}(a_{1}),l_{1},\ldots,u_{x}(a_{i}),l_{i}=\emptyset,u_{y}(a_{i+1}),l_{i+1},\ldots,u_{y}(a_{n}))$

in $\operatorname{CCLW}(k,l-1,c)$. Note that the $a_{i}=a_{i+1}$ because of
the loop symbol $L_{i}$, so $u_{y}(a_{i+1})\equiv u_{x}(a_{i})\pm 1$.
Therefore the position $i$ meets the requirement for
$\operatorname{CCLW}(k,l-1,c)$.

Since there is a symmetric cycle $\mathbb{C}_{c}$ in $\mathbb{H}$ and
$\mathcal{V}$ is a loop-producing variety, there is a loop in $\mathbb{H}$ by
Proposition 2.4 (5). A loop in $\mathbb{H}$ corresponds to a digraph
homomorphism $\operatorname{CCLW}(k,l,c)\to\mathbb{G}$. Finally, the
$\operatorname{CCLW}(k,l,c)$ loop condition gives a loop in $\mathbb{G}$.

###  3.5 Proof of Lemma 6

######  Lemma 6.

For any odd $c\geq 3$ there is some $k\geq 2$ such that the following
implication between loop conditions holds for $\mathcal{V}$:

$\operatorname{CCLW}(k,0,c)\Rightarrow\operatorname{DCP}(2,c).$

Actually, this is true because there is a digraph homomorphism
$\operatorname{CCLW}(k,0,c)\to\operatorname{DCP}(2,c)$. To show it, let us
reformulate the existence of a homomorphism a bit.

Consider a digraph homomorphism $a\colon\mathbb{Z}\to\mathbb{C}_{c}$ which
contains all the finite walks on $\mathbb{C}_{c}$. This is possible since
there are just countable number of the finite walks and $\mathbb{C}_{c}$ is
connected. Let us view the mapping $a\colon\mathbb{Z}\to\mathbb{C}_{c}$ (and
later defined $x\colon\mathbb{Z}\to\operatorname{DCP}_{c}$ as well) as a
sequence instead of a function and write $a_{i}$ instead of $a(i)$.

######  Claim 3.7.

There is a digraph homomorphism $x\colon\mathbb{Z}\to\operatorname{DCP}(2,c)$
and a number $k\geq 1$ such that whenever

$(a_{i-k},a_{i-k+1},\ldots,a_{i+k})=(a_{j-k}),a_{j-k+1},\ldots,a_{j+k})$

for some integers $i,j$, then also $x_{i}=x_{j}$.

First, let us see how the claim proves Lemma 6. The value $x_{i}$ is
determined only by the $(2k+1)$-tuple $(a_{i-k},\ldots,a_{i+k})$. By
construction of $a$, any such walk on $\mathbb{C}_{c}$ of length $(2k+1)$
occurs among such tuples. So there is a well defined mapping
$\operatorname{CCLW}(2k+1,0,c)\to\operatorname{DCP}(2,c)$ given by

$(a_{i-k},\emptyset,a_{i-k+1},\emptyset,\ldots,a_{i+k})\mapsto x_{i}.$

Finally, this mapping is a homomorphism since the sequence $a$ covers all the
walks of length $(2k+2)$ corresponding to the edges of
$\operatorname{CCLW}(2k+1,0,c)$.

Now, we prove the claim. Let $S$ be the set of all the integers $i$ satisfying

  1. 1.

$a_{i}=0$ or

  2. 2.

$a_{i}\equiv 0\pmod{2}$ and all the values $a_{i-c+1},\ldots,a_{i+c-1}$ are
nonzero.

Observe that the difference between consecutive elements of $S$ can not exceed
$2c$. Indeed, whenever there are two zeros $a_{i}$, $a_{j}$ in the sequence
$a$, $i+2c<j$, and there are no zeros between them, there is at least one
integer in the middle assigned to $S$ by the rule 2.

On the other hand, whenever there are two integers in $S$ such that their
difference is less than $c$, then the difference is even.

Given these facts, we can define the sequence $x$. For every $i\in S$ we set
$x_{i}=A_{0}=B_{0}$, then we fill the even spaces by alternation

$A_{0},A_{1},A_{0},A_{1},\ldots,A_{0}$

and the odd spaces greater than $c$ by

$B_{0},B_{1},\ldots B_{c-1},A_{0},A_{1},A_{0},A_{1},\ldots,A_{0}.$

Such a definition of $x_{i}$ depends only on $S\cap\\{i-2c+1,\ldots,i+2c-1\\}$
and the definition of $S$ depends just on neighborhoods with radius $c$. So
$k=3c$ completes the claim.

###  3.6 Proof of Lemma 7

######  Lemma 7.

For any $p,b\geq 1$, $b$ odd, the following implication between loop
conditions holds for $\mathcal{V}$:

$\operatorname{DCP}(2^{p},2^{p+1}+b)\Rightarrow\operatorname{DCP}(2^{p+1},b).$

Let the $\operatorname{DCP}(2^{p},2^{p+1}+b)$ loop condition be satisfied in
$\mathcal{V}$ and let $\mathbb{G}$ be a digraph compatible with an algebra
$\mathbf{A}\in\mathcal{V}$ having $\operatorname{DCP}(2^{p+1},b)$ as its
subdigraph. We need to show that $\mathbb{G}$ contains a loop.

Every node in $\operatorname{DCP}(2^{p+1},b)$ is contained in a directed cycle
of length $2^{p+1}+b$. Since this property is pp-definable, we can assume
without lost of generality that all nodes of $\mathbb{G}$ are contained in
such a cycle.

On the same set of vertices, we define another digraph $\mathbb{H}$ using
second relational power of the edges of $\mathbb{G}$, that is $(x,y)$ is an
$\mathbb{H}$-edge if and only if there is a directed $\mathbb{G}$-walk of
length 2 from $x$ to $y$. Since $\mathbb{H}$ is pp-defined from $\mathbb{G}$,
it is compatible with $\mathbf{A}$.

It is still true that every node of $\mathbb{H}$ is contained in a directed
$\mathbb{H}$-cycle of length $2^{p+1}+b$. Moreover, the nodes
$A_{0},A_{2},A_{4},\ldots,A_{2^{p+1}-2}$ form a cycle of length $2^{p}$.
Therefore, there is a homomorphism
$\operatorname{DCP}(2^{p},2^{p+1}+b)\to\mathbb{H}$. Using the assumption on
$\mathcal{V}$, we get a loop in $\mathbb{H}$.

Such a loop corresponds to an undirected edge in $\mathbb{G}$. Any directed
cycle of an even length can be homomorphically mapped to such an edge, in
particular the cycle of length $2^{p}$. Since every node of $\mathbb{G}$
belongs to a cycle of length $2^{p+1}+b$, there is a digraph homomorphism
$\operatorname{DCP}(2^{p},2^{p+1}+b)\to\mathbb{G}$. Second application of the
loop condition finished the proof.

##  4 Example loop-producing classes

In this section, we compare our result with standard classes in universal
algebra, and show which of them are loop-producing.

We start by providing an alternative proof of Theorem 1.2 that finite Taylor
algebras have a Siggers term. Our approach has a slightly weaker outcome than
Theorem 1.3 (finite directed loop lemma) since we require strong conectedness.
On the other hand, we managed to reduce the necessity of finiteness to a
single step in the proof. That gives a hope for generalizations under weaker
assumptions than local finiteness. One such generalization could be into the
class of so called oligomorphic structures, which are already known to satisfy
their own version of loop lemma, so called pseudoloop lemma. Details can be
found in [5].

A variety $\mathcal{V}$ is said to be _locally finite_ , if any finitely
generated $\mathbf{A}\in\mathcal{V}$ is finite. Conversely, any variety
generated by a single finite algebra is locally finite, which explains the
equivalence between Theorem 1.2 and the following formulation.

######  Theorem 4.1.

Let $\mathcal{V}$ be a locally finite variety having a (not necessarilly
idempotent) Taylor term, that is, a $k$-ary term $t$ satisfying some $k$
identities of the form

$\displaystyle t(x,?,?,...,?,?)$ $\displaystyle=t(y,?,?,...,?,?)=s_{1}(x,y),$
$\displaystyle t(?,x,?,...,?,?)$ $\displaystyle=t(?,y,?,...,?,?)=s_{2}(x,y),$
$\displaystyle\kern 4.83694pt\vdots$ $\displaystyle t(?,?,?,...,?,x)$
$\displaystyle=t(?,?,?,...,?,y)=s_{k}(x,y).$

where every question mark stands for either $x$ or $y$. Then $\mathcal{V}$ is
loop-producing.

###### Proof.

We check that by verifying that $\mathcal{V}$ satisfies the $\mathbb{K}_{3k}$
loop condition. Let $\mathbf{F}$ be the free algebra generated by $3k$
elements, and $\mathbb{G}$ be a graph compatible with it containing
$3k$-clique as a homomorphic image. We are supposed to prove that $\mathbb{G}$
contains a loop.

To do that, it is sufficient to prove that whenever $\mathbb{G}$ contains a
clique of size $c\geq 3k$ as a homomorphic image, it also contains a clique of
size $c+1$. Therefore we will be able to gradually increase the size of the
clique, and eventually exceed the size of algebra $\mathbf{F}$ which is finite
since $\mathcal{V}$ is a locally finite variety. The existence of a loop is
then a direct consequence of the pigeonhole principle.

So let us suppose that there is a clique with elements
$A_{i},B_{i},C_{i},D_{j}$ for $1\leq i\leq k$ and $1\leq j\leq c-3k$. We are
going to fill a matrix $a_{i,j}$ of size $c+1\times k$ in such a way that the
Taylor term $t$ applied row-wise outputs the desired clique of size $c+1$. We
write $a_{ii}=A_{i},a_{ij}=B_{i}$ for $i\neq j$, $1\leq i,j\leq k$. So the
values $t(a_{i,1},\ldots,a_{i,k})$ form a clique for $i\leq k$ since we used
disjoint parts of the original clique in separate rows. Now, we fill in the
next $k$ rows of the matrix. For a row $k+i$, where $1\leq i\leq k$, we use
the elements $A_{i},C_{i}$ in such a way that

$t(a_{k+i,1},a_{k+i,2},\ldots,a_{k+i,k})=s_{i}(A_{i},C_{i})$

and moreover $a_{k+i,i}=A_{i}$. This is possible by the $i$-th Taylor
identity. If we apply the Taylor term to the first $2k$ rows now, we still get
a clique. In particular, there is an edge between

$t(a_{i,1},a_{i,2},\ldots,a_{i,k})=t(B_{i},\ldots,B_{i},A_{i}=a_{i,i},B_{i},\ldots,B_{i})$

and

$t(a_{k+i,1},a_{k+i,2},\ldots,a_{k+i,k})=s_{i}(A_{i},C_{i})$

since there is a representation of

$s_{i}(A_{i},C_{i})=t(b_{i,1},b_{i,2},\ldots,b_{i,k})$

such that all $b_{i,j}$ are equal to $A_{i}$ or $C_{i}$ and moreover
$b_{i,i}=C_{i}$.

Since $a_{i,i}=a_{k+i,i}=A_{i}$, every column contains at most $2n-1$ distinct
vertices. Hence, we just complete the $c+1-2n$ remaining positions by the
remaining $c-(2n-1)$ distinct vertices, and the Taylor term applied to rows
gives a clique of size $c+1$. By this process, we gradually raise the size of
the clique until we exceed the size of the algebra $\mathbf{F}$. Thus, we get
a loop, and the variety is loop-producing. ∎

If we omit the assumption of local finiteness, we cannot hope for the Siggers
term even under the assumption of idempotency, as shown in [10]. This
counterexample can be even extended to a congruence meet-semidistributive
variety that does not have a Siggers term. That directs us to the varieties
satisfying a non-trivial congruence identity, equivalently; having a Hobby-
McKenzie term. The corresponding finite property is “ommiting types (1), (5)”.

######  Theorem 4.2.

Let $\mathcal{V}$ be a variety satisfying a non-trivial congruence identity
(see [1]). Then $\mathcal{V}$ has a Siggers term.

###### Proof.

Among many characterization (see [1], Theorem A.2), we use the following one
(number (9) in the reffered theorem). A variety $\mathcal{V}$ has a Hobby-
KcKenzie term if and only if it has a sequence of terms
$f_{0},\ldots,f_{2m+1}$ such that

  1. (i)

$\mathcal{V}\models f_{0}(x,y,u,v)\approx x$,

  2. (ii)

$\mathcal{V}\models f_{i}(x,y,y,y)\approx f_{i+1}(x,y,y,y)$ for even $i$,

  3. (iii)

$\mathcal{V}\models f_{i}(x,x,y,y)\approx f_{i+1}(x,x,y,y)$ and
$\mathcal{V}\models f_{i}(x,y,x,y)\approx f_{i+1}(x,y,x,y)$ for odd $i$,

  4. (iv)

$\mathcal{V}\models f_{2m+1}(x,y,u,v)\approx v$.

We can easily check that all the terms $f_{i}$ have to be idempotent, that is
$f_{i}(x,x,x,x)=x$ for any $i$ and $x$. We can assume that all terms of
$\mathcal{V}$ are idempotent, otherwise we consider the idempotent reduct.

Let $\mathbf{F}$ be a $\mathcal{V}$-free algebra generated by an infinite
countable set $X$. By Proposition 2.4 (ii), it suffices to prove the
following. If $\mathbb{G}=(A,G)$ is a graph, where the binary relation $G$ is
generated by distinct pairs of $X$, then $R$ contains a loop. Since our clique
is infinite, and every element $x\in\mathbf{F}$ is generated by finitely many
elements of $X$, any such element is $\mathbb{G}$-adjacent to all but finitely
many elements of $X$. Therefore, for any finite set
$x_{1},x_{2},\ldots,x_{n}\in\mathbf{F}$, we can find an element $y\in X$ such
that $y\mathrel{-}x_{i}$ for all $i=1,\ldots,n$.

Let $\hat{\phi}_{1},\hat{\phi}_{2}\colon X\to X$ be two injective mappings
with disjoint images $X_{1},X_{2}$, and let
$\phi_{1},\phi_{2}\colon\mathbf{F}\to\mathbf{F}$ be their unique extensions to
endomorphisms of $\mathbf{F}$.

Since $\mathbf{F}$ is idempotent and the relation $G$ is full on $X_{1}\times
X_{2}$, we have an edge $\phi_{1}(x)\mathrel{-}\phi_{2}(y)$ for every pair
$x,y\in\mathbf{F}$. Since $\hat{\phi}_{1},\hat{\phi}_{2}$ are injective, the
mappings $\hat{\phi}_{1},\hat{\phi}_{2}$ are endomorphisms of the relational
structure $\mathbb{G}|_{X}$. Therefore, even the induced mappings
$\phi_{1},\phi_{2}$ are homomorphisms of the relational structure
$\mathbb{G}$.

For $i=0,1,\ldots,m$, we gradually construct sequences
$\hat{a}_{i},a_{i},\hat{b}_{i},b_{i},\hat{c}_{i},c_{i},d_{i}$ such that

$a_{i}\mathrel{-}f_{2i}(x,a_{i},a_{i},a_{i})$

for all $x\mathrel{-}\hat{a}_{i}$. We start with an arbitrary
$\hat{a}_{0}=a_{0}$, then $f_{0}(x,a_{0},a_{0},a_{0})=x$ so the condition on
$a_{0}$ is satisfied. Now consider a general $i\in\\{0,1,\ldots,m\\}$ and take
a $\hat{b}_{i}\mathrel{-}\hat{a}_{i}$. Then

$a_{i}\mathrel{-}f_{2i}(\hat{b}_{i},a_{i},a_{i},a_{i})=f_{2i+1}(\hat{b}_{i},a_{i},a_{i},a_{i})\buildrel\rm
def\over{=}b_{i}.$

so $b_{i}\mathrel{-}a_{i}$. We continue by taking an element $\hat{c}_{i}\in
X$ such that $\hat{c}_{i}\mathrel{-}\hat{b}_{i},a_{i}$. Then

$c_{i}\buildrel\rm
def\over{=}f_{2(i+1)}(\hat{c}_{i},b_{i},\hat{c}_{i},b_{i})=f_{2i+1}(\hat{c}_{i},b_{i},\hat{c}_{i},b_{i})\mathrel{-}f_{2i+1}(\hat{b}_{i},a_{i},a_{i},a_{i})=b_{i}$

and

$d_{i}\buildrel\rm
def\over{=}f_{2(i+1)}(\hat{c}_{i},\hat{c}_{i},b_{i},b_{i})=f_{2i+1}(\hat{c}_{i},\hat{c}_{i},b_{i},b_{i})\mathrel{-}f_{2i+1}(\hat{b}_{i},a_{i},a_{i},a_{i})=b_{i}$

Finally, consider an element $\hat{a}_{i+1}\in X$ such that
$\hat{a}_{i+1}\mathrel{-}\phi_{1}(\hat{c}_{i}),\phi_{2}(\hat{c}_{i})$, define

$a_{i+1}=f_{2(i+1)}(\hat{a}_{i+1},\phi_{1}(c_{i}),\phi_{2}(d_{i}),\phi_{2}(d_{i})),$

and check the edges $a_{i+1}\mathrel{-}\phi_{1}(c_{i}),\phi_{2}(d_{i})$:

$\displaystyle
f_{2(i+1)}(\hat{a}_{i+1},\phi_{1}(c_{i}),\phi_{2}(d_{i}),\phi_{2}(d_{i}))$
$\displaystyle\mathrel{-}f_{2(i+1)}(\phi_{1}(\hat{c}_{i}),\phi_{1}(b_{i}),\phi_{1}(\hat{c}_{i}),\phi_{1}(b_{i})),$
$\displaystyle
f_{2(i+1)}(\hat{a}_{i+1},\phi_{1}(c_{i}),\phi_{2}(d_{i}),\phi_{2}(d_{i}))$
$\displaystyle\mathrel{-}f_{2(i+1)}(\phi_{2}(\hat{c}_{i}),\phi_{2}(\hat{c}_{i}),\phi_{2}(b_{i}),\phi_{2}(b_{i})),$

So $a_{i+1}\mathrel{-}\phi_{1}(c_{i})$ and
$a_{i+1}\mathrel{-}\phi_{2}(d_{i})$. Therefore for any $x\in X$ such that
$x\mathrel{-}\hat{a}_{i+1}$, we have an edge

$a_{i+1}=f_{2(i+1)}(\hat{a}_{i+1},\phi_{1}(c_{i}),\phi_{2}(d_{i}),\phi_{2}(d_{i}))\mathrel{-}f_{2(i+1)}(x,a_{i+1},a_{i+1},a_{i+1}),$

so we ensured the condition for $a_{i+1}$. We ultimately get an edge

$a_{m}\mathrel{-}f_{2m}(x,a_{m},a_{m},a_{m})=f_{2m+1}(x,a_{m},a_{m},a_{m})=a_{m}$

for some $x\mathrel{-}\hat{a}_{m}$. This gives a loop on $a_{m}$ and finishes
the proof. ∎

##  5 Cyclic terms

For $n\geq 2$, an $n$-ary cyclic term $c_{n}$ is such a term that satisfies

$c(x_{1},x_{2},x_{3}\ldots,x_{n})=c(x_{2},x_{3},\ldots,x_{n},x_{1}).$

The existence of an $n$-ary cyclic term is clearly a loop condition of the
digraph $\mathbb{D}_{n}$. The importance of cyclic terms among loop conditions
lies in the following theorem.

######  Theorem 5.1.

Every non-trivial strongly conencted loop condition $C$ is either equivalent
to the existence of a Siggers term, or to the existence of a certain cyclic
term.

Before we prove the theorem, we analyze what implications hold between the
loop conditions of cyclic terms. We can directly get the following.

######  Proposition 5.1.

For $d,n\geq 2$, where $d$ is a divisor of $n$, the following implications
between loop conditions hold.

  1. (i)

$\mathbb{D}_{n}\Rightarrow\mathbb{D}_{d}$,

  2. (ii)

$\mathbb{D}_{n}\Rightarrow\mathbb{D}_{n^{2}}$.

###### Proof.

The implication (i) follows from the existence of a digraph homomorphism
$\mathbb{D}_{n}\to\mathbb{D}_{d}$. For proving the implication (ii), we use a
standard trick: Let $\mathbb{G}=(A,G)$ be a digraph containing
$\mathbb{D}_{n^{2}}$ and compatible with an $n$-ary cyclic term $c_{n}$. We
define a digraph $\mathbb{H}$, where $x\buildrel\mathbb{H}\over{\rightarrow}y$
if and only if there is a directed $\mathbb{G}$-walk from $x$ to $y$ of length
$n$. The digraph $\mathbb{H}$ is pp-defined from $\mathbb{G}$, so it is
compatible with $c_{n}$ as well. Since $\mathbb{G}$ contained
$\mathbb{D}_{n^{2}}$, the digraph $\mathbb{H}$ contains $\mathbb{D}_{n}$, and
by compatibility with $c_{n}$, it has a loop. A loop in $\mathbb{H}$
corresponds to $\mathbb{D}_{n}$ in $\mathbb{G}$, so by second application of
$c_{n}$, we get a loop in $\mathbb{G}$. This finishes the proof. ∎

Just from these two facts, we get the following. Let $\operatorname{rad}(n)$
denote the radical of an integer $n\geq 2$, that is the product of all
distinct prime divisors of $n$.

######  Corollary 5.1.

If $\operatorname{rad}(n_{2})$ divides $\operatorname{rad}(n_{1})$, then the
$\mathbb{D}_{n_{1}}$ loop condition implies the $\mathbb{D}_{n_{2}}$ loop
condition. In particular, all the loop conditions $\mathbb{D}_{n}$ with a
fixed radical of $n$ are equivalent.

Now, we are ready prove Theorem 5.1. Consider a strongly connected loop
condition $C$. Let $n=al(\mathbb{G}_{C})$ If $n=1$, then $C$ is equivalent to
the existence of a Siggers term by Corollary 3.2. Otherwise, there is a
digraph homomorphism $\mathbb{G}_{C}\to\mathbb{D}_{n}$, and a digraph
homomorphisms $\mathbb{D}_{kn}\to\mathbb{G}_{C}$ for any $k$ that is large
enough. So there is a digraph homomorphism
$\mathbb{D}_{n^{e}}\to\mathbb{G}_{C}$ for some exponent $e$, and since the
$\mathbb{D}_{n}$ and the $\mathbb{D}_{n^{e}}$ loop conditions are equivalent,
they are both equivalent to $C$.

We finish this section with an example showing that the implications we have,
are optimal.

######  Theorem 5.2.

Let $C_{1},C_{2}$ be two non-trivial strongly connected loop conditions. Let
numbers $n_{1},n_{2}$ denote the algebraic lengths of $\mathbb{G}_{C_{1}}$,
$\mathbb{G}_{C_{2}}$ respectively. Then $C_{1}$ implies $C_{2}$ if and only if
$\operatorname{rad}(n_{2})$ divides $\operatorname{rad}(n_{1})$.

###### Proof.

If $\operatorname{rad}(n_{2})$ divides $\operatorname{rad}(n_{1})$, then
either $n_{2}=1$, or $n_{1},n_{2}\geq 2$. In the first case, $C_{2}$ is the
weakest non-trivial loop condition, and therefore implied by $C_{1}$. In the
second case, the conditions are equivalent to the existence of cyclic terms of
arities $n_{1},n_{2}$ respectively, and we get $C_{1}\Rightarrow C_{2}$ from
Corollary 5.1.

Now suppose that $\operatorname{rad}(n_{2})$ does not divide
$\operatorname{rad}(n_{1})$. So there is a prime number $p$ that divides
$n_{2}$ but not $n_{1}$. Let $A$ be the universe of the one-dimensional vector
space over the $p$-element field. We equip the set $A$ with operations of the
following form: For every $k$-tuple $\alpha_{1},\ldots,\alpha_{k}$ such that
$\alpha_{1}+\cdots+\alpha_{k}=1$, we consider the $k$-ary operation $A^{k}\to
A$:

$(x_{1},\ldots,x_{k})\mapsto\alpha_{1}x_{1}+\cdots+\alpha_{k}x_{k},$

that is, the affine combination given by coefficients
$\alpha_{1}\ldots,\alpha_{k}$. We denote the final algebra $(A,\text{affine
combinations})$ as $\mathbf{A}$. Note that all the term operations of
$\mathbf{A}$ are still just some affine combinations. The algebra $\mathbf{A}$
satisfies $C_{1}$. If $n_{1}\geq 2$, it suffices to find a cyclic affine
combination. There is the following one:

$c_{1}(x_{1},\ldots,x_{n_{1}})=\frac{1}{n_{1}}\sum_{i=1}^{n_{1}}x_{i}.$

Note that $\frac{1}{n_{1}}$ is well defined since $p$ does not divide $n_{1}$.
If $n_{1}=1$, it suffices to find any satisfied loop condition. There is the
Maltsev term $m(x,y,z)=x-y+z$ satisfying $m(y,x,x)=m(z,z,y)$.

On the other hand, there is no $n_{2}$-ary cyclic term in $\mathbf{A}$. For a
contradiction, consider such a term $c_{2}$:

$c_{2}(x_{1},\ldots,x_{n_{2}})=\sum_{i=1}^{n_{2}}a_{i}x_{i}.$

Let $0$ denote the zero vector in $\mathbf{A}$, and $1$ denote an arbitrary
non-zero vector. Since $c_{2}$ is cyclic, all the values

$c_{2}(1,0,\ldots,0)=c_{2}(0,1,0,\ldots,0)=\cdots=c_{2}(0,\ldots,0,1)$

are equal. Therefore $a_{1}=a_{2}=\cdots=a_{n_{2}}$. But then

$\sum_{i=1}^{n_{2}}a_{i}=n_{2}a_{1}=0$

since $p$ divides $n_{2}$. This contradicts the fact that $c_{2}$ should be
affine, and the sum is supposed to be equal to 1. ∎

##  6 Without strong conectedness

The case of loop conditions that are not strongly connected is largely open.
It seems that there is no further big collapse of loop conditions up to
equivalence. We provide two basic counterexamples concerning loop conditions
that are not strongly connected, and then we provide a few of positive
results.

###  6.1 Counter-examples

We have shown that all the non-trivial loop conditions corresponding to a
digraph with a strongly connected component of algebraic length one are
equivalent. In our first example we demonstrate that there is no other loop
condition equivalent to them.

######  Example 6.1.

There is an algebra $\mathbf{A}=(A,s)$ and a compatible digraph
$\mathbb{G}=(A,G)$ such that $s$ is an idempotent 6-ary Siggers operation,
$\mathbb{G}$ does not have a loop but any countable digraph without a strongly
connected component with algebraic length 1 can be homomorphicly mapped into
$\mathbb{G}$. Therefore $\mathbf{A}$ satisfies all the non-trivial loop
conditions corresponding to a digraph with a strongly connected component with
algebraic length one, but it satisfies no other non-trivial loop condition.

###### Proof.

Let $\mathbb{G}_{0}=(A_{0},G_{0})$ be the disjoint union of directed cycles of
all lengths $l\geq 2$. First, we show that $\mathbb{G}_{0}$ is compatible with
an idempotent algebra $\mathbf{A}_{0}=(A_{0},s_{0})$, where $s_{0}$ is a 6-ary
Siggers operation.

We define $\sim$ as the smallest reflexive symmetric binary relation on
$A_{0}^{6}$ that satisfies

$(x,x,y,y,z,z)\sim(y,z,z,x,x,y)$

for any $x,y,z\in A_{0}$. Note that this relation is also transitive: The only
non-trivial way of applying transitivity is by interpretting a single six-
tuple as both $(x,x,y,y,z,z)$ and $(y,z,z,x,x,y)$, but then $x=y=z$, and we
generate just the reflexivity on constant tuples.

Let $\phi\colon A_{0}\to A_{0}$ be the mapping that maps $x$ to $y$ such that
$x\buildrel\mathbb{G}_{0}\over{\rightarrow}y$, and let $S$ be a factor set
$A_{0}^{6}/\sim$. The function $\phi$ is clearly compatible with $\sim$, so
$\phi$ acts on $S$ as well. In order to construct an idempotent Siggers
operation, we need to find a mapping $s_{0}\colon S\to A_{0}$ that maps
constant six-tuples to the appropriate elements and commutes with $\phi$. The
constant tuples has just one-element equivalent classes in $\sim$, and they
are closed under $\phi$, so we can handle them independently of the rest, and
simply map them to the appropriate elements.

Now, consider any other element $\mathbf{x}\in S$ represented by a six-tuple

$\bar{x}=(x_{1},x_{2},x_{3},x_{4},x_{5},x_{6})\in A_{0}^{6}.$

The element $\mathbf{x}$ is in a $\phi$-cycle of a finite length $l$ that is
less than or equal to the product of the lengths of the cycles containing
$x_{1},\ldots,x_{6}$. If $l\geq 2$, we can map that cycle into $\mathbb{G}$.
It remains to check that the possibility $l=1$ cannot happen. For a
contradiction, assume that $\phi(\mathbf{x})=\mathbf{x}$, that is,
$\phi(\bar{x})\sim\bar{x}$. Since $\phi(x_{1})\neq x_{1}$, also
$\phi(\bar{x})\neq\bar{x}$. Therefore there are $x,y,z\in A_{0}$ such that

$\bar{x}=(x,x,y,y,z,z)\text{ and }\psi(\bar{x})=(y,z,z,x,x,y),$

where $\psi$ stands for either $\phi$ of $\phi^{-1}$. Then we have
$y=\psi(x)=z$ and $z=\psi(y)=x$, and we get a contradiction with the
assumption that $\bar{x}$ is non-constant.

Now, we construct the promised example. Take the algebra
$\mathbf{A}_{1}=(\mathbb{Q},s)$, where $\mathbb{Q}$ denotes the set of all
rational numbers, and $s_{1}$ is the arithmetical mean of six elements. Note
that $s_{1}$ satisfies the Siggers equation as well. We set
$\mathbf{A}=\mathbf{A}_{0}\times\mathbf{A}_{1}=(A,s)$. The digraph
$\mathbb{G}=(A,G)$ is defined as follows:

$(x_{1},q_{1})\buildrel\mathbb{G}\over{\rightarrow}(x_{2},q_{2})\buildrel\rm
def\over{\Leftrightarrow}q_{1}<q_{2}\text{ or }(q_{1}=q_{2}\text{ and
}(x_{1},x_{2})\in G_{0}).$

Now, consider six edges $((x_{i},p_{i}),(y_{i},q_{i}))\in G$ for
$i=1,2,3,4,5,6$. Let $((x,p),(y,q))$ be the result of applying $s$ to them. We
have to check that the resulting edge is in $G$ as well. We distinguish two
cases. If $p_{i}<q_{i}$ for some $i$, then $p<q$, so
$(x,p)\buildrel\mathbb{G}\over{\rightarrow}(y,q)$. Otherwise for all $i$,
$p_{i}=q_{i}$ and $x_{i}\buildrel\mathbb{G}_{0}\over{\rightarrow}y_{i}$. In
that case $p=q$ and $x\buildrel\mathbb{G}_{0}\over{\rightarrow}y$, so
$(x,p)\buildrel\mathbb{G}\over{\rightarrow}(y,q)$.

Finally, we observe that any countable digraph $\mathbb{H}$ having no strongly
connected component with algebraic length 1 can be homomorphically mapped to
$\mathbb{G}$. Modulo the strong conectedness, the digraph $\mathbb{H}$ has no
loop, so it can be mapped into $(\mathbb{Q},<)$, since $(\mathbb{Q},<)$
contains all strict partial orders as subdigrahs. Finally, every strongly
connected component of $\mathbb{H}$ can be mapped into $G_{0}$ since it has
algebraic length bigger than one. These two mappings together form the digraph
homomorphism $\mathbb{H}\to\mathbb{G}$. ∎

Our second example shows that if we do not require at least some cycles in the
digraph, we cannot get a loop even under quite strong assumptions. In
particular, our example is locally finite, has a ternary near unanimity
operation, and the compatible digraph forms an $\omega$-categorical structure.

######  Example 6.2.

Let $\mathbf{A}=(\\{0,1\\},m)$ be the two-element algebra, where $m$ is the
majority operation

$m(x,x,y)=m(x,y,x)=m(y,x,x)=x.$

There is a smooth loopless digraph $\mathbf{G}$ compatible with a subalgebra
$\mathbf{B}\leq\mathbf{A}^{\omega}$, such that $\mathbb{G}$ contains as
subdigraphs all countable digraphs without directed cycles.

###### Proof.

Regard elements of $\mathbf{A}^{\omega}$ as infinite sequences indexed by
rational numbers, that is functions $a\colon\mathbb{Q}\to\\{0,1\\}$. For
$q\in\mathbb{Q}$ define $b_{q}\in\mathbf{A}^{\omega}$ as follows

$b_{q}(x)=\begin{cases}0&\text{if }x\leq q,\cr 1&\text{if }x>q.\cr\end{cases}$

Then if $q_{1},q_{2},q_{3}\in\mathbb{Q}$, the value
$m(b_{q_{1}},b_{q_{2}},b_{q_{3}})$ equals the function $b_{q}$, where $q$ is
the median element of the triple $(q_{1},q_{2},q_{3})$. Therefore, the set
$B=\\{b_{q}:q\in\mathbb{Q}\\}$ is a subuniverse, and we consider the
subalgebra $\mathbf{B}=(B,m)$.

The digraph $\mathbb{G}=(B,G)$ is constructed by putting
$(b_{q_{1}},b_{q_{2}})\in G$ if and only if $q_{1}<q_{2}$. This digraph
contains all countable digraphs without directed cycles since any countable
strict partial order is a subdigraph of $(\mathbb{Q},<)$.

It is not difficult to check that $\mathbb{G}$ is compatible with the
operation $m$, that is that the strict order is compatible with median
operation. Let $m^{\prime}$ denote the median of three rational numbers.
Consider three pairs $p_{1}<q_{1}$, $p_{2}<q_{2}$, $p_{3}<q_{3}$, we check
$m^{\prime}(p_{1},p_{2},p_{3})<m^{\prime}(q_{1},q_{2},q_{3})$. Without loss of
generality, $p_{1}\leq p_{2}\leq p_{3}$, so
$m^{\prime}(p_{1},p_{2},p_{3})=p_{2}$. Both $q_{2}$ and $q_{3}$ are strictly
greater than $p_{2}$, therefore
$m^{\prime}(q_{1},q_{2},q_{3})>p_{2}=m^{\prime}(p_{1},p_{2},p_{3})$. ∎

###  6.2 Partial positive results

Here we show a few loop conditions that are not strongly connected, and are
satisfied by certain algebras. We begin with the definitions.

A _Maltsev term_ is an idempotent ternary term $m$ satisfying the equation
$m(y,x,x)=m(z,z,y)$. By a _non-idempotent Maltsev term_ we mean a term $m$
satisfying this equation but not being necessarily idempotent. The existence
of a Maltsev term is a loop condition given by the graph $x\to y\to
z\leftarrow x$.

A _near unanimity term_ (briefly _NU term_) is an $n$-ary term $t$ such that
$t(x,\ldots,x,y,x,\ldots,x)=x$ for any position of $y$. Here, we will be
primarily interested in ternary NU term, that is, a term $t$ such that
$t(x,x,y)=t(x,y,x)=t(y,x,x)=x$.

By a _cone_ , we mean the digraph given by
$c_{1}\mathrel{\rightarrow}\cdots\mathrel{\rightarrow}c_{n}\to c_{1}$, where
$n\geq 2$, $a\mathrel{\rightarrow}c_{i}$ for any $1\leq i\leq n$, and
$b\mathrel{\rightarrow}a$.

######  Proposition 6.1.

Non-idempotent Maltsev term implies any weakly connected loop condition with
algebraic length 1.

###### Proof.

Consider a digraph $\mathbb{G}=(A,G)$ having a weakly connected component of
algebraic length 1, and compatible with an algebra $\mathbf{A}$ with a Maltsev
term $m$. Since $\mathbb{G}$ has algebraic length 1, there is an oriented
cycle $a_{0},a_{1},\ldots,a_{n-1},a_{0}$ such that
$a_{i}\buildrel\mathbb{G}\over{\rightarrow}a_{i+1}$ or
$a_{i}\buildrel\mathbb{G}\over{\leftarrow}a_{i+1}$ for every $i=0.\ldots,n-1$
(we calculate indices modulo $n$ in this proof), and the number or right
arrows exceeds the number of left arrows by one. We prove our proposition by
induction on $n$. If $n=1$, we have a loop.

If $n>1$, we distinguish two cases.

  1. (a)

There is a zig-zag pattern in the cycle
$a_{i}\buildrel\mathbb{G}\over{\rightarrow}a_{i+1}\buildrel\mathbb{G}\over{\leftarrow}a_{i+2}\buildrel\mathbb{G}\over{\rightarrow}a_{i+3}$,
or
$a_{i}\buildrel\mathbb{G}\over{\leftarrow}a_{i+1}\buildrel\mathbb{G}\over{\rightarrow}a_{i+2}\buildrel\mathbb{G}\over{\leftarrow}a_{i+3}$.

  2. (b)

There is no zig-zag pattern in the cycle, that is, each arrow is next to an
arrow of the same direction.

If there is a zig-zag pattern, we pp-define a digraph $\mathbb{H}=(A,H)$ by
$y_{1}\buildrel\mathbb{H}\over{\rightarrow}y_{2}$ if there are $x,z$ such that
$y_{1}\buildrel\mathbb{G}\over{\rightarrow}z\buildrel\mathbb{G}\over{\leftarrow}x\buildrel\mathbb{G}\over{\rightarrow}y_{2}$.
Notice that $H\supset G$, and $\mathbb{H}$ builds a “bridge”
$a_{i}\buildrel\mathbb{H}\over{\rightarrow}a_{i+3}$, or
$a_{i+3}\buildrel\mathbb{H}\over{\rightarrow}a_{i}$ to the zig-zag pattern. So
if we omit $a_{i+1},a_{i+2}$, the cycle has still algebraic length one in
$\mathbb{H}$. By induction hypothesis, Maltsev term imply the loop condition
of that shorter cycle, so $\mathbb{H}$ has a loop. A loop in $\mathbb{H}$
corresponds to
$x\buildrel\mathbb{G}\over{\rightarrow}y\buildrel\mathbb{G}\over{\rightarrow}z,x\buildrel\mathbb{G}\over{\rightarrow}z$,
which is the digraph of the non-idempotent maltsev term. Therefore
$\mathbb{G}$ has a loop.

If there is no zig-zag pattern in the cycle, we use the following pp-
definition. $x_{1}\buildrel\mathbb{H}\over{\rightarrow}x_{2}$ if there are
$y,z$ such that
$x_{1}\buildrel\mathbb{G}\over{\rightarrow}y\buildrel\mathbb{G}\over{\rightarrow}z\buildrel\mathbb{G}\over{\leftarrow}x_{2}$.
Now, we have $x_{1}\buildrel\mathbb{H}\over{\rightarrow}x_{2}$ whenever
$x_{1}\buildrel\mathbb{G}\over{\rightarrow}x_{2}$ and $x_{2}$ has an outcoming
edge. Nevertheless, we can omit all the peaks from our cycle. Whenever we have

$a_{i}\buildrel\mathbb{G}\over{\rightarrow}a_{i+1}\buildrel\mathbb{G}\over{\rightarrow}a_{i+2}\buildrel\mathbb{G}\over{\leftarrow}a_{i+3}\buildrel\mathbb{G}\over{\leftarrow}a_{i+4},$

we can discard $a_{i+2}$ since
$a_{i}\buildrel\mathbb{H}\over{\rightarrow}a_{i+3}$. Therefore we get a
shorter cycle in $\mathbb{H}$ following a loop in $\mathbb{H}$. As in the
previous case, a loop in $\mathbb{H}$ corresponds to a digraph
$x\buildrel\mathbb{G}\over{\rightarrow}y\buildrel\mathbb{G}\over{\rightarrow}z,x\buildrel\mathbb{G}\over{\rightarrow}z$
that implies a loop using the Maltsev term. ∎

######  Proposition 6.2.

Ternary near unanimity term implies the “cone” loop condition.

###### Proof.

Let $\mathbf{A}=(A,t)$ be an algebra where $t$ is a ternary near unanimity
term, and assume that there is a graph (denoted by arrows) compatible with
$\mathbf{A}$. Moreover assume that a cone $a,b,c_{1},\ldots,c_{n}$ is a
subgraph of the graph. We need to prove that the graph contains a loop.

We set $x_{n}=c_{n}$ and recursively construct elements
$x_{n-1},x_{n-2},\ldots,x_{1}\in\mathbf{A}$: by $x_{i}=m(x_{i+1},c_{i}.a)$.

We get a loop on $x_{1}$ by proving the following properties by induction

  1. (i)

$x_{i}\mathrel{\rightarrow}c_{1}$ for all $n\geq i\geq 1$,

  2. (ii)

$a\mathrel{\rightarrow}x_{i}$ for all $n\geq i\geq 1$,

  3. (iii)

$x_{i}\mathrel{\rightarrow}x_{i+1}$ for all $n-1\geq i\geq 1$.

When they are proved, there is a loop by

$x_{1}=m(x_{1},x_{1},b)\mathrel{\rightarrow}m(x_{2},c_{1},a)=x_{1}.$

The proof is straighforward. We check the first step of induction:

  1. (i)

$x_{n}=c_{n}\mathrel{\rightarrow}c_{1}$,

  2. (ii)

$a\mathrel{\rightarrow}c_{n}=x_{n}$,

  3. (iii)

$x_{n-1}=m(x_{n},c_{n-1},a)\mathrel{\rightarrow}m(c_{1},c_{n},c_{n})=x_{n}$,

and the induction step:

  1. (i)

$x_{i-1}=m(x_{i},c_{i-1},a)\mathrel{\rightarrow}m(c_{1},c_{i},c_{1})=c_{1}$,

  2. (ii)

$a=m(a,a,b)\mathrel{\rightarrow}m(x_{i},c_{i-1},a)=x_{i-1}$,

  3. (iii)

$\displaystyle x_{i-1}=m(x_{i},c_{i-1},a)$
$\displaystyle\mathrel{\rightarrow}m(x_{i+1},c_{i},x_{i+1})=x_{i+1},$
$\displaystyle x_{i-1}=m(x_{i},c_{i-1},a)$
$\displaystyle\mathrel{\rightarrow}m(x_{i+1},c_{i},c_{i})=c_{i},$
$\displaystyle x_{i-1}=m(x_{i-1},x_{i-1},b)$
$\displaystyle\mathrel{\rightarrow}m(x_{i+1},c_{i},a)=x_{i}.$

This finishes the proof. ∎

However, we don’t have an answer to the following question.

######  Question 6.1.

Does the existence of a 4-ary near unanimity term

$t(y,x,x,x)=t(x,y,x,x)=t(x,x,y,x)=t(x,x,x,y)=x$

imply any loop condition that is not equivalent to the $\mathbb{K}_{3}$ loop
condition?

## References

  * [1] Keith A. Kearnes and Emil Kiss.  The shape of congruence lattices, volume 1046.  Providence, Rhode Island : American Mathematical Society, 03 2013.
  * [2] Libor Barto and Marcin Kozik.  Absorption in Universal Algebra and CSP.  In Andrei Krokhin and Stanislav Zivny, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 45–77. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017.
  * [3] Libor Barto, Marcin Kozik, and Todd Niven.  The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of Bang-Jensen and Hell).  SIAM J. Comput., 38(5):1782–1802, 2008/09.
  * [4] Libor Barto, Andrei Krokhin, and Ross Willard.  Polymorphisms, and How to Use Them.  In Andrei Krokhin and Stanislav Zivny, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 1–44. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017.
  * [5] Libor Barto and Michael Pinsker.  The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems.  In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS ’16, pages 615–622, New York, NY, USA, 2016. ACM.
  * [6] Clifford Bergman.  Universal algebra, volume 301 of Pure and Applied Mathematics (Boca Raton).  CRC Press, Boca Raton, FL, 2012.  Fundamentals and selected topics.
  * [7] Clifford Bergman, Roger D. Maddux, and Don Pigozzi, editors.  Algebraic Logic and Universal Algebra in Computer Science, Conference, Ames, Iowa, USA, June 1-4, 1988, Proceedings, volume 425 of Lecture Notes in Computer Science. Springer, 1990.
  * [8] Andrei A. Bulatov.  $H$-coloring dichotomy revisited.  Theoret. Comput. Sci., 349(1):31–39, 2005.
  * [9] Pavol Hell and Jaroslav Nešetřil.  On the complexity of $H$-coloring.  J. Combin. Theory Ser. B, 48(1):92–110, 1990.
  * [10] Alexandr Kazda.  Taylor term does not imply any nontrivial linear one-equality Maltsev condition.  Preprint arXiv:1409.4601, 2017.
  * [11] Keith Kearnes, Petar Marković, and Ralph McKenzie.  Optimal strong Mal’cev conditions for omitting type 1 in locally finite varieties.  Algebra Universalis, 72(1):91–100, 2014.
  * [12] Miroslav Olšák.  Loop conditions.  Preprint arXiv:1701.00260, 2017.
  * [13] Mark H. Siggers.  A strong Mal’cev condition for locally finite varieties omitting the unary type.  Algebra Universalis, 64(1-2):15–20, 2010.