# Słupecki digraphs

Ádám Kunos  Bolyai Institute, University of Szeged<EMAIL_ADDRESS>,
Benoît Larose  Laboratoire d’Algèbre, de Combinatoire et d’Informatique
Mathématique (LACIM)
Université du Québec à Montréal<EMAIL_ADDRESS>and  David Emmanuel
Pazmiño Pullas  Laboratoire d’Algèbre, de Combinatoire et d’Informatique
Mathématique (LACIM)
Université du Québec à Montréal
<EMAIL_ADDRESS>
###### Abstract.

Call a finite relational structure $k$-Słupecki if its only surjective $k$-ary
polymorphisms are essentially unary, and Słupecki if it is $k$-Słupecki for
all $k\geq 2$. We present conditions, some necessary and some sufficient, for
a reflexive digraph to be Słupecki. We prove that all digraphs that
triangulate a 1-sphere are Słupecki, as are all the ordinal sums $m\oplus n$
($m,n\geq 2$). We prove that the posets $\mathbb{P}=m\oplus n\oplus k$ are not
3-Słupecki for $m,n,k\geq 2$, and prove there is a bound $B(m,k)$ such that
$\mathbb{P}$ is 2-Słupecki if and only if $n>B(m,k)+1$; in particular there
exist posets that are 2-Słupecki but not 3-Słupecki.

We wish to thank Barnaby Martin for his very helpful comments.

##  1\. Introduction

For our purposes, a digraph is a finite, non-empty set $A$ together with a
binary relation on $A$. In this paper, all digraphs are assumed to be
reflexive, i.e. that the binary relation contains $(a,a)$ for all $a\in A$. We
study the surjective polymorphisms of these objects; these operations play an
important role in the complexity of the related quantified constraint
satisfaction problem (QCSP) and the surjective H-colouring problem, as do
idempotent polymorphisms in the study of the associated CSP (see for instance
[10, 11, 12, 16]).

A digraph is $k$-idempotent trivial if all its $k$-ary idempotent
polymorphisms are projections, and idempotent trivial if it is $k$-idempotent
trivial for all $k$. Similarly, we say a digraph is $k$-Słupecki if all its
$k$-ary surjective polymorphisms are essentially unary, and Słupecki if it is
$k$-Słupecki for all $k$. Clearly a digraph is idempotent trivial if it is
Słupecki. It is known that these properties respectively imply NP-hardness and
PSPACE-hardness of the CSP and QCSP naturally associated to the digraph (see
[10] and [16]). The Słupecki property has also been studied independently, see
for example [3] and [4].

The starting point of our investigation was to find some workable sufficient
condition for a digraph to be Słupecki: in particular, we wanted to verify
that all cycles of girth at least 4 have this property. There is a known
sufficient condition for a digraph to be idempotent trivial that relies on the
homotopy of a simplicial complex naturally associated to the digraph (see
section 2): if for some $n>0$ the $n$-th homotopy group of the space is non-
trivial, but the $n$-th homotopy group of any proper retract is trivial, and
provided the identity is isolated in the digraph of endomorphisms, then the
digraph is idempotent trivial [9]. It turns out that digraphs that triangulate
$n$-spheres satisfy these properties, and thus are potentially Słupecki. At
first glance, the most straightforward approach to show a structure is
Słupecki is to pp-define the Słupecki relation from its basic relations (see
Section 4), and we manage to do this for a variety of digraphs triangulating
$n$-spheres; however, this approach seems impractical for general cycles. In
section 3 we present an alternative sufficient condition: provided the
identity is isolated in the digraph of endomorphisms, if every onto
polymorphism of the idempotent trivial digraph is a retraction, then the
digraph is Słupecki (see Lemma 3.2 and Theorem 3.3). In a companion paper,
this result is used to prove that cycles of girth at least 4 are indeed
Słupecki [6]. The slightly annoying technical condition on the identity
endomorphism can be removed for several families of digraphs (Lemmas 3.6 and
3.7), but we provide an example of a Słupecki digraph that does not satisfy it
(Lemma 3.8). However, we do not know if the condition can be removed from the
statement of Lemma 3.2.

As mentioned above, examining small digraphs triangulating spheres, it turns
out that many are Słupecki, such as for instance, all digraphs that
triangulate a 1-sphere (Theorem 4.11), but in section 5 we provide an example
of a small digraph triangulating a 2-sphere which isn’t Słupecki: indeed, the
poset $2\oplus 2\oplus 2$ satisfies the conditions of Theorem 5.2, and is the
suspension of a 4-cycle. Furthermore, we provide examples of posets that are
2-Słupecki but not 3-Słupecki (Theorem 5.5); contrast this with the fact that
all digraphs that are 2-idempotent trivial are idempotent trivial (see [17]).

We now outline the contents of the paper. In section 2 we introduce basic
terminology and notation. In section 3 we present various sufficient and
necessary conditions for a digraph to be Słupecki. The main result of that
section, Theorem 3.3, is a crucial tool for the main result of the paper [6],
namely that all cycles of girth at least 4 are Słupecki, and is also used in
section 5 to provide some examples of Słupecki posets. In section 4 we prove
that various digraphs that triangulate spheres are indeed Słupecki, via pp-
definitions using gadgets. We also state the result that all digraphs that
triangulate 1-spheres are Słupecki (Theorem 4.11). In section 5 we consider
posets that are ordinal sums of antichains; we exhibit small digraphs that
triangulate spheres but are not Słupecki (Theorem 5.2); we also provide
examples of posets that are 3-Słupecki but not 2-Słupecki Theorem 5.5. In
section 6 we discuss various open questions that follow naturally from our
results.

##  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$; an arc of the form $(x,x)$ we call a loop. 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 undirected graph $\mathbb{G}_{Sym}$ 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 $\mathbb{G}_{Sym}$ is
connected. We say the digraph $\mathbb{G}$ is symmetric if $x\rightarrow y$
implies $y\rightarrow x$ for all $x,y\in G$ (i.e. $\mathbb{G}$ is undirected).
Let $\mathbb{G}$ be a digraph and $x,y\in G$. We say that $x$ and $y$ are in
the same strong component of $\mathbb{G}$ if there exist
$x=x_{0},x_{1},\cdots,x_{t}=y$ and $y=y_{0},y_{1},\cdots,y_{s}=x$ such that
$x_{i}\rightarrow x_{i+1}$ for all $0\leq i\leq t-1$ and $y_{j}\rightarrow
y_{j+1}$ for all $0\leq j\leq s-1$. Clearly every digraph is partitioned into
strongly connected components. We say $\mathbb{G}$ is strongly connected if it
has exactly one strong component. 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}$.

Let $\mathbb{G}$ and $\mathbb{H}$ be digraphs. A map $f:G\rightarrow H$ is a
homomorphism if it preserves arcs, i.e. if $(x,y)$ is an arc of $\mathbb{G}$
then $(f(x),f(y))$ is an arc of $\mathbb{H}$. If $\mathbb{G}$ and $\mathbb{H}$
are digraphs and we write $f:\mathbb{H}\rightarrow\mathbb{G}$ it is understood
that $f$ is a homomorphism. We say $f:\mathbb{H}\rightarrow\mathbb{G}$ is an
embedding if it is an isomorphism onto its image (and hence $\mathbb{H}$ is
embedded in $\mathbb{G}$). 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}$; the integer $k$ is the
arity of $f$; $f$ 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$; it is a projection if furthermore the homomorphism $g$
is the identity.

######  Definition 2.1.

Let $k\geq 2$. We say that the digraph $\mathbb{G}$ is $k$-idempotent trivial
if all its idempotent $k$-ary polymorphisms are projections. We say that the
digraph $\mathbb{G}$ is idempotent trivial if it is $k$-idempotent trivial for
all $k\geq 2$.

######  Definition 2.2.

Let $k\geq 2$. We say that the digraph $\mathbb{G}$ is $k$-Słupecki if all its
surjective $k$-ary polymorphisms are essentially unary. We say the digraph
$\mathbb{G}$ is Słupecki if it is $k$-Słupecki for all $k\geq 2$.

It is easy to see that if a digraph is $k$-Słupecki for some $k\geq 3$ then it
is $(k-1)$-Słupecki. Note also that a Słupecki digraph is idempotent trivial.

######  Definition 2.3.

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.4.

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.

We now discuss briefly the connection of reflexive digraphs to simplicial
complexes: all details can be found in [13], see also [9]. A digraph
$\mathbb{P}$ is a poset if its edge relation is reflexive, antisymmetric (if
$(x,y)$ and $(y,x)$ are arcs then $x=y$) and transitive (if $(x,y)$ and
$(y,z)$ are arcs so is $(x,z)$). We usually denote the relation on a poset by
$\leq$. A poset $\mathbb{P}$ is a chain or totally ordered set if for every
$x,y\in P$ either $x\leq y$ or $y\leq x$.

Let $\mathbb{G}$ be a digraph. Define a simplicial complex $K(\mathbb{G})$ as
follows: a subset $S$ of $G$ is a simplex of $K(\mathbb{G})$ if there exists a
totally ordered set $\mathbb{P}$ and a homomorphism from $\mathbb{P}$ to
$\mathbb{G}$ whose image is $S$. We will call $K(\mathbb{G})$ the simplicial
realisation of $\mathbb{G}$, and we will say that $\mathbb{G}$ triangulates a
topological space $X$ if $X$ is homeomorphic to the geometric realisation of
$K(\mathbb{G}).$

Let $\mathbb{G}$ be a digraph. The suspension of $\mathbb{G}$ is the digraph
obtained from $\mathbb{G}$ by adding two vertices $u$ and $v$ that are
adjacent to every vertex of $\mathbb{G}$ (by a two-way edge) and nothing else
(see Figure 1). It turns out that the geometric realisation of the suspension
of $\mathbb{G}$ is homeomorphic to the suspension of the geometric realisation
of $\mathbb{G}$ (hence the name).

Figure 1. A digraph and its suspension.

For posets we can refine the construction a bit. Given two posets $\mathbb{P}$
and $\mathbb{Q}$, their ordinal sum $\mathbb{P}\oplus\mathbb{Q}$ is the poset
obtained from the disjoint union of $\mathbb{P}$ and $\mathbb{Q}$ by adding
the relations $p\leq q$ for all $p\in P$ and $q\in Q$. An antichain is a
totally disconnected poset, i.e. with no edges except loops. In ordinal sums,
we denote the $n$-element antichain simply by $n$. The poset suspension of
$\mathbb{P}$ is the poset $\mathbb{P}\oplus 2$. It turns out that the
geometric realisation of the suspension of $\mathbb{P}$ is homeomorphic to the
suspension of the geometric realisation of $\mathbb{P}$ (hence the name).

##  3\. A sufficient condition

In this section we present various necessary and sufficient conditions for a
digraph to be Słupecki. The main result, Theorem 3.3, will be used in sections
4 and 5 and is a central tool in [6].

Let $\mathbb{G}$, $\mathbb{H}$ be digraphs. The digraph
$Hom(\mathbb{G},\mathbb{H})$ is defined as follows: its vertices are the
homomorphisms $\mathbb{G}\rightarrow\mathbb{H}$, and we have an arc $(f,g)$ if
$(f(x),g(y))$ is an arc of $\mathbb{H}$ whenever $(x,y)$ is an arc of
$\mathbb{G}$. It is easy to verify that if $f,g,h\in
Hom(\mathbb{G},\mathbb{G})$ and $f\rightarrow g$ then $h\circ f\rightarrow
h\circ g$ (see Lemma 2.1 of [9]).

######  Lemma 3.1.

Let $\mathbb{G}$ be a digraph such that the identity is an isolated loop in
$Hom(\mathbb{G},\mathbb{G})$. If $f:\mathbb{G}^{p}\rightarrow\mathbb{G}$ is an
onto, essentially unary polymorphism then $f$ is an isolated loop in
$Hom(\mathbb{G}^{p},\mathbb{G})$.

###### Proof.

It suffices to show the result for projections: indeed, if $f$ is an onto
essentially unary polymorphism of arity $p$ then $f=\sigma\circ\pi$ for some
projection $\pi$ and some automorphism $\sigma$ of $\mathbb{G}$. If
$f\rightarrow g$ then $\pi\rightarrow\sigma^{-1}\circ g$ so if the result
holds for projections then $\pi=\sigma^{-1}\circ g$ and $f=g$; similarly if
$g\rightarrow f$.

Suppose that $\pi\rightarrow f$ in $Hom(\mathbb{G}^{p},\mathbb{G})$ where
$\pi$ is a projection (the case $f\rightarrow\pi$ is identical). Without loss
of generality, suppose that $\pi$ is the first projection. Fix
$a_{2},\dots,a_{p}\in G$ and define $g(x)=f(x,a_{2},\dots,a_{p})$. Then it is
clear that $id\rightarrow g$ in $Hom(\mathbb{G},\mathbb{G})$. Thus $g=id$ and
hence $f$ is the first projection.

∎

For $i=1,\dots,p$ let $\pi_{i}:\mathbb{G}^{p}\rightarrow\mathbb{G}$ denote the
$i$-th projection.

######  Lemma 3.2.

Let $\mathbb{G}$ be a digraph and let $f:\mathbb{G}^{p}\rightarrow\mathbb{G}$
be an onto polymorphism of arity at least 2. Then $(2)\Rightarrow(1)$:

  1. (1)

there exists an embedding $e:\mathbb{G}\hookrightarrow\mathbb{G}^{p}$ such
that the restriction of $f$ to $e(\mathbb{G})$ is onto;

  2. (2)

$f$ is essentially unary.

if $\mathbb{G}$ is idempotent trivial such that the identity is an isolated
loop in $Hom(\mathbb{G},\mathbb{G})$, the converse holds.

###### Proof.

$(2)\Rightarrow(1)$: suppose $f$ is onto and depends only on its $i$-th
variable; then the required embedding is
$e:\mathbb{G}\hookrightarrow\mathbb{G}^{p}$ defined by
$e(x)=(a,a,\dots,a,x,a,\dots,a)$ where $a$ is any fixed vertex in $\mathbb{G}$
and $x$ appears in the $i$-th position.

Now assume that $\mathbb{G}$ is idempotent trivial and that the identity is an
isolated loop in $Hom(\mathbb{G},\mathbb{G})$: we prove $(1)\Rightarrow(2)$.
First notice that if $\mathbb{G}$ is idempotent trivial then it must be
connected: one can easily construct a binary idempotent polymorphism which is
a non-projection if $\mathbb{G}$ is not connected. Let
$f:\mathbb{G}^{p}\rightarrow\mathbb{G}$ and
$e:\mathbb{G}\hookrightarrow\mathbb{G}^{p}$ be such that
$f(e(\mathbb{G}))=\mathbb{G}$. It follows that $f\circ e=\sigma$ for some
automorphism $\sigma$ of $\mathbb{G}$. Define an operation
$\phi:\mathbb{G}^{p}\rightarrow\mathbb{G}$ by

$\phi(x_{1},\dots,x_{p})=\sigma^{-1}f(\pi_{1}(e(x_{1})),\dots,\pi_{p}(e(x_{p}))).$

Then
$\phi(x,\dots,x)=\sigma^{-1}f(\pi_{1}(e(x)),\dots,\pi_{p}(e(x)))=\sigma^{-1}f(e(x))=x$
and thus $\phi$ is idempotent. Since $\mathbb{G}$ is idempotent trivial there
exists some $i$ such that $\phi(x_{1},\dots,x_{p})=x_{i}$ for all
$x_{1},\dots,x_{p}$. We may suppose without loss of generality that $i=1$, and
thus

$f(\pi_{1}(e(x_{1})),\dots,\pi_{p}(e(x_{p})))=\sigma(x_{1})$

for all $x_{i}$; in particular, if we let
$\mathbb{H}_{i}=\pi_{i}(e(\mathbb{G}))$ for all $i=1,\dots,p$, we conclude
that $\mathbb{H}_{1}=\mathbb{G}$. Let $k$ be the largest index $i$ such that
$\mathbb{H}_{i}=\mathbb{G}$: notice that for each $1\leq i\leq k$,
$\sigma_{i}=\pi_{i}\circ e$ is an automorphism of $\mathbb{G}$. If $k=p$ then
we’ve shown that $f$ depends only on its first variable. Otherwise, consider
the map $\psi:\mathbb{G}^{p-k}\rightarrow Hom(\mathbb{G}^{k},\mathbb{G})$
where $\psi(b_{k+1},\dots,b_{p})$ is the homomorphism
$(x_{1},\dots,x_{k})\mapsto f(x_{1},\dots,x_{k},b_{k+1},\dots,b_{p})$. Clearly
$\psi$ is a homomorphism, and since $\mathbb{G}^{p-k}$ is connected, so is the
image of $\psi$. Choose elements $c_{j}\in\mathbb{H}_{j}$, $k+1\leq j\leq p$.
Then by the above identity we have that
$\psi(c_{k+1},\dots,c_{p})(x_{1},\dots,x_{k})=\sigma(\sigma_{1}^{-1}(x_{1}))$;
in particular $\tau=\psi(c_{k+1},\dots,c_{p})$ is an essentially unary onto
polymorphism. By Lemma 3.1, it is an isolated loop and hence $\psi$ is a
constant map with value $\tau$; in other words,
$f(x_{1},\dots,x_{p})=\sigma(\sigma_{1}^{-1}(x_{1}))$ for all $x_{j}$ and we
are done. ∎

We remark in passing that if the condition that $\mathbb{G}$ is idempotent
trivial is dropped then the implication $(1)\Rightarrow(2)$ in the previous
result is not necessarily true (the construction of a binary non-projection
idempotent polymorphism on a disconnected digraph easily shows this.)

######  Theorem 3.3.

Let $n\geq 1$ and let $\mathbb{G}$ triangulate an $n$-sphere. 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.

###### Proof.

If $\mathbb{G}$ triangulates an $n$-sphere then the $n$-th homotopy group of
the geometric realisation of $\mathbb{G}$ is non-trivial, but every proper
retract of $\mathbb{G}$ has a contractible realisation and hence has trivial
homotopy. It follows from Theorem 2.11 of [9] and Claim 1 in the proof of that
same theorem that $\mathbb{G}$ is idempotent trivial and that the identity is
alone in its connected component of $Hom(\mathbb{G},\mathbb{G})$. We can then
invoke Lemma 3.2 to conclude. ∎

For completeness’ sake, we state an analog of Lemma 3.2 when we only consider
strong components. Write $f\sim g$ to mean that $f$ and $g$ are in the same
strong component of $Hom(\mathbb{G},\mathbb{G})$.

######  Lemma 3.4.

Let $\mathbb{G}$ be a digraph such that the identity is alone in its strong
component of $Hom(\mathbb{G},\mathbb{G})$. If
$f:\mathbb{G}^{n}\rightarrow\mathbb{G}$ is an onto, essentially unary
polymorphism then $f$ is alone in its strong component of
$Hom(\mathbb{G}^{n},\mathbb{G})$.

###### Proof.

It suffices to show the result for projections: indeed, if $f$ is an onto
essentially unary polymorphism of arity $n$ then $f=\sigma\circ\pi$ for some
projection $\pi$ and some automorphism $\sigma$ of $\mathbb{G}$. If $f\sim g$
then $\pi\sim\sigma^{-1}\circ g$ so if the result holds for projections then
$\pi=\sigma^{-1}\circ g$ and $f=g$.

Suppose that $\pi\sim f$ in $Hom(\mathbb{G}^{n},\mathbb{G})$ where $\pi$ is a
projection. Without loss of generality, suppose that $\pi$ is the first
projection. Fix $a_{2},\dots,a_{n}\in G$ and define
$g(x)=f(x,a_{2},\dots,a_{n})$. Then it is easy to see that $id\sim g$ in
$Hom(\mathbb{G},\mathbb{G})$. Thus $g=id$ and hence $f$ is the first
projection.

∎

Now we can state the analog of Lemma 3.2 for strongly connected digraphs: in
this case we can weaken the technical condition on the identity.

######  Lemma 3.5.

Let $\mathbb{G}$ be a strongly connected digraph and let
$f:\mathbb{G}^{n}\rightarrow\mathbb{G}$ be an onto polymorphism of arity at
least 2. If $\mathbb{G}$ is idempotent trivial such that the identity is alone
in its strong component of $Hom(\mathbb{G},\mathbb{G})$, then (1) implies (2):

  1. (1)

there exists an embedding $e:\mathbb{G}\hookrightarrow\mathbb{G}^{n}$ such
that the restriction of $f$ to $e(\mathbb{G})$ is onto;

  2. (2)

$f$ is essentially unary.

###### Proof.

The proof is exactly the same as for Lemma 3.2, except for two observations:
(i) we replace the use of Lemma 3.1 by that of Lemma 3.4 and (ii) since
$\mathbb{G}$ is strongly connected, so is the image of the homomorphism
$\psi$; since its image contains a surjective essentially unary polymorphism,
this image must be constant by (i). ∎

We close this section with some observations on the conditions used in the
previous lemmas. The technical condition that the identity should be an
isolated loop is slightly vexing; it can be removed in many instances, but
unfortunately not always.

We say the digraph $\mathbb{G}$ is intransitive if its simplices all have
dimension at most 1, i.e. there are no transitive triples in $\mathbb{G}$.

######  Lemma 3.6.

Let $\mathbb{G}$ be a poset or symmetric digraph or intransitive digraph. If
$\mathbb{G}$ is idempotent trivial then the identity is isolated in
$Hom(\mathbb{G},\mathbb{G})$.

As we argued earlier, we can assume that $\mathbb{G}$ is connected if it is
idempotent trivial.

###### Proof.

(1) Suppose $\mathbb{G}$ is a poset, and $id$ is not alone in its connected
component. Then (see the comment following Lemma 2.10 in [15]) without loss of
generality $id<f$ where $f$ differs from $id$ only in one place, say $f(a)=b$;
it is easy to see that in this case $b$ is a unique upper cover of $a$ in
$\mathbb{G}$ (i.e. if $a<c$ then $b\leq c$); then define $\phi(x,y)=y$ if
$x\leq a$ and $\phi(x,y)=f(y)$ otherwise. It is easy to see that $\phi$ is an
idempotent polymorphism, and that it is not a projection.

(2) Suppose that $\mathbb{G}$ is a symmetric digraph, and that $id$ is not
alone in its component, so without loss of generality let $id\rightarrow f$.
By Lemma 2.2 of [15], we can assume that $f$ has at least one fixed point.
Then define $\phi(x,y)=f(y)$ if $x=a$ and $\phi(x,y)=y$ otherwise. It is easy
to see that $\phi$ is an idempotent polymorphism and that it is not a
projection.

(3) Suppose that $\mathbb{G}$ is an intransitive digraph. Suppose that the
identity is not alone in its component, so without loss of generality let
$f\rightarrow id$. Let $x,y\in G$ be distinct such that $x\rightarrow y$. Then
$\\{f(x),x,y\\}$ is a simplex, and hence $f(x)\in\\{x,y\\}$. Similarly,
$\\{f(x),f(y),y\\}$ is a simplex. We want to show that
$(f(x),f(y))\in\\{(x,y),(y,x)\\}$, and that $(f(x),f(y))=(x,y)$ in the case
the edge is non-symmetric.

Case 1. Suppose that $\\{x,y\\}$ is not a symmetric edge. Then $f(x)=x$ and
$f(y)\in\\{x,y\\}$. If $f(y)=y$ we are done; otherwise $f(y)=x$; we show that
$y$ has a unique in-neighbour (namely $x$) and no out-neighbour. First suppose
$y\rightarrow w$. Then $x=f(y)\rightarrow w$ means that $\\{x,y,w\\}$ is
transitive so $y=w$. Now suppose that $z\rightarrow y$. We now know this edge
in non-symmetric, so by our first observation $f(z)=z$. Then
$z=f(z)\rightarrow f(y)=x$ implies that $\\{z,x,y\\}$ is a transitive triple,
and hence $z\in\\{x,y\\}$.

Define a map $\phi:G^{2}\rightarrow G$ by

$\phi(u,v)=\begin{cases}x,&\text{if }v=y\text{ and }u\neq y,\\\
v,&\text{otherwise.}\end{cases}$

It is straightforward to verify that $\phi$ is an idempotent polymorphism of
$\mathbb{G}$ and is not a projection, contradicting our hypothesis. Hence
$f(x)=x$ and $f(y)=y$ if the edge is non-symmetric.

Case 2. Now assume the edge is symmetric and that $f(x)=x$. One can argue as
above that if $f(y)\neq y$ then $y$ is a pendant vertex (with symmetric edge),
and mimicking Case 1, we can define a binary idempotent polymorphism which is
not a projection. We conclude that $f(y)=y$. Now if $f(x)=y$, by our previous
argument (exchanging the roles of $x$ and $y$) we must have $f(y)\neq y$ and
hence $f(y)=x$.

So we conclude that for every non-symmetric edge $x\rightarrow y$ we have
$f(x)=x$ and $f(y)=y$, and for a symmetric edge $(x,y)$ we have $f(x)=x$ and
$f(y)=y$ or $f(x)=y$ and $f(y)=x$. However, suppose that $(x,y)$ is such a
flipped edge. Then it is easy to see that neither $x$ nor $y$ can have any
other neighbour (symmetric or not), so $\mathbb{G}$ is an edge. Since the edge
admits all polymorphisms it is not idempotent trivial. Consequently, $f$ fixes
all vertices that are incident to some arc, and hence the identity is alone in
its connected component.

∎

A pre-order is a reflexive, antisymmetric relation. If $A$ and $B$ are strong
components of the digraph $\mathbb{G}$, define $A\sqsubseteq B$ if there exist
$a\in A$ and $b\in B$ such that $a\rightarrow b$. It is immediate that this
defines a pre-order on the set of strong components of $\mathbb{G}$. An
element $a$ of a pre-order $\mathbb{K}$ is minimal if $b\rightarrow a$ implies
$a=b$ for all $b\in K$; maximal elements are defined dually.

######  Lemma 3.7.

Let $\mathbb{G}$ be a Słupecki digraph which is not strongly connected. Then
the identity is alone in its connected component of
$Hom(\mathbb{G},\mathbb{G})$.

###### Proof.

Suppose that $id\rightarrow r$ where $r\neq id$ (the case $r\rightarrow id$ is
identical.) Since $\mathbb{G}$ is not strongly connected, its strong
components form a pre-order. Choose a strong component $A$ which is minimal in
the pre-order, and define a binary polymorphism $f$ as follows: $f(x,y)=y$ if
$x\in A$ and $f(x,y)=r(y)$ otherwise. It is obviously onto, and it is easy to
verify that it is a polymorphism. Let $a\in A$, $b\not\in A$ and let $z\neq
r(z)$. Then $f(a,z)=z$ and $f(b,z)=r(z)$ so $f$ depends on its first variable.
And since $f(a,y)=y$ for all $y$ $f$ depends on its second variable. ∎

One may ask whether the conditions above can be relaxed. The following example
shows that the Słupecki condition does not imply the identity is alone in its
connected component.

######  Lemma 3.8.

There exists a reflexive digraph $\mathbb{G}$ with the following properties:

  * •

$\mathbb{G}$ is Słupecki;

  * •

$\mathbb{G}$ is strongly connected;

  * •

there are arcs $s\rightarrow id\rightarrow r$ in $Hom(\mathbb{G},\mathbb{G})$
such that $r$ and $s$ are retractions onto the same subdigraph of size
$|G|-1$;

  * •

the connected component of the identity is exactly $\\{id,r,s\\}$, in
particular, the identity is alone in its strong component.

Figure 2. A Słupecki digraph where the identity is not isolated.

###### Proof.

Let $\mathbb{G}$ be the reflexive digraph with vertices $\\{0,1,2,3\\}$ and
arcs (other than loops) $\\{(0,1),(1,2),(2,3),(3,0),(3,1)\\}$. It is easy to
verify that there are two retractions of $\mathbb{G}$ onto the subdigraph
$\mathbb{H}$ induced by $H=\\{1,2,3\\}$, one sending 0 to 1 (call it $r$) the
other sending 0 to 3 (call it $s$); we have that $s\rightarrow id\rightarrow
r$, and no other arcs between these homomorphisms.

Now we show that $\mathbb{G}$ is Słupecki; let
$f:\mathbb{G}^{n}\rightarrow\mathbb{G}$ be an $n$-ary, surjective
polymorphism, where $n\geq 2$. Let $\Delta$ denote the diagonal of
$\mathbb{G}^{n}$. It is immediate that the only strongly connected subdigraphs
of $\mathbb{G}$ are singletons, $\mathbb{H}$ and $\mathbb{G}$. Notice that
$\mathbb{H}$ is a directed cycle and hence is Słupecki by Proposition 4.5.

Claim 1. $f(\Delta)$ contains $H$.

Indeed, since $\Delta$ is strongly connected, so is its image under $f$. By
the last remark, it thus suffices to prove that $f$ is not constant on
$\Delta$; suppose for a contradiction that $f(\Delta)=\\{a\\}$. If
$u\rightarrow v$ in $\mathbb{G}$, then
$(u,\dots,u)\rightarrow\overline{x}\rightarrow(v,\dots,v)$ for all
$\overline{x}\in\\{u,v\\}^{n}$; applying $f$, and since $\mathbb{G}$ contains
no symmetric edges, we conclude that $f(\overline{x})=a$. If
$\overline{x}\in\\{0,2\\}^{n}$, notice that
$\overline{a}\rightarrow\overline{x}\rightarrow\overline{b}$ where
$\overline{a}$ is obtained from $\overline{x}$ by replacing all 2’s by 1’s and
$\overline{b}$ is obtained from $\overline{x}$ by replacing all 0’s by 1’s;
applying $f$ we obtain again that $f(\overline{x})=a$. Hence $f$ has value $a$
on any tuple with at most two distinct coordinates. Now if $u\rightarrow
v\rightarrow w$ in $\mathbb{G}$, we have that
$\overline{a}\rightarrow\overline{x}\rightarrow\overline{b}$ where
$\overline{a}$ is obtained from $\overline{x}$ by replacing all v’s by u’s and
$\overline{b}$ is obtained from $\overline{x}$ by replacing all v’s by w’s,
and this for all $\overline{x}\in\\{u,v,w\\}^{n}$. Since every 3-element
subset of $G$ has this form, we conclude, as before, that $f$ has value $a$ on
any tuple with at most three distinct coordinates. It is easy to see that an
analogous argument will show that $f$ must also have value $a$ on all tuples
with 4 distinct coordinates, a contradiction since $f$ is onto.

Claim 2. Let $\Delta^{\prime}=\Delta\cap H^{n}$. Then $f(\Delta^{\prime})=H$.

By Claim 1, we certainly have that $|f(\Delta^{\prime})|\geq 2$ and so it is
not a singleton; since $\Delta^{\prime}$ is strongly connected, so is
$f(\Delta^{\prime})$ and thus it must contain $H$ and we are done.

Claim 3. $f(H^{n})=H$.

Otherwise, by Claim 2, we have some $\overline{x}\in H^{n}$ such that
$f(\overline{x})=0$. Let $\overline{y}\in H^{n}$ such that $f(\overline{y})=1$
(it exists by Claim 2). Now clearly we have the following: for any
$u,w\in\mathbb{H}$ there exists $v\in\mathbb{H}$ such that $u\rightarrow
v\rightarrow w$, and hence the same property holds in $\mathbb{H}^{n}$. Then
there exists $v$ such that $\overline{y}\rightarrow v\rightarrow\overline{x}$;
but then $1\rightarrow f(v)\rightarrow 0$, a contradiction.

By Claim 3, and since $\mathbb{H}$ is Słupecki, we conclude that there exists
an automorphism $g:\mathbb{H}\rightarrow\mathbb{H}$, such that, without loss
of generality, $f(x_{1},\dots,x_{n})=g(x_{1})$ for all $x_{i}\in H$.

Claim 4. Let $\overline{x}$ be a tuple such that $x_{1}\neq 0$. Then
$f(\overline{x})=g(x_{1})$.

We have $\overline{a}\rightarrow\overline{x}\rightarrow\overline{b}$ where
$\overline{a}$ is obtained from $\overline{x}$ by replacing all 0’s by 3’s and
$\overline{b}$ is obtained from $\overline{x}$ by replacing all 0’s by 1’s;
applying $f$ we obtain that
$f(\overline{x})=f(\overline{a})=f(\overline{b})=g(x_{1})$ (since $\mathbb{G}$
has no symmetric edges).

Now take any $\overline{x}\in\\{0\\}\times\mathbb{G}^{n-1}$; then
$\overline{a}\rightarrow\overline{x}\rightarrow\overline{b}$ where
$\overline{a}$ is obtained from $\overline{x}$ by replacing the first
coordinate by 3 and $\overline{b}$ is obtained from $\overline{x}$ by
replacing the first coordinate by 1; applying $f$ we obtain using Claim 4 that
$g(3)\rightarrow f(\overline{x})\rightarrow g(1)$. It follows that there
exists a value $a\in\mathbb{H}$ such that $f(\overline{x})=a$ for all
$\overline{x}\in\\{0\\}\times\mathbb{G}^{n-1}$ (this value $a$ depends on the
automorphism $g$). In particular, the image under $f$ of the strongly
connected digraph $\\{0\\}\times\mathbb{G}^{n-1}$ must be a singleton, and
thus $f$ depends only on its first variable.

Finally we show that the component of the identity is $\\{id,r,s\\}$. Consider
the maps from $Hom(\mathbb{G},\mathbb{G})$ to $Hom(\mathbb{H},\mathbb{H})$
sending $f$ to $(r\circ f)|_{\mathbb{H}}$ and $(s\circ f)|_{\mathbb{H}}$
respectively. These are clearly homomorphisms, and thus must map the entire
component of $id_{\mathbb{G}}$ to the component of $id_{\mathbb{H}}$ which by
Lemma 3.7 is $\\{id_{\mathbb{H}}\\}$. A simple verification shows that this
forces any member $f$ of the component of $id_{\mathbb{G}}$ to be the identity
when restricted to $\mathbb{H}$, which forces $f\in\\{id,r,s\\}$.

∎

##  4\. Some Słupecki Spheres

As we remarked earlier, digraphs that triangulate spheres are known to be
idempotent trivial, and cycles of girth at least 4 are in fact Słupecki. In
the next section we will provide examples of digraphs that triangulate
2-spheres that are not Słupecki; in the present section we provide examples of
digraphs triangulating spheres that are Słupecki, using a technique involving
gadgets. We also state for the record the result that digraphs that
triangulate 1-spheres are Słupecki.

An $n$-ary operation $f$ on a set $A$ preserves the $k$-ary relation
$\theta\subseteq A^{k}$ if applying $f$ to the rows of any $k\times n$ matrix
whose columns are tuples in $\theta$ yields a tuple in $\theta$.

######  Lemma 4.1 ([14]).

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$.

The set of operations preserving the above relation $\theta$ is called the
Słupecki clone; it is known to be a maximal clone, and it is easy to see that
it contains all non-surjective operations and all unary operations. To show
that a reflexive digraph is Słupecki, it is necessary and sufficient to prove
that its polymorphisms preserve the relation $\theta$; it is well-known (see
[14]) that this is equivalent to showing that there exists a primitive,
positive definition of $\theta$ in terms of the edge relation of the digraph.
Or in more convenient terms for our purposes:

######  Lemma 4.2.

The digraph $\mathbb{G}$ is Słupecki if and only if there exists a digraph
$\mathbb{K}$ and vertices $x_{1},\dots,x_{n}$ of $\mathbb{K}$ such that

$\theta=\\{(f(x_{1}),\dots,f(x_{n})):f:\mathbb{K}\rightarrow\mathbb{G}\\}.$

If the above holds we say that the gadget $\mathbb{K}$ pp-defines the Słupecki
relation $\theta$. It turns out that finding the gadget $\mathbb{K}$ is fairly
easy for various families of cycles (see below), but we do not know of a
uniform gadget construction for all cycles.

######  Definition 4.3.

Let $\mathbb{G}$ be a digraph, and let $S\subseteq G$. If there exists a
digraph $\mathbb{K}$, vertices $x_{1},\dots,x_{k},u\in K$ and a partial map
$f:\\{x_{1},\dots,x_{k}\\}\rightarrow G$ such that
$S=\\{g(u):g:\mathbb{K}\rightarrow\mathbb{G},\,g(x_{i})=f(x_{i})\,\text{ for
all }i\\}$ then we say $S$ is pp-defined by $(\mathbb{K},f,u)$.

######  Theorem 4.4.

Let $\mathbb{G}$ be a digraph. If there exists a digraph $\mathbb{K}$ with
vertices $x_{1},\dots,x_{k},u$ such that the conditions below hold, then
$\mathbb{G}$ is Słupecki.

  1. (1)

for all $a\in G$, there exists some $f_{a}$ such that $(\mathbb{K},f_{a},u)$
pp-defines $G\setminus\\{a\\}$;

  2. (2)

for all $f$, the set pp-defined by $(\mathbb{K},f,u)$ is a proper subset of
$G$.

Figure 3. A gadget $\mathbb{L}$ with $n=3$ and $k=2$.

###### Proof.

Let $n=|G|$. Glue $n$ distinct copies of $\mathbb{K}$ by identifying their
vertices $x_{1},\dots,x_{k}$; rename their respective vertices $u$ as
$u_{1},\dots,u_{n}$. We claim that this structure $\mathbb{L}$ pp-defines the
Słupecki relation $\theta$. Indeed, let $g:\mathbb{L}\rightarrow\mathbb{G}$;
by the second property, we know that the values of $g$ on $u_{1},\dots,u_{n}$
can never be all distinct; and when the restriction of $g$ to
$x_{1},\dots,x_{n}$ is equal to $f_{a}$, then we will obtain all $n$-tuples
that miss the value $a$. ∎

Notice that if $k=1$, condition (2) of Theorem 4.4 is implied by condition
(1).

######  Proposition 4.5.

[[4]] A directed cycle of girth at least 3 is Słupecki.

###### Proof.

We invoke Theorem 4.4. Let $m$ be the girth of $\mathbb{G}$. The gadget
$\mathbb{K}$ consists of a directed path of length $m-2$, with starting point
$x_{1}=x$ and end point $u$. Notice that the only vertex not reachable from
$i+1$ in $\mathbb{G}$ by a directed path of length $m-2$ is $i$, hence
$(\mathbb{K},f,u)$ pp-defines $G\setminus\\{i\\}$ when $f(x)=i+1$. ∎

######  Proposition 4.6.

A symmetric even cycle of girth at least 4 is Słupecki.

###### Proof.

Let $\mathbb{G}$ be the cycle of girth $n=2m$; we invoke Theorem 4.4: the
gadget $\mathbb{K}$ consists of a path of length $m-1$ with starting point
$x_{1}=x$ and endpoint $u$. Notice that the only vertex not reachable from $a$
in $\mathbb{G}$ by a path of length $m-1$ is its antipode $b$; hence
$(\mathbb{K},f,u)$ pp-defines $G\setminus\\{b\\}$ when $f(x)=a$. ∎

######  Definition 4.7.

Let $m\geq 2$. The $2m$-crown is the reflexive digraph on
$\\{0,1,\dots,2m-1\\}$ with arcs $(2i,2i\pm 1)$, $0\leq i\leq m-1$ (modulo
$2m$).

Figure 4. The 6-crown. Arcs are all oriented bottom to top.

######  Proposition 4.8 ([3]).

Every crown is Słupecki.

Figure 5. The gadget for the 6-crown.

###### Proof.

We invoke Theorem 4.4: the gadget $\mathbb{K}$ consists of two paths
$\mathbb{P}$ and $\mathbb{Q}$ glued at their start point (call this $x_{1}=x$)
and also glued at their end point, call that one $u$: $\mathbb{P}$ is an
alternating sequence of forward and backward edges of length $m$, and
$\mathbb{Q}$ is an alternating sequence of the same length but opposite
orientations. We claim that if we set $f(x)=a$, then $(\mathbb{K},f,u)$ pp-
defines $G\setminus\\{a+m\\}$. Indeed, by symmetry of $\mathbb{K}$ and
$\mathbb{G}$ we may assume without loss of generality that $a=0$; then using
the path $\mathbb{Q}$, we can reach all vertices of $\mathbb{G}$ except $m$
(because in the first step the backward edge forces the value to remain 0, and
this leaves a path of length $m-1$ so we cannot reach $m$). Notice that for
$a=0$, using the path $\mathbb{P}$ we can reach all vertices. This proves our
claim. ∎

Here is a rather ad hoc example.

######  Proposition 4.9.

Let $\mathbb{G}$ be the 4-cycle with the following edge structure:
$E(\mathbb{G})=\\{(0,1),(1,2),(2,1),(2,3),(3,0),(0,3)\\}$. Then $\mathbb{G}$
is Słupecki.

Figure 6. An ad hoc example of a 4-cycle.

###### Proof.

Let $\mathbb{K}$ be a directed 4-cycle; choose some vertex $x_{1}=x$ and let
$u$ be its antipode. Suppose that $f(x)=1$; then it is easy to see that
$f(u)\in\\{1,2,3\\}$. By symmetry of $\mathbb{G}$, if $f(x)=3$ then
$(\mathbb{K},f,u)$ pp-defines $\\{0,1,3\\}$. Finally, if we reverse all arcs,
the same argument shows that $(\mathbb{K},f,u)$ pp-defines the other two
3-element subsets for some choice of $f$. We can now apply Theorem 4.4.

∎

######  Lemma 4.10.

A digraph $\mathbb{G}$ triangulates a 1-sphere if and only if $\mathbb{G}$ is
a directed 3-cycle or a cycle of girth at least 4.

###### Proof.

Let $\mathbb{G}$ triangulate a 1-sphere. Then $\mathbb{G}_{Sym}$ is connected,
has no pendant vertex, and it has Euler characteristic 0, i.e. the number of
vertices is equal to the number of edges, and thus every vertex has degree
exactly 2. Hence $\mathbb{G}$ is a cycle. Furthermore, there cannot be any
simplex of size 3, thus if it is a 3-cycle then it is the directed 3-cycle.
Consequently, the digraphs that triangulate a 1-sphere are precisely the
directed 3-cycle and the cycles of girth at least 4. ∎

######  Theorem 4.11.

If $\mathbb{G}$ triangulates a 1-sphere, then $\mathbb{G}$ is Słupecki.

###### Proof.

This follows from the previous lemma, Proposition 4.5 and the main result of
[6]. ∎

######  Proposition 4.12.

Let $n\geq 2$. Let $\mathbb{G}_{n}$ be obtained from the complete graph on
$2n$ vertices by removing the edges $\\{i,i+n\\}$ for all $0\leq i\leq n-1$.
Then

  1. (1)

$\mathbb{G}_{n}$ triangulates $\mathbb{S}^{n-1}$;

  2. (2)

$\mathbb{G}_{n}$ is Słupecki.

###### Proof.

(1) Notice that $\mathbb{G}_{2}$ is a 4-cycle and thus triangulates
$\mathbb{S}^{1}$; and it is easy to see that $\mathbb{G}_{n}$ is the
suspension of $\mathbb{G}_{n-1}$. (2) We invoke Theorem 4.4: we use as gadget
$\mathbb{K}$ a symmetric edge with vertices $x$ and $u$. Once having chosen
the image of $x$, the only vertex not in its reach is its antipode.

∎

######  Proposition 4.13.

Let $n\geq 3$. Let $\mathbb{H}_{n}$ be obtained from the complete graph on $n$
vertices by removing the directed cycle $(0,1),\dots,(n-1,0)$. Then

  1. (1)

$\mathbb{H}_{n}$ triangulates $\mathbb{S}^{n-2}$;

  2. (2)

$\mathbb{H}_{n}$ is Słupecki.

###### Proof.

(1) It is easy to see that the simplicial complex of $\mathbb{H}_{n}$ is a
truncated boolean lattice of height $n-2$. (2) To show that $\mathbb{H}_{n}$
is Słupecki, we let the gadget $\mathbb{K}$ be a directed edge from $x$ to
$u$. Again, once chosen the value for $f(x)=i$, by the construction of our
graph, the only non-reachable vertex is $i+1$ (mod n). We conclude by using
Theorem 4.4.

∎

##  5\. Ordinal sums

In this section we investigate the nature of surjective polymorphisms on
posets of the form $m\oplus n$ and $m\oplus n\oplus k$ with $m,n,k\geq 2$.
These posets are known to be idempotent trivial [8], and, hence, by Lemma 3.6,
the identity is an isolated loop in $Hom(\mathbb{P},\mathbb{P})$. These rather
simple-looking posets will provide many examples of unexpected behaviour.
Namely, although $m\oplus n$ is Słupecki, none of the posets $n\oplus m\oplus
k$ are; this includes the poset $2\oplus 2\oplus 2$ which is the poset
suspension of a 4-cycle and hence triangulates a 2-sphere. When considering
homomorphisms between posets we often use the term monotone instead.

######  Theorem 5.1.

Let $m,n\geq 2$. Then $\mathbb{P}=m\oplus n$ is Słupecki.

Figure 7. The poset $3\oplus 4$. Arcs are all oriented bottom to top.

###### Proof.

We are going to use Lemma 3.2 in the $(1)\Rightarrow(2)$ direction. We have
just observed that the two technical conditions, namely that $\mathbb{P}$ is
idempotent trivial and the identity is isolated, are fulfilled. Let
$f:\mathbb{P}^{s}\rightarrow\mathbb{P}$ ($s\geq 2$) be an onto polymorphism.
Finding the embedding $e$ of Lemma 3.2 means finding an isomorphic copy of
$\mathbb{P}$ in $\mathbb{P}^{s}$ on which $f$ is onto. That is what we are
going to do.

Let $A$ and $B$ denote the set of minimal and maximal elements of
$\mathbb{P}$, respectively. We claim $f(A^{s})\supseteq A$. Pick $a\in A$,
then $f(x)=a$ for some $x\in\mathbb{P}^{s}$, and, under $x$, there is a
minimal element $y$ of $\mathbb{P}^{s}$ for which $f(y)=a$, and, from
minimality, we have $y\in A^{s}$. Dually, $f(B^{s})\supseteq B$. Now we can
choose two sets of elements $X_{A}\subseteq A^{s}$ and $X_{B}\subseteq B^{s}$
such that

$|X_{A}|=|A|,\;|X_{B}|=|B|,\;f(X_{A})=A,\text{ and }f(X_{B})=B.$

As the elements of $A^{s}$ and $B^{s}$ form two antichains such that the
elements of $A^{s}$ are all under those of $B^{s}$, the poset $X_{A}\cup
X_{B}$ is in fact an isomorphic copy of $\mathbb{P}$ in $\mathbb{P}^{s}$ on
which $f$ is onto. We are done. ∎

The case of ordinal sums of three antichains is more interesting. First some
notation. Once $m,n,k\geq 2$ are fixed, we let $A=\\{a_{0},\dots,a_{m-1}\\}$,
$B=\\{b_{0},\dots,b_{n-1}\\}$ and $C=\\{c_{0},\dots,c_{k-1}\\}$ denote the
minimal, middle and maximal elements of $\mathbb{P}=m\oplus n\oplus k$
respectively.

We first show that $m\oplus n\oplus k$ is not 3-Słupecki (and hence not
Słupecki) by directly exhibiting a not essentially-unary ternary polymorphism.

######  Theorem 5.2.

Let $m,n,k\geq 2$. Then $\mathbb{P}=m\oplus n\oplus k$ is not 3-Słupecki, and,
hence, not Słupecki.

###### Proof.

We exhibit a polymorphism $f:\mathbb{P}^{3}\to\mathbb{P}$ that is onto and not
essentially unary: let

$f(x,y,z)=\begin{cases}s,&\text{if }(x,y,z)=(s,s,s),\;\;\text{for }s\in A\cup
C\\\ b_{i},&\text{if }(x,y,z)=(a_{0},c_{0},b_{i}),\;\;(i=0,\dots,n-1)\\\
a_{0},&\text{if }(x,y,z)<(a_{0},c_{0},b_{i}),\;\;(i=0,\dots,n-1)\\\
c_{0},&\text{if }(x,y,z)>(a_{0},c_{0},b_{i}),\;\;(i=0,\dots,n-1)\\\
b_{0},&\text{otherwise.}\end{cases}$

First, we have to verify that our function is well-defined. There are, indeed,
elements of $P^{3}$ that are given values multiple times in the definition; we
need to make sure that they are given the same value. It is clear that this
occurs for $(a_{0},a_{0},a_{0})$ and $(c_{0},c_{0},c_{0})$ which are given the
values $a_{0}$ and $c_{0}$ respectively, at each of their occurrences in the
definition, hence there is no conflict here. Let $x^{\uparrow}=\\{y:x\leq
y\\}$ and similarly $x_{\downarrow}=\\{y:x\geq y\\}$. The only other way this
multiple assignment phenomenon can happen for $(x,y,z)\in P^{3}$ is if it
belongs to $(a_{0},c_{0},b_{i})^{\uparrow}\cap(a_{0},c_{0},b_{j})^{\uparrow}$
(or its dual) for $i\neq j$. On those intersections, we define our function to
be $c_{0}$ ($a_{0}$ on its dual), hence this causes no conflict either, our
function is well-defined.
It is clear that $f$ is onto.
Let’s show that $f$ is not essentially unary. The fact that
$c_{0}=f(a_{0},c_{0},c_{0})\neq f(a_{0},c_{0},a_{0})=a_{0}$ shows that if $f$
depends only on one variable it is the third; if $f$ depended only its third
variable, then its surjectivity would imply that it would be injective on its
third variable, which contradicts the fact that
$f(a_{0},c_{0},a_{0})=f(a_{0},c_{0},a_{1})=a_{0}$.
Finally, the reader can easily verify that $f$ is a polymorphism using that
$f$ is defined using upsets and downsets. ∎

Let us turn our attention to binary polymorphisms. Surprisingly,
2-Słupeckiness of $m\oplus n\oplus k$ depends on $m$, $n$, and $k$: if $n$ is
small enough compared to $m$ and $k$, then $m\oplus n\oplus k$ is not
2-Słupecki, and otherwise, it is. More precisely, the main result of the
section, Theorem 5.5, states that there is a bound $B(m,k)$ for which the
poset $m\oplus n\oplus k$ is 2-Słupecki if and only if $n>B(m,k)+1$.

We start with a standalone, auxiliary result that we will make use of later:

######  Lemma 5.3.

Let $m,n,k\geq 2$, let $\mathbb{P}=m\oplus n\oplus k$ and let
$f:\mathbb{P}^{2}\rightarrow\mathbb{P}$ be a monotone map. Suppose $|B|>2$ and
that $f(B^{2})\subseteq B$ has size at least 2. Then there exist
$b,b^{\prime}\in B$ distinct, $\tau_{i}\in Aut(\mathbb{P})$, $i=0,1$, such
that

  1. (1)

$\tau_{i}(x)=x$ for all $x\in A\cup C$ and all $i=0,1$;

  2. (2)

$(\tau_{0}\circ f\circ\sigma)(s,s)=s$ for $s\in\\{b,b^{\prime}\\}$, where
$\sigma(x,y)=(\tau_{1}(x),y)$.

###### Proof.

Notice that $Aut(\mathbb{P})$ contains every transposition of pairs of
elements in $B$ (which fixes all other elements in $\mathbb{P}$.) We first
prove the result in the case where the restriction of $f$ to the diagonal of
$B^{2}$ has image of size at least 2: if $f(b,b)=u$ and
$f(b^{\prime},b^{\prime})=v$ where $u\neq v$ then choose $\tau_{0}$ to be any
automorphism of $\mathbb{P}$ that sends $u$ to $b$ and $v$ to $b^{\prime}$:
then $(\tau_{0}\circ f)(s,s)=s$ for $s\in\\{b,b^{\prime}\\}$ and we are done.
Otherwise, there exist some $z$ such that $f(t,t)=z$ for all $t\in B$, and
some $u\neq v$ and $w\neq z$ such that $f(u,v)=w$. Let $\tau_{1}\in
Aut(\mathbb{P})$ swap $u$ and $v$. Then $(f\circ\sigma)(t,t)=z$ for any
$t\not\in\\{u,v\\}$ and $(f\circ\sigma)(v,v)=f(\tau_{1}(v),v)=f(u,v)=w$. We
conclude with the preceding argument.

∎

Now we define the bound $B(m,k)$ of Theorem 5.5.

######  Definition 5.4.

Let $m,k\geq 2$ be integers. We let $\mu(m,k)$ denote the maximum of the
function $\alpha\gamma+\beta\delta$ where $\alpha,\beta,\gamma,\delta$ are
integers satisfying $0<\alpha,\beta<m$, $0<\gamma,\delta<k$,
$(m-\alpha)(m-\beta)\geq m-1$ and $(k-\gamma)(k-\delta)\geq k-1$. Let
$B(m,k)=\max(\mu(m,k),mk)$.

From the definition and the individual bounds for $\alpha,\beta,\gamma$ and
$\delta$, one sees easily that $mk\leq B(m,k)<2mk$ and in particular that the
function is well-defined; notice also that $B(m,k)\geq 4$ for all $m,k\geq 2$.
We have verified numerically that $B(m,k)=mk$ if $m,k\leq 11$. On the other
hand, $B(12,12)=145$ as shown by the choice $\alpha=\gamma=9$, and
$\beta=\delta=8$, and $B(10,13)=134$.

######  Theorem 5.5.

The poset $m\oplus n\oplus k$ is 2-Słupecki if and only if $n>B(m,k)+1$.

We split the proof into two separate lemmas (Lemma 5.7 and Lemma 5.8)
according to the two directions of the statement.

######  Definition 5.6.

Given any map $f:A^{2}\cup C^{2}\rightarrow A\cup C$ such that
$f(A^{2})\subseteq A$ and $f(C^{2})\subseteq C$, for $T\in\\{A,C\\}$, let
$l(T)$ denote the set of all $s\in T$ such that the map $x\mapsto f(s,x)$ is
constant, and let $l(s)$ denote the value of this map. Similarly let $r(T)$
denote the set of all $t\in T$ such that the map $x\mapsto f(x,t)$ is
constant, and let $r(t)$ denote the value of this map.

First, we take on the only if direction. We actually formulate its
contrapositive:

######  Lemma 5.7.

If $n\leq B(m,k)+1$, then $m\oplus n\oplus k$ is not 2-Słupecki.

###### Proof.

With $\mathbb{P}=m\oplus n\oplus k$, we will exhibit an essentially binary
polymorphism $f:\mathbb{P}^{2}\to\mathbb{P}$. To do so, we start by defining
$f$ partially on $A^{2}$ and $C^{2}$. Let us denote the corresponding
restrictions by $f_{A}$ and $f_{C}$.

Claim 0. There exist onto maps $f_{A}:A^{2}\rightarrow A$ and
$f_{C}:C^{2}\rightarrow C$ such that there are exactly $B(m,k)$ pairs
$(s,t)\in A\times C\cup C\times A$ where both the maps $x\mapsto f(x,t)$ and
$x\mapsto f(s,x)$ are constant, where, for convenience, $f$ stands for the
corresponding $f_{A}$ or $f_{C}$.

Proof of Claim 0. If $B(m,k)=mk$, then we define $f$ to be the first
projection on $A$ and the second projection on $C$. Clearly there are exactly
$B(m,k)=mk$ pairs $(s,t)\in A\times C$ (and none in $C\times A$) such that
both the maps $x\mapsto f(x,t)$ and $x\mapsto f(s,x)$ are constant. Otherwise,
$B(m,k)=\alpha\gamma+\beta\delta$ with $0<\alpha,\beta<m$,
$0<\gamma,\delta<k$. By definition of $B(m,k)$ there exists a map $g$ from
$\\{a_{\alpha},\dots,a_{m-1}\\}\times\\{a_{\beta},\dots,a_{m-1}\\}$ onto
$\\{a_{1},\dots,a_{m-1}\\}$. Then define

$f(a_{i},a_{j})=\begin{cases}a_{0}&\mbox{ if $i<\alpha$ or $j<\beta$},\\\
g(a_{i},a_{j})&\mbox{ otherwise.}\end{cases}$

$f$ | $a_{0}$ | $\cdots$ | $a_{\beta-1}$ | $a_{\beta}$ | $\cdots$ | $a_{m-1}$
---|---|---|---|---|---|---
$a_{0}$ |  |  |  |  |  |
$\vdots$ |  | $a_{0}$ |  |  | $a_{0}$ |
$a_{\alpha-1}$ |  |  |  |  |  |
$a_{\alpha}$ |  |  |  |  | $g$ |
$\vdots$ |  | $a_{0}$ |  |  | with image |
$a_{m-1}$ |  |  |  |  | $\\{a_{1},\dots,a_{m-1}\\}$ |
Figure 8. The “multiplication table” for $f$.

By definition of $f$ there are exactly $\alpha$ values $a\in A$ such that the
map $x\mapsto f(a,x)$ is constant, and $\beta$ values $a\in A$ such that the
map $x\mapsto f(x,a)$ is constant. Similarly, we can define $f$ on $C^{2}$ to
be onto $C$ and such that there are exactly $\gamma$ values $c\in C$ such that
the map $x\mapsto f(x,c)$ is constant and $\delta$ values of $c\in C$ such
that the map $x\mapsto f(c,x)$ is constant. In particular, this shows that
there are exactly $B(m,k)$ pairs $(s,t)\in(A\times C)\cup(C\times A)$ such
that both the map $x\mapsto f(x,t)$ and $x\mapsto f(s,x)$ are constant.

Now we will extend $f$ to be a fully defined map on $P^{2}$. Let $b_{0}\in B$;
by our hypothesis and Claim 0, there exists a map $h:(l(A)\times
r(C))\cup(l(C)\times r(A))\rightarrow B\setminus\\{b_{0}\\}$ which is onto. We
now define our map $f$ as follows:

$f(x,y)=\begin{cases}f_{A}(x,y)&\mbox{ if $(x,y)\in A^{2}$},\\\
f_{C}(x,y)&\mbox{ if $(x,y)\in C^{2}$},\\\ h(x,y)&\mbox{if
$(x,y)\in(l(A)\times r(C))\cup(l(C)\times r(A))$},\\\ l(x)&\mbox{if $x\in
l(A)$ and $y\in B$},\\\ r(y)&\mbox{if $y\in r(A)$ and $x\in B$},\\\
l(x)&\mbox{if $x\in l(C)$ and $y\in B$},\\\ r(y)&\mbox{if $y\in r(C)$ and
$x\in B$},\\\ b_{0}&\mbox{otherwise.}\par\end{cases}$

Clearly $f$ is onto; and since $B(m,k)\geq 4$ implies $l(A)\times
r(C)\neq\emptyset$, there is some pair $(a,c)\in A\times C$ such that
$f(a,c)\in B$; since $f(a,a)\in A$ and $f(c,c)\in C$, $f$ depends on both
variables. Finally we verify that $f$ is monotone. It suffices to verify that
$f(x,y)\leq f(u,v)$ where $(u,v)$ covers $(x,y)$ in $\mathbb{P}^{2}$; and it
is easy to see that this occurs if and only if $u=x$ and $v$ covers $y$ or
$v=y$ and $u$ covers $x$.

  1. (1)

$(a,a^{\prime})<(a,b)$: if $a\in l(A)$ then $f(a,a^{\prime})=f(a,b)=l(a)$;
otherwise $f(a,a^{\prime})\leq b_{0}=f(a,b)$. The argument for
$(b,a^{\prime})$ is identical.

  2. (2)

$(a,b)<(b^{\prime},b)$: $f(a,b)\in A\cup\\{b_{0}\\}$ and
$f(b^{\prime},b)=b_{0}$. The argument for $(b^{\prime},a)$ is identical.

  3. (3)

$(a,b)<(a,c)$: if $a\not\in l(A)$ then $f(a,b)=f(a,c)=b_{0}$; otherwise
$f(a,b)\in A$ and $f(a,c)\in B$. The argument for $(b,a)<(c,a)$ is identical.

  4. (4)

the remaining cases are dual to the previous ones (replacing $A$ by $C$).

∎

It is time to prove the converse (the if direction of Theorem 5.5).

######  Lemma 5.8.

The poset $\mathbb{P}=m\oplus n\oplus k$ is 2-Słupecki if $n>B(m,k)+1$.

###### Proof.

Suppose that $\mathbb{P}$ admits a binary, not essentially unary onto
polymorphism $f$; we want to show that $n\leq B(m,k)+1$. Without loss of
generality we may assume that $n\geq 3$. Our goal is to obtain from $f$ a
binary, not essentially unary onto polymorphism with a very specific form.

Claim 1. $f(A^{2})\supseteq A$, $f(C^{2})\supseteq C$ and $f(B^{2})\subseteq
B$.

Proof of Claim 1. The first statement is clear: $f$ is onto, and every element
of $\mathbb{P}^{2}$ is above some minimal element which is in $A^{2}$. The
second statement is proved dually. It is then clear that $f(B^{2})\subseteq B$
since an element $(b,b^{\prime})\in B^{2}$ is above every element of $A^{2}$
and below every element of $C^{2}$, so by our first two statements $a\leq
f(b,b^{\prime})\leq c$ for all $a\in A$ and $c\in C$ which shows that
$f(b,b^{\prime})\in B$.

Claim 2. We may assume that $f(C^{2})=C$ and $f(A^{2})=A$.

Proof of Claim 2. Suppose that $f(c_{i},c_{j})=y\not\in C$ for some $i,j$.
Suppose that no other pair is mapped to $y$ by $f$. Then $f(s,t)<y$ for all
$s,t\in A\cup B$. Since $y\not\in C$ this means that $f((A\cup B)^{2})=A$
(using Claim 1). But $A\cup B$ is connected and $A$ is not, so this is
impossible. Thus $f(u,v)=y$ for some $(u,v)\neq(c_{i},c_{j})$. Define a map as
follows:

$g(s,t)=\begin{cases}c_{1}&\mbox{ if $(s,t)=(c_{i},c_{j})$},\\\ f(s,t)&\mbox{
otherwise.}\end{cases}$

It is clear that $g$ is monotone, onto, and since obviously $f<g$ and the
identity is alone in its connected component, we conclude by Lemma 3.1 that
$g$ depends on both variables. The argument for $A$ is identical.

Claim 3. Let $b\in B$. If $b\in f((A\times B)\cup(B\times A))\cup f((C\times
B)\cup(B\times C))$ then $b\in f(B^{2})$.

Proof of Claim 3. Let $(x,y)\in(A\times B)\cup(B\times A)$ with $f(x,y)=b$.
Then $(x,y)$ is comparable to a pair $(u,v)\in B^{2}$ so $f(u,v)=b$ (since
$f(u,v)\in B$). Similarly if $(x,y)\in(C\times B)\cup(B\times C)$.

Claim 4. There exists $(x,y)\in(A\times C)\cup(C\times A)$ such that
$f(x,y)\in B$.

Proof of Claim 4. Otherwise, it follows from Claim 3 that $f(B^{2})=B$. By
Claim 2 we can then find subsets $A^{\prime}\subseteq A$, $B^{\prime}\subseteq
B$ and $C^{\prime}\subseteq C$ of size $m,n,k$ respectively such that
$f(A^{\prime}\cup B^{\prime}\cup C^{\prime})=\mathbb{P}$. But this gives an
embedding $e$ of $\mathbb{P}$ into $\mathbb{P}^{2}$ such that
$f(e(\mathbb{P}))=\mathbb{P}$, contradicting Lemma 3.2.

Claim 5. Let $b_{0}\in f(B^{2})$ and let $(a,c)\in A\times C$.

  1. (1)

If $f(a,c)\in B\setminus\\{b_{0}\\}$, then $(a,c)\in l(A)\times r(C)$;

  2. (2)

If $f(c,a)\in B\setminus\\{b_{0}\\}$, then $(c,a)\in l(C)\times r(A)$.

Proof of Claim 5. We prove (1) (the proof of (2) is identical). Let
$f(b,b^{\prime})=b_{0}$ where $b,b^{\prime},b_{0}\in B$. Then $f(b,c)\geq
f(a,c),f(b,b^{\prime})$ so $f(b,c)\in C$. On the other hand, $f(b,c)\leq
f(x,c)$ for all $x\in C$, thus $c\in r(C)$. We have $f(a,b^{\prime})\leq
f(a,c),f(b,b^{\prime})$ so $f(a,b^{\prime})\in A$. On the other hand,
$f(a,b^{\prime})\geq f(a,x)$ for all $x\in A$, thus $a\in l(A)$.

Claim 6. $|f(B^{2})|=1$.

Proof of Claim 6. We consider two cases. First suppose that the restrictions
$f_{A}$ and $f_{C}$ of $f$ to $A^{2}$ and $C^{2}$ respectively depend on two
different variables, without loss of generality suppose $f_{C}$ depends on its
first variable and $f_{A}$ depends on its second. This precisely means there
exist $a\in A\setminus l(A)$ and $c\in C\setminus r(C)$. Choose any $b\in B$.
Since $f(a,x)\leq f(a,c)\leq f(b,c)\leq f(y,c)$ for all $x\in A$ and all $y\in
C$, we conclude that $f(a,c)$ and $f(b,c)$ must be in $B$ (and equal). Now if
$b^{\prime}\in B$ arbitrary, we have $f(b,b^{\prime})\leq f(b,c)$ and hence
they must also be equal. Hence $f(B^{2})=\\{f(a,c)\\}$.

If the restrictions of $f$ to $A^{2}$ and $C^{2}$ do not depend on different
variables, it implies they are both essentially unary (and depend on the same
variable.) By applying an appropriate $\tau\in Aut(\mathbb{P}^{2})$, we can
then suppose that $f(x,x)=x$ for all $x\in A\cup C$ (notice that Claim 4
guarantees we still obtain an essentially binary operation.) Suppose for a
contradiction that $|f(B^{2})|\geq 2$. By Lemma 5.3, we may assume that
$f(s,s)=s$ for $s\in\\{b_{1},b_{2}\\}$ (again Claim 4 guarantees we may apply
automorphisms and obtain an essentially binary operation). Let $\mathbb{R}$ be
the subposet of $\mathbb{P}$ induced by $A\cup\\{b_{1},b_{2}\\}\cup C$. It is
isomorphic to $m\oplus 2\oplus k$ and thus is idempotent trivial. There is an
obvious retraction $r$ of $\mathbb{P}$ onto $\mathbb{R}$, that fixes $A$ and
$C$ pointwise and sends $B$ onto $\\{b_{1},b_{2}\\}$. Consider the restriction
of $r\circ f$ to $\mathbb{R}^{2}$: it is idempotent and hence a projection. In
particular, for the pair $(x,y)$ from Claim 4, we will have that $(r\circ
f)(x,y)\in\\{x,y\\}$, but since $f(x,y)\in B$, this is a contradiction.

Claim 7. $|(l(A)\times r(C))\cup(l(C)\times r(A))|\leq B(m,k)$.

Proof of Claim 7. Let $M=|(l(A)\times r(C))\cup(l(C)\times r(A))|$. If one of
the values in $\\{|r(A)|,|r(C)|,|l(A)|,|l(C)|\\}$ is equal to 0, then clearly
$M\leq mk\leq B(m,k)$. So we may now assume that all 4 values are non-zero. If
both $|r(A)|$ and $|l(A)|$ are non-zero it means that all the maps $x\mapsto
f(a,x)$ and $x\mapsto f(x,a)$ that are constant must have the same value, i.e.
there exists some $w\in A$ such that $l(a)=r(a^{\prime})=w$ for all $a\in
l(A)$ and all $a^{\prime}\in r(A)$. By Claim 2 it means that the restriction
of $f_{A}$ to $(A-l(A))\times(A-r(A))$ has image $A-\\{w\\}$, and thus
$(m-|l(A)|)(m-|l(B)|)\geq m-1$, and in particular, $|l(A)|,|r(A)|<m$. The same
argument shows that the values $|l(C)|,|r(C)|$ also satisfy the required
inequalities of Definition 5.4, and thus $M\leq\mu(m,k)\leq B(m,k)$.

We can now conclude the proof. Let $f(B^{2})=\\{b_{0}\\}$. By Claims 3, 5 and
6, any $b\in B\setminus\\{b_{0}\\}$ must be in the image of $(l(A)\times
r(C))\cup(l(C)\times r(A))$. Hence by Claim 7 $|B|-1\leq|(l(A)\times
r(C))\cup(l(C)\times r(A))|\leq B(m,k)$ and we are done. ∎

##  6\. Conclusion

We have presented various necessary and sufficient conditions for a reflexive
digraph to be Słupecki. We’ve shown in particular that there exist posets that
triangulate spheres that are idempotent trivial but not 2-Słupecki; and some
idempotent trivial posets that are 2-Słupecki but not 3-Słupecki. Here now are
some related questions:

  1. (1)

Can the condition that the identity is isolated be removed in Lemma 3.2 ?

  2. (2)

If $\mathbb{G}$ is strongly connected and idempotent trivial, is the identity
alone in its strong component ? Notice that if this holds, then combining
Lemmas 3.5 and 3.7 with Lemma 3.2 gives a positive answer to question (1).

  3. (3)

What is the algorithmic complexity of recognising Słupecki (idempotent
trivial) digraphs ?

  4. (4)

An operation $f$ is conservative if
$f(x_{1},\dots,x_{n})\in\\{x_{1},\dots,x_{n}\\}$ for all $x_{i}$. It is known
that a poset of size at least 3 is idempotent trivial if and only if all its
idempotent binary polymorphisms are conservative [7]; hence a poset is
idempotent trivial precisely when all its 2-element subsets are pp-definable
by gadgets. Does this property hold for reflexive digraphs in general ? Also,
although it is not true in general that one can always find gadgets that are
trees, is it possible that an algorithm such as singleton arc-consistency (as
described in [1]) might determine if all 2-element subsets are constructible ?
If so, this might lead to interesting algorithms for recognising idempotent
trivial posets.

  5. (5)

the bound $B(m,k)$ we introduced is intriguing from a combinatorial
standpoint. Investigate.

  6. (6)

Are there posets (or more generally digraphs) that are not Słupecki but
$n$-Słupecki for arbitrary large $n$ ? What is the relationship to the size of
the digraph ?

  7. (7)

The idempotent trivial posets of height 1 are known [2]; they are the height 1
posets that are connected and such that no element has a unique upper nor
unique lower cover. Are they all Słupecki ?

## References

  * [1] Hubie Chen, Victor Dalmau, Berit Grussien.  Arc consistency and friends.  Journal of Logic and Computation, 23 (1), 87–108, 2013.
  * [2] Ernest Corominas.  Sur les ensembles ordonnés projectifs et la propriété du point fixe. C.R. Acad. Sci. Paris, 311, Série I, 199–204, 1990.
  * [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] Isabelle Larivière, Benoît Larose and David E. Pazmiño Pullas.  Surjective Polymorphisms of Directed Reflexive Cycles.  Algebra Universalis 85 (4): 1–28, 2024.
  * [7] Benoit Larose.  Finite projective ordered sets, Order, 8: 33-40, 1991.
  * [8] Benoit Larose.  Minimal Automorphic Posets and the Projection Property  International Journal of Algebra and Computation 5 (1): 65-80, 1995.
  * [9] Benoit Larose.  Taylor operations on finite reflexive structures.  Int. J. Math. Comput. Sci., 1 (1):1–21, 2006.
  * [10] 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.
  * [11] Benoit Larose, Barnaby Martin, Petar Markovic, Daniël Paulusma, Siani Smith, Stanislav Zivný.  QCSP on Reflexive Tournaments. ACM Trans. Comput. Log. 23 (3): 14:1-14:22, 2022.
  * [12] Benoît Larose, Barnaby Martin, Daniël Paulusma:  Surjective H-Colouring over Reflexive Digraphs. ACM Trans. Comput. Theory 11 (1): 3:1-3:21, 2019.
  * [13] Benoit Larose and Claude Tardif.  A discrete homotopy theory for binary reflexive structures.  Adv. Math., 189 (2):268–300, 2004.
  * [14] Dietlinde Lau.  Function algebras on finite sets.  Springer Monographs in Mathematics. Springer-Verlag, Berlin, 2006.
  * [15] Miklós Maróti and László Zádori.  Reflexive digraphs with near unanimity polymorphisms.  Discret. Math., 312 (15):2316–2328, 2012.
  * [16] 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.
  * [17] Maurice Pouzet, Ivo G. Rosenberg, Michael G. Stone.  A projection property. Algebra Universalis 36 (2): 159–184, 1996.


# Optimizing Autonomous Driving for Safety: A Human-Centric Approach with LLM-
Enhanced RLHF

Yuan Sun  WINLAB, Rutgers University Piscataway, NJ,  USA
<EMAIL_ADDRESS>,  Salami Pargoo, Navid  WINLAB, Rutgers University
Piscataway, NJ,  USA<EMAIL_ADDRESS>,  Peter J. Jin  Rutgers
University Piscataway, NJ,  USA<EMAIL_ADDRESS>and  Jorge Ortiz
WINLAB, Rutgers University Piscataway, NJ,  USA<EMAIL_ADDRESS>
###### Abstract.

Reinforcement Learning from Human Feedback (RLHF) is popular in large language
models (LLMs), whereas traditional Reinforcement Learning (RL) often falls
short. Current autonomous driving methods typically utilize either human
feedback in machine learning, including RL, or LLMs. Most feedback guides the
car agent’s learning process (e.g., controlling the car). RLHF is usually
applied in the fine-tuning step, requiring direct human ”preferences,” which
are not commonly used in optimizing autonomous driving models. In this
research, we innovatively combine RLHF and LLMs to enhance autonomous driving
safety. Training a model with human guidance from scratch is inefficient. Our
framework starts with a pre-trained autonomous car agent model and implements
multiple human-controlled agents, such as cars and pedestrians, to simulate
real-life road environments. The autonomous car model is not directly
controlled by humans. We integrate both physical and physiological feedback to
fine-tune the model, optimizing this process using LLMs. This multi-agent
interactive environment ensures safe, realistic interactions before real-world
application. Finally, we will validate our model using data gathered from
real-life testbeds located in New Jersey and New York City.

††copyright: acmlicensed††journalyear:  ††doi: XXXXXXX.XXXXXXX††conference:
Make sure to enter the correct conference title from your rights confirmation
emai; June 03–05, ; Woodstock, NY††isbn:

##  1\. Introduction

Reinforcement Learning (RL) and Large Language Models (LLMs) play a crucial
role in the development of autonomous driving systems. RL, a branch of machine
learning, focuses on enabling agents to make optimal decisions over time by
learning from their mistakes and experiences. Numerous studies have
demonstrated the application of RL in autonomous driving. For instance,
(galias2019simulation, 6) proposed using RL to map sensor observations to
control outputs in simulated environments. Similarly,
(lillicrap2015continuous, 9) explored deep RL for continuous control tasks,
which are applicable to autonomous driving scenarios. Additionally,
(wang2023efficient, 15) introduced ASAP-RL, an efficient RL algorithm that
utilizes motion skills and expert priors to enhance learning efficiency and
driving performance in dense traffic. Moreover, (hoel2018automated, 7)
presented a method for making decisions such as lane changing, accelerating,
and braking on highways, employing Deep Q Networks (DQN) to train their model
and predict optimal actions. Recent research has increasingly incorporated
Large Language Models (LLMs) into autonomous driving systems, leveraging their
capabilities for decision-making, reasoning, and interaction. For instance,
(cui2023drivellm, 2, 5, 10) integrated LLMs to enhance commonsense reasoning
and high-level decision-making. In another study, (duan2024prompting, 4)
utilized LLMs to help autonomous driving models mimic human behavior, thereby
improving end-to-end driving performance. (wang2022adept, 16) employed GPT to
extract crucial information from NHTSA accident reports using a QA approach,
enabling the generation of diverse scene codes for simulation and testing.
Additionally, (tan2023language, 14) demonstrated the use of LLMs as powerful
interpreters that translate user text queries into structured specifications
of map lanes and vehicle locations for traffic simulation scenarios. RLHF is a
fundamental component in the training of Large Language Models (LLMs) and is
regarded as an essential element of the modern LLM training pipeline
(kirk2023understanding, 8, 17, 18). RLHF is particularly well-suited for LLMs
(sun2023reinforcement, 13), as it involves RL agents learning from human
preference feedback. This type of feedback is considered more intuitive for
human users, better aligned with human values, and easier to obtain in various
applications (kirk2023understanding, 8).

However, most of the work applies RLHF to optimize LLMs because the scenarios
in which humans use LLMs are more suitable for tracking human preferences.
This alignment with human values ensures that the models perform more
intuitively in real-world applications. In contrast, for autonomous driving
scenarios, it is impractical for humans to provide preference feedback on a
frame-by-frame basis. Consequently, RLHF is seldom used in autonomous driving
contexts.

In this research, we creatively apply RLHF to autonomous driving by modeling
human preferences through various sensor feedback from our environment. We
incorporate both physical and physiological feedback into the simulation to
optimize the RL training loop for autonomous driving. Additionally, the LLM
agent facilitates interaction within our multi-agent system. We posit that
training autonomous car agents alongside human-driven cars in the simulation
can significantly enhance safety and allow the agents to learn human
preferences concurrently. This approach aligns the autonomous car models more
closely with real-world scenarios, ultimately making the application of
autonomous driving models safer in real-life contexts.

##  2\. Methodology

Figure 1. Overview of our human-centric multi-agent LLM-enhanced RLHF system
framework. During the fine-tuning of an autonomous car model, human agents and
proliferated LLM agents mimicking multiple human behaviors are incorporated
into the environment to align with real-world human preferences.

Our system (figure 2) is designed as a multi-agent framework, centering on
human interaction while incorporating LLM agents and autonomous car agents.
The system includes human drivers, human pedestrians, and an LLM agent that
mimics their behavior to generate training interactions for the car. Humans
control the car using physical controllers such as steering wheels and pedals.
Additionally, they wear various wearable sensors, including VR headsets,
wristbands to collect and monitor physiological signals in real-time, and
smart glasses to track focus. A camera is also set up in the environment to
record human reactions. This collected multimodal data is sent to the
simulation. Before integration, the LLM assists the car agent in understanding
this data and aids the human agent in adapting to the simulation environment.
The autonomous vehicle model learns from human feedback within the RL loop,
with the LLM helping to interpret human data into ”preferences” to optimize
the model in the RL loop.

###  2.1. RLHF

In traditional reinforcement learning, the objective of the agent is to
develop a policy, a function that dictates its actions. This policy is
optimized to maximize rewards provided by a distinct reward function based on
the agent’s performance in a given task (russell2016artificial, 11). However,
defining a reward function that accurately reflects human preferences is
challenging. To address this, RLHF aims to train a ”reward model” directly
from human feedback (ziegler2019fine, 19).

However, in our scenario, it is typically difficult to obtain ”preference”
feedback directly on a frame-by-frame basis. For instance, when training an
autonomous car model using RL, the car might simply reward itself with a
positive score for avoiding collisions. However, the car might execute a rapid
lane change that frightens the user. This type of feedback—reflecting user
comfort and safety preferences—is crucial but challenging to capture.
Additionally, scenarios such as aggressive braking, abrupt acceleration, or
failing to yield to pedestrians can all contribute to negative user
experiences, which are important ”preferences” in the autonomous driving RL
loop.At the same time, human driving behavior provides valuable feedback to
the system, as it reflects real-world driving preferences and responses to
various driving conditions.

In our autonomous driving RLHF framework, the objective
function(stiennon2020learning, 12) is defined as follows:

(1) $\text{objective}(\phi)=\mathbb{E}_{(x,y)\sim
D_{\pi^{RL}_{\phi}}}\left[r_{\theta}(x,y)-\beta\log\left(\frac{\pi^{RL}_{\phi}(y|x)}{\pi^{SFT}(y|x)}\right)\right]$

where ,in our work, $x$ represents the input data from various sensors,
including physical sensors, physiological sensors, and simulation data such as
LiDAR and camera inputs. The output $y$ denotes the actions taken by the
autonomous vehicle. The reward function $r_{\theta}(x,y)$ evaluates the
quality of the action $y$ given the sensor inputs $x$, guided by human
feedback. The term
$\beta\log\left(\frac{\pi^{RL}_{\phi}(y|x)}{\pi^{SFT}(y|x)}\right)$ introduces
a KL divergence penalty to ensure the new policy remains close to the initial
supervised model, balancing learning from new data while retaining useful
information from the initial model.

###  2.2. LLM Integration in Autonomous Driving

The primary functions of the LLM in our work include acting as an agent in the
simulation, facilitating interaction between humans and the simulation system,
and optimizing the RL training loop.

####  2.2.1. LLM Agent in the Simulation

In this section, we emphasize our multi-agent system with two key use cases.
First, the LLM agent can mimic human behavior to interact with the car agent
when a human is not available. Second, when a human is in the loop, the LLM
agent can act as another agent, such as a car or pedestrian, to increase the
system’s complexity. For instance, human feedback differs when there is one
car versus multiple cars on the road. The feedback in such a complex scenario
is more representative of real-life situations.

####  2.2.2. Enhanced Human-Simulation Interaction Based on LLM

When the simulation interacts with the human agent, the LLM can enhance the
interaction. Firstly, when sending data collected from humans to the system,
the LLM can help interpret the data. For example, if a driver is skilled, the
LLM might adjust the simulation weather to foggy conditions. Conversely, if
the driver is less skilled, the LLM can help the user adapt to the environment
before the car agent begins its training.

####  2.2.3. LLM-Enhanced RLHF

In the RLHF loop, ”preferences” are not as straightforward as yes or no
answers. The LLM can translate physical and physiological data into preference
formats, which are then incorporated into the objective function. For example,
if a driver’s heart rate increases significantly during a particular maneuver,
the LLM can interpret this physiological response as a negative preference for
that action. Similarly, if sensor data indicates smooth and confident handling
of the vehicle, this can be translated into a positive preference. By
integrating these nuanced preferences into the RL training loop, the
autonomous driving model can be better aligned with human comfort and safety
standards.

##  3\. hardware setup

Figure 2. Simulation room with VR headset, steering controls, and monitors for
real-time multimodal data collection and autonomous driving optimization.

The sensors utilized in our multi-agent LLM-enhanced RLHF system are
categorized into two primary modalities: vehicle and physiological. The
vehicle sensors, primarily sourced from the CARLA simulator and Logitech
hardware, include acceleration, rotation (gyroscope), speed, brake, steering,
throttle, and reverse, all sampled at approximately 60 Hz. These sensors
capture the dynamic state and control inputs of the autonomous vehicle. The
physiological sensors, provided by Empatica, measure various physiological
signals such as blood volume pulse (64 Hz), heart rate (1 Hz), interbeat
interval (varying), electrodermal activity (4 Hz), wrist acceleration (32 Hz),
and body temperature (4 Hz). Additionally, the gaze modality employs an Adhawk
sensor to track coordinates on the screen at a sampling rate of 125 Hz,
capturing the human agent’s visual focus and attention. These sensors monitor
the human agent’s physical and emotional responses during the simulation.
Except for the monitor, we also have a VR headset to create an immersive
environment. Additionally, a Raspberry Pi camera in the simulation room
observes the human reaction to the simulation. This multi-modal data
integration is crucial for fine-tuning the autonomous driving model, providing
comprehensive feedback to align the model’s performance with human preferences
and ensuring realistic and safe interactions in the simulation environment.

##  4\. Initial Implementation

Our initial implementation demonstrates the integration of the LLM with the
car simulation system using the GPT-4 interface. The LLM agent can imitate
human driving behavior, especially when interacting with a car agent in front.
It also assists the car agent in managing situations such as avoiding
collisions. Additionally, the LLM agent helps human users by instructing them
on how to effectively navigate and use the simulation system.

Figure 3. Example of GPT-4o imitating a human agent in the CARLA simulation.
The LLM agent is attempting to overtake the car in front in a human-like
manner. Figure 4. Example of the LLM agent guiding the autonomous car agent to
reverse away from a collision with a building. Figure 5. Example of the LLM
agent assisting the human agent in using the simulation.

Furthermore, we plan to implement our experiments in our real-life city test
bed, located in Harlem(cosmos-lab, 1), NYC, and New Brunswick(cait-datacity,
3), NJ. The real-life data collected from these locations will be used to test
the robustness of our algorithm. Additionally, we can import real-life data
into the simulation as a cross-validation method. The figure 6 below shows an
example of importing real-life road data from New Brunswick into the CARLA
system.

Figure 6. Example of importing real-life road data from New Brunswick testbed
into the CARLA simulation.

##  5\. Conclusion and Future Work

In this work, we introduce a novel framework that integrates RLHF and LLMs to
optimize autonomous driving models. We define human preferences within the
RLHF framework and build a simulation-to-reality system based on this concept.
Our method simulates a multi-agent environment for training the car agent,
allowing it to learn human behaviors through multimodal sensory data. The LLM
agent can proliferate multiple human agents by mimicking human behavior and
facilitating interactions between the car agent and other agents on the road
within the simulation. When optimizing the model, the LLM agent also
interprets human data to enhance the model via RLHF. Our system incorporates
both physical and simulation sensors. The initial implementation demonstrates
various scenarios where LLMs are applied to the framework. This preliminary
work establishes the foundational infrastructure for our experiments and
discusses the theoretical feasibility of the framework.

However, there is still much work to be done in the next stage of our plan.
Firstly, the GPT-4 interface has rate limits; we may need to explore different
interfaces for this study. The machine learning model for autonomous driving
should be evaluated across different types of multimodal models to prove the
robustness of our method. We will apply more real-life data to our research to
improve the robustness of our method. We will recruit subjects with diverse
backgrounds and varying driving skills for human evaluation. Individuals with
good driving skills and those with less experience present different
challenges in our study. We plan to provide a comprehensive evaluation of how
different levels of background influence the RLHF autonomous driving
framework.

Finally, we hope that through our study, we can eventually propose a safe
driving model that can help autonomous vehicles navigate real-life roads and
contribute to the overall road safety of society.

##  6\. Acknowledgments

This work was supported by the National Science Foundation (NSF) as part of
the Center for Smart Streetscapes, under NSF Cooperative Agreement
EEC-2133516. DataCity Smart Mobility Testing Ground is jointly funded by
Middlesex County Resolution 21-821-R, New Jersey Department of Transportation
and Federal Highway Administration Research Project 21-60168.

## References

  * (1) “COSMOS Lab” Accessed: 2024-05-26  URL: https://cosmos-lab.org/
  * (2) Yaodong Cui et al.  “DriveLLM: Charting the path toward full autonomous driving with large language models”  In _IEEE Transactions on Intelligent Vehicles_ IEEE, 2023
  * (3) “DataCity Smart Mobility Testing Ground” Accessed: 2024-05-26  URL: https://cait.rutgers.edu/datacity/
  * (4) Yiqun Duan, Qiang Zhang and Renjing Xu  “Prompting Multi-Modal Tokens to Enhance End-to-End Autonomous Driving Imitation Learning with LLMs”  In _arXiv preprint arXiv:2404.04869_ , 2024
  * (5) Daocheng Fu et al.  “LimSim++: A Closed-Loop Platform for Deploying Multimodal LLMs in Autonomous Driving”  In _arXiv preprint arXiv:2402.01246_ , 2024
  * (6) Christopher Galias et al.  “Simulation-based reinforcement learning for autonomous driving”, 2019
  * (7) Carl-Johan Hoel, Krister Wolff and Leo Laine  “Automated speed and lane change decision making using deep reinforcement learning”  In _2018 21st International Conference on Intelligent Transportation Systems (ITSC)_ , 2018, pp. 2148–2155  IEEE
  * (8) Robert Kirk et al.  “Understanding the effects of rlhf on llm generalisation and diversity”  In _arXiv preprint arXiv:2310.06452_ , 2023
  * (9) Timothy P Lillicrap et al.  “Continuous control with deep reinforcement learning”  In _arXiv preprint arXiv:1509.02971_ , 2015
  * (10) Jimuyang Zhang Zanming Huang Arijit Ray and Eshed Ohn-Bar  “Feedback-Guided Autonomous Driving”
  * (11) Stuart J Russell and Peter Norvig  “Artificial intelligence: a modern approach”  Pearson, 2016
  * (12) Nisan Stiennon et al.  “Learning to summarize with human feedback”  In _Advances in Neural Information Processing Systems_ 33, 2020, pp. 3008–3021
  * (13) Hao Sun  “Reinforcement learning in the era of llms: What is essential? what is needed? an rl perspective on rlhf, prompting, and beyond”  In _arXiv preprint arXiv:2310.06147_ , 2023
  * (14) Shuhan Tan et al.  “Language conditioned traffic generation”  In _arXiv preprint arXiv:2307.07947_ , 2023
  * (15) Letian Wang et al.  “Efficient reinforcement learning for autonomous driving with parameterized skills and priors”  In _arXiv preprint arXiv:2305.04412_ , 2023
  * (16) Sen Wang et al.  “ADEPT: A testing platform for simulated autonomous driving”  In _Proceedings of the 37th IEEE/ACM International Conference on Automated Software Engineering_ , 2022, pp. 1–4
  * (17) Chen Zheng et al.  “Balancing Enhancement, Harmlessness, and General Capabilities: Enhancing Conversational LLMs with Direct RLHF”  In _arXiv preprint arXiv:2403.02513_ , 2024
  * (18) Banghua Zhu, Michael Jordan and Jiantao Jiao  “Principled reinforcement learning with human feedback from pairwise or k-wise comparisons”  In _International Conference on Machine Learning_ , 2023, pp. 43037–43067  PMLR
  * (19) Daniel M Ziegler et al.  “Fine-tuning language models from human preferences”  In _arXiv preprint arXiv:1909.08593_ , 2019