# Relation Graphs and Partial Clones on a 2-Element Set

Miguel Couceiro, Lucien Haddad, Karsten Schölzel, Tamas Waldhauser

► To cite this version:

Miguel Couceiro, Lucien Haddad, Karsten Schölzel, Tamas Waldhauser. Relation Graphs and Partial Clones on a 2-Element Set. IEEE 44th International Symposium on Multiple-Valued Logic (ISMVL), 2014, May 2014, Bremen, Germany. pp.161-166, 10.1109/ISMVL.2014.36 . hal-01090638

HAL Id: hal-01090638

https://hal.science/hal-01090638

Submitted on 13 Aug 2015

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
RELATION GRAPHS AND PARTIAL CLONES ON A
2-ELEMENT SET

MIGUEL COUCEIRO, LUCIEN HADDAD, KARSTEN SCHÖLZEL, AND TAMÁS WALDHAUSER

ABSTRACT. In a recent paper, the authors show that the sublattice of partial clones that preserve the relation { (0,0), (0,1), (1,0) } is of continuum cardinality on 2. In this paper we give an alternative proof to this result by making use of a representation of relations derived from { (0,0), (0,1), (1,0) } in terms of certain types of graphs. As a by-product, this tool brings some light into the understanding of the structure of this uncountable sublattice of strong partial clones.

# 1. INTRODUCTION

Let $A$ be a finite non-singleton set. Without loss of generality we assume that $A = \mathbf{k} := \{0, \dots, k-1\}$. For a positive integer $n$, an $n$-ary partial function on $\mathbf{k}$ is a map $f : \text{dom}(f) \to \mathbf{k}$ where $\text{dom}(f)$ is a subset of $\mathbf{k}^n$ called the domain of $f$. If $\text{dom}(f) = \mathbf{k}^n$, then $f$ is a total function (or operation) on $\mathbf{k}$. Let $\text{Par}^{(n)}(\mathbf{k})$ denote the set of all $n$-ary partial functions on $\mathbf{k}$ and let $\text{Par}(\mathbf{k}) := \bigcup_{n \ge 1} \text{Par}^{(n)}(\mathbf{k})$. The set of all total operations on $\mathbf{k}$ is denoted by $\text{Op}(\mathbf{k})$.

For $n, m \ge 1$, $f \in \text{Par}^{(n)}(\mathbf{k})$ and $g_1, \dots, g_n \in \text{Par}^{(m)}(\mathbf{k})$, the composition of $f$ and $g_1, \dots, g_n$, denoted by $f[g_1, \dots, g_n] \in \text{Par}^{(m)}(\mathbf{k})$, is defined by

$$ \text{dom}(f[g_1, \dots, g_n]) := \{\vec{a} \in \mathbf{k}^m : \vec{a} \in \bigcap_{i=1}^n \text{dom}(g_i) \text{ and } (g_1(\vec{a}), \dots, g_n(\vec{a})) \in \text{dom}(f)\} $$

and

$$ f[g_1, \dots, g_n](\vec{a}) := f(g_1(\vec{a}), \dots, g_n(\vec{a})) $$

for all $\vec{a} \in \text{dom}(f[g_1, \dots, g_n])$.

For every positive integer $n$ and each $1 \le i \le n$, let $e_i^n$ denote the $n$-ary $i$-th projection function defined by $e_i^n(a_1, \dots, a_n) = a_i$ for all $(a_1, \dots, a_n) \in \mathbf{k}^n$. Furthermore, let

$$ J_{\mathbf{k}} := \{e_i^n : 1 \le i \le n\} $$

be the set of all (total) projections.

**Definition 1.** A partial clone on $\mathbf{k}$ is a composition closed subset of $\text{Par}(\mathbf{k})$ containing $J_{\mathbf{k}}$.

The partial clones on $\mathbf{k}$, ordered by inclusion, form a lattice $\mathcal{L}_{P_{\mathbf{k}}}$ in which the infinimum is the set-theoretical intersection. That means that the intersection of an arbitrary family of partial clones on $\mathbf{k}$ is also a partial clone on $\mathbf{k}$.

**Examples.**

$$ (1) \quad \Omega_k := \bigcup_{n \ge 1} \{f \in \text{Par}^{(n)}(\mathbf{k}) : \text{dom}(f) \ne \emptyset \implies \text{dom}(f) = \mathbf{k}^n\} \text{ is a partial clone on } \mathbf{k}. $$
(2) For $a = 0, 1$ let $T_a$ be the set of all total functions satisfying $f(a, \dots, a) = a$, $M$ be the set of all monotone total functions and $S$ be the set of all self-dual total functions on **2**. Then $T_0, T_1, M$ and $S$ are (total) clones on **2**.

(3) Let

$$ T_{0,2} := \{f \in \mathrm{Op}(\mathbf{2}) : [(a_1, b_1) \neq (1, 1), \dots, (a_n, b_n) \neq (1, 1)] \\ \qquad \implies (f(a_1, \dots, a_n), f(b_1, \dots, b_n)) \neq (1, 1)\}. $$

Then $T_{0,2}$ is a (total) clone on **2**.

(4) Let

$$ \tilde{S} := \{f \in \mathrm{Par}(\mathbf{2}) : \{(a_1, \dots, a_n), (\neg a_1, \dots, \neg a_n)\} \subseteq \mathrm{dom}(f) \\ \qquad \implies f(\neg a_1, \dots, \neg a_n) = \neg f(a_1, \dots, a_n)\}, $$

where $\neg$ is the negation on **2**. Then $\tilde{S}$ is a partial clone on **2**.

**Definition 2.** For $h \ge 1$, let $\rho$ be an $h$-ary relation on $\mathbf{k}$ and $f$ be an $n$-ary partial function on $\mathbf{k}$. We say that $f$ preserves $\rho$ if for every $h \times n$ matrix $M = [M_{ij}]$ whose columns $M_{*j} \in \rho$, $(j = 1, \dots, n)$ and whose rows $M_{i*} \in \mathrm{dom}(f)$ $(i = 1, \dots, h)$, the $h$-tuple $(f(M_{1*}), \dots, f(M_{h*})) \in \rho$. Define

$$ \mathrm{pPol}(\rho) := \{f \in \mathrm{Par}(\mathbf{k}) : f \text{ preserves } \rho\}. $$

It is well known that $\mathrm{pPol}\rho$ is a partial clone called the *partial clone determined by the relation* $\rho$. Note that if there is no $h \times n$ matrix $M = [M_{ij}]$ whose columns $M_{*j} \in \rho$ and whose rows $M_{i*} \in \mathrm{dom}(f)$, then $f \in \mathrm{pPol}(\rho)$.

Each partial clone of the form $\mathrm{pPol}(\rho)$ is closed under taking subfunctions, in the sense that if a partial function $f$ belongs to $\mathrm{pPol}(\rho)$, then so does any partial function $g$ such that $\mathrm{dom}(g) \subseteq \mathrm{dom}(f)$ and $g$ is the restriction of $f$ to $\mathrm{dom} g$. Such partial clones are called *strong partial clones*. Note also that the total clone on $\mathbf{k}$ determined by the relation $\rho$ is $\mathrm{Pol}(\rho) := \mathrm{pPol}(\rho) \cap \mathrm{Op}(\mathbf{k})$.

In the examples above $T_a = \mathrm{Pol}(\{a\})$, $M = \mathrm{Pol}(\leq)$, $S = \mathrm{Pol}(\neq)$, $T_{0,2} = \mathrm{Pol}(\{(0,0), (0,1), (1,0)\})$ and $\tilde{S} = \mathrm{pPol}(\neq)$, whereas $\Omega_k$ is not a strong partial clone. Here, for simplicity, we write $\leq$ for $\{(0,0), (0,1), (1,1)\}$ and $\neq$ for $\{(0,1), (1,0)\}$.

The study of partial clones on **2** := $\{0,1\}$ was initiated by Freivald [7]. Among other things, he showed that the set of all monotone partial functions and the set of all self-dual partial functions are both maximal partial clones on **2**. In fact, Freivald showed that there are exactly eight maximal partial clones on **2**. To state Freivald's result, we introduce the following two relations: let

$$ R_1 = \{(x, x, y, y) : x, y \in \mathbf{2}\} \cup \{(x, y, y, x) : x, y \in \mathbf{2}\} $$

$$ R_2 = R_1 \cup \{(x, y, x, y) : x, y \in \mathbf{2}\}. $$

**Theorem 3.** ([7]) There are exactly 8 maximal partial clones on **2**: $\mathrm{pPol}(\{0\})$, $\mathrm{pPol}(\{1\})$, $\mathrm{pPol}(\{0,1\})$, $\mathrm{pPol}(\leq)$, $\mathrm{pPol}(\neq)$, $\mathrm{pPol}(R_1)$, $\mathrm{pPol}(R_2)$ and $\Omega_2$.

Note that the set of total functions preserving $R_2$ form the maximal clone of all (total) linear functions over **2**.

Also interesting is to determine the intersections of maximal partial clones. It is shown in [1] that the set of all partial clones on **2** that contain the maximal clone consisting of all total linear functions on **2** is of continuum cardinality (for details see [1, 10] and Theorem 20.7.13 of [14]). A consequence of this is that the interval of partial clones $[\mathrm{pPol}(R_2) \cap \Omega_2, \mathrm{Par}(\mathbf{2})]$ is of continuum cardinality.

A similar result, (but slightly easier to prove) is established in [9] where it is shown that the interval of partial clones $[\mathrm{pPol}(R_1) \cap \Omega_2, \mathrm{Par}(\mathbf{2})]$ is also of continuum cardinality. Notice that the three maximal partial clones $\mathrm{pPol} R_1$, $\mathrm{pPol} R_2$ and $\Omega_2$ contain all unary functions (i.e., maps) on **2**. Such partial clones are called *Slupecki type* partial clones in [10, 17]. These are the only three maximal partial clones of Slupecki type on **2**.
For a complete study of the pairwise intersections of all maximal partial clones of Slupecki type on a finite non-singleton set $k$, see [10]. The papers [11, 12, 15, 18, 19] focus on the case $k = 2$ where various interesting, and sometimes hard to obtain, results are established. For instance, the intervals

$$[\text{pPol}(\{0\}) \cap \text{pPol}(\{1\}) \cap \text{pPol}(\{(0, 1)\}) \cap \text{pPol}(\leq), \text{Par}(2)]$$

and

$$[\text{pPol}(\{0\}) \cap \text{pPol}(\{1\}) \cap \text{pPol}(\{(0, 1)\}) \cap \text{pPol}(\neq), \text{Par}(2)]$$

are shown to be finite and are completely described in [11]. Some of the results in [11] are included in [18, 19] where partial clones on **2** are handled via the one point extension approach (see section 20.2 in [14]).

In view of results from [1, 9, 11, 18, 19], it was thought that if $2 \le i \le 5$ and $M_1, \dots, M_i$ are non-Slupecki maximal partial clones on **2**, then the interval $[M_1 \cap \dots \cap M_i, \text{Par}(2)]$ is either finite or countably infinite. Now it is shown in [12] that the interval of partial clones $[\text{pPol}(\le) \cap \text{pPol}(\ne), \text{Par}(2)]$ is infinite. However, it remained an open problem to determine whether $[\text{pPol}(\le) \cap \text{pPol}(\ne), \text{Par}(2)]$ is countably or uncountably infinite. This problem was settled in [3]:

**Theorem 4.** The interval of partial clones $[\text{pPol}(\le) \cap \text{pPol}(\ne), \text{Par}(2)]$ that contain the strong partial clone of monotone self-dual partial functions, is of continuum cardinality on **2**.

The main construction in proving this result was later adapted in [4] to solve an intrinsically related problem that was first considered by D. Lau, and tackled recently by several authors, namely: Given a total clone $C$ on **2**, describe the interval $\mathcal{I}(C)$ of all partial clones on **2** whose total component is $C$.

In [4] we established a complete classification of all intervals of the form $\mathcal{I}(C)$, for a total clone $C$ on **2**, and showed that each such $\mathcal{I}(C)$ is either finite or of continuum cardinality. Given the previous results by several authors, the missing case was settled by the following:

**Theorem 5 ([4]).** The interval of partial clones $\mathcal{I}(T_{0,2})$ is of continuum cardinality.

In this paper we provide an alternative proof of Theorem 5 based on a representation of relations that are invariant under $T_{0,2}$ by graphs. By defining an appropriate closure operator on graphs, we will show that there are a continuum of such closed classes of graphs, which in turn are in a one-to-one correspondence with strong partial clones containing $T_{0,2}$, thus providing an alternative proof of Theorem 5. As we will see, this construction will contribute to a better understanding of the structure of this uncountable sublattice of partial clones.

This paper is organized as follows. In Section 2 we recall some basic notions and preliminary results on relations, graphs and lattices that will be needed throughout. In Section 3 we introduce a representation of relations by graphs and show that the lattice of strong partial clones containing $T_{0,2}$ is dually isomorphic to the lattice of “closed” classes of graphs. Motivated by this duality, in Section 4 we focus on this lattice of closed classes of graphs and provide some preliminary results about its structure. (The descriptions of this section are given in terms of graphs. Their dual counterparts, i.e., descriptions in terms of strong partial clones will be part of an extension to the current paper.)

## 2. PRELIMINARIES

2.1. **Relations.** Let $k \ge 2$ and $k = \{0, 1, \dots, k-1\}$. An $n$-ary relation over $k$ is a subset $\rho$ of $k^n$. Sometimes it will be convenient to think of a relation $\rho$ as an $n \times |\rho|$ matrix, whose columns are the tuples belonging to $\rho$ (the order of the columns is
irrelevant). We can also regard $\rho$ as a map $\mathbf{k}^n \to \{0, 1\}$, whose value at $(a_1, \dots, a_n)$ is 1 iff $(a_1, \dots, a_n) \in \rho$. We shall need the following constructions for relations.

* If two relations $\rho$ and $\sigma$, considered as matrices, can be obtained from each other by permuting rows and adding or deleting repeated rows, then we say that $\rho$ and $\sigma$ are essentially the same, and we write $\rho \approx \sigma$. Notice that in such a case we have pPol $\rho = pPol \sigma$.

* For $\rho \subseteq \mathbf{k}^n$ and $\sigma \subseteq \mathbf{k}^m$, the direct product of $\rho$ and $\sigma$ is the relation $\rho \times \sigma \subseteq \mathbf{k}^{n+m}$ defined by

$$ \rho \times \sigma = \{(a_1, \dots, a_{n+m}) \in \mathbf{k}^{n+m} : (a_1, \dots, a_n) \in \rho \text{ and } (a_{n+1}, \dots, a_{n+m}) \in \sigma\}. $$

* Let $\rho \subseteq \mathbf{k}^n$ and let $\varepsilon$ be an equivalence relation on $\{1, 2, \dots, n\}$. Define $\Delta_\varepsilon(\rho) \subseteq \mathbf{k}^n$ by

$$ \Delta_\varepsilon(\rho) = \{(a_1, \dots, a_n) \in \mathbf{k}^n : (a_1, \dots, a_n) \in \rho \text{ and } a_i = a_j \text{ whenever } (i, j) \in \varepsilon\}. $$

We say that $\Delta_\varepsilon(\rho)$ is obtained from $\rho$ by *diagonalization*.

For a class $\mathcal{R}$ of relations on $\mathbf{k}$, we say that $\mathcal{R}$ is *closed* if

1) if $\rho, \sigma \in \mathcal{R}$, then $\rho \times \sigma \in \mathcal{R}$;

2) if $\rho \in \mathcal{R}$, then $\Delta_\varepsilon(\rho) \in \mathcal{R}$ (for all appropriate equivalence relations $\varepsilon$);

3) $\emptyset, \mathbf{k} \in \mathcal{R}$ (here $\mathbf{k}$ is understood as the total unary relation);

4) if $\rho \in \mathcal{R}$ and $\sigma \approx \rho$, then $\sigma \in \mathcal{R}$.

The closure of a class of relations $\mathcal{R}$ is the smallest closed class $\langle \mathcal{R} \rangle$ that contains $\mathcal{R}$. This closure can be described in terms of first order formulas, too: $\sigma \subseteq \mathbf{k}^n$ belongs to $\langle \mathcal{R} \rangle$ if and only if $\sigma$ is definable by a quantifier-free primitive positive formula over the set $\mathcal{R} \cup \{=\}$. Formally, $\sigma \in \langle \mathcal{R} \rangle$ if and only if there exist relations $\rho_1, \dots, \rho_t \in \mathcal{R} \cup \{=\}$ of arities $r_1, \dots, r_t$, respectively, and there are variables $z_i^{(j)} \in \{x_1, x_2, \dots, x_n\}$ ($j = 1, \dots, t$; $i = 1, \dots, r_j$) such that

$$ \sigma(x_1, \dots, x_n) = \bigwedge_{j=1}^{t} \rho_j \left( z_1^{(j)}, \dots, z_{r_j}^{(j)} \right). $$

The closure operator described above is exactly the Galois closure corresponding to the Galois connection pPol-Inv between partial functions and relations: for every class $\mathcal{R}$ of relations on $\mathbf{k}$ we have $\langle \mathcal{R} \rangle = \text{Inv pPol } \mathcal{R}$.

## 2.2. Graphs.
We consider finite undirected graphs without multiple edges. For any graph $G$, let $V(G)$ and $E(G)$ denote the set of vertices and edges of $G$, respectively. An edge $uv \in E(G)$ is called a loop if $u = v$. A map $\varphi: V(G) \to V(H)$ is a homomorphism from $G$ to $H$ if for all $uv \in E(G)$ we have $\varphi(u)\varphi(v) \in E(H)$. We use the notation $G \to H$ to denote the fact that there is a homomorphism from $G$ to $H$. The homomorphic image of $G$ under $\varphi$ is the subgraph $\varphi(G)$ of $H$ given by $V(\varphi(G)) = \{\varphi(v) : v \in V(G)\}$ and $E(\varphi(G)) = \{\varphi(u)\varphi(v) : uv \in E(G)\}$. If $\varphi(G)$ is an induced subgraph of $H$, then we say that $\varphi$ is a faithful homomorphism; this means that every edge of $H$ between two vertices in $\varphi(V(G))$ is the image of an edge of $G$ under $\varphi$. If $\varphi: G \to H$ is a surjective faithful homomorphism, then $\varphi$ is said to be a complete homomorphism. In this case $H$ is the homomorphic image of $G$ under $\varphi$ (i.e., $H = \varphi(G)$), and we shall denote this by $G \to H$.

If $\varepsilon$ is an equivalence relation on the set of vertices $V(G)$ of a graph $G$, then we can form the quotient graph $G/\varepsilon$ as follows: the vertices of $G/\varepsilon$ are the equivalence classes of $\varepsilon$, and two such equivalence classes $C, D$ are connected by an edge in $G/\varepsilon$ if and only if there exist $u \in C, v \in D$ such that $uv \in E(G)$. Note that a vertex of $G/\varepsilon$ has no loop if and only if the corresponding equivalence class is an independent set in $G$ (i.e., there are no edges inside this equivalence class in $G$). There is a canonical correspondence between quotients and homomorphic images:
the quotient $G/\varepsilon$ is a homomorphic image of $G$ (under the natural homomorphism sending every vertex to the $\varepsilon$-class to which it belongs), and if $\varphi: G \to H$ is a complete homomorphism, then $H$ is isomorphic to the quotient of $G$ corresponding to the kernel of $\varphi$.

For $n \ge 0$, the complete graph $K_n$ is the graph on $n$ vertices that has no loops but has an edge between any two distinct vertices, i.e.,

$$E(K_n) = \{uv: u, v \in V(K_n) \text{ and } u \neq v\}.$$

Note that this defines $K_n$ only up to isomorphism (as the vertex set is not specified). In fact, in the following we will not distinguish between isomorphic graphs. For $n = 0$ we obtain the null graph $K_0$ with an empty set of vertices, cf. [13]. For $n = 1$ we get the graph $K_1$ consisting of a single isolated vertex. We will denote the one-vertex graph with a loop by $L$.

A homomorphism $G \to K_n$ is a proper coloring of $G$ by $n$ colors (regard the vertices of $K_n$ as $n$ different colors; properness means that adjacent vertices of $G$ must receive different colors). The chromatic number $\chi(G)$ of a loopless graph is the least number of colors required in a proper coloring of $G$. Observe that if $G \to H$, then $\chi(G) \le \chi(H)$, since $G \to H \to K_n$ implies $G \to K_n$ for all natural numbers $n$. A graph is bipartite if and only if $\chi(G) \le 2$, i.e., $G$ is 2-colorable.

The girth of a graph is the length of its shortest cycle (if there is a cycle at all), and the odd girth of a graph $G$ is the length of the shortest cycle of odd length in $G$ (is there is an odd cycle at all, i.e., if $G$ is not bipartite). The odd girth can be described in terms of homomorphisms as follows. Let $C_n$ denote the cycle of length $n$ without loops (just like $K_n$, this graph is defined only up to isomorphism). Then the odd girth of a non-bipartite graph $G$ is the least odd number $n$ such that $C_n \to G$. It follows that if $G \to H$, then the odd girth of $H$ is at most as large as the odd girth of $G$. Paul Erdős has proved that for any pair of natural numbers $(k, g)$ with $k, g \ge 3$ there exists a graph with chromatic number $k$ and girth $g$ [6].

The disjoint union of graphs $G$ and $H$ will be denoted by $G \oplus H$. Observe that there exist natural homomorphisms $G \to G \oplus H$ and $H \to G \oplus H$. By $k \cdot G := G \oplus \cdots \oplus G$ we denote the disjoint union of $k$ copies of $G$ (with $0 \cdot G = K_0$). For classes $\mathcal{K}_1$ and $\mathcal{K}_2$ of graphs, let $\mathcal{K}_1 \oplus \mathcal{K}_2 = \{G_1 \oplus G_2: G_1 \in \mathcal{K}_1, G_2 \in \mathcal{K}_2\}$.

**2.3. Technical lemma on meet irreducible elements of lattices.** In the last section we will make use of the following result dealing with meet irreducible elements of complete lattices. For general background in lattice theory we refer the reader to [5, 8].

**Lemma 6.** If $L$ is a complete lattice and $a \in L$ is meet irreducible but not completely meet irreducible then a does not have an upper cover in $L$.

*Proof.* Assume for contradiction that $a \in L$ is meet irreducible but not completely meet irreducible yet $a$ does have an upper cover $b$ in $L$. Since $a$ is not completely meet irreducible, there exists a set $S \subseteq L$ such that $\bigwedge S = a$ and $a \notin S$. For arbitrary $s \in S$ we have $a \le s \wedge b \le b$, thus either $s \wedge b = a$ or $s \wedge b = b$, as $b$ covers $a$. However, $a$ is meet irreducible, hence $s \wedge b = a$ is impossible. Therefore, $s \wedge b = b$, i.e., $s \ge b$ for all $s \in S$. This implies $\bigwedge S \ge b$, which contradicts $\bigwedge S = a$. $\square$

### 3. REPRESENTING RELATIONS BY GRAPHS

Let $\rho_{0,2}$ be the binary relation $\rho_{0,2} = \{(0,0), (0,1), (1,0)\} \subseteq \mathbb{2}^2$. We will represent relations in $\langle\rho_{0,2}\rangle$ by graphs, and we will introduce an appropriate closure operator on graphs such that the closed classes of graphs are in a one-to-one correspondence with the closed subclasses of $\langle\rho_{0,2}\rangle$, which are in turn in a one-to-one correspondence with the strong partial clones containing $\text{pPol}\,\rho_{0,2}$. This will allow
us to give a simple proof for the fact that there is a continuum of strong partial clones containing $T_{0,2}$, and we will be able to describe the bottom and the top of the lattice of these clones.

Let $\mathcal{G}$ denote the set of all (isomorphism types of) finite graphs without multiple edges but possibly with loops. If $G \in \mathcal{G}$ is a graph with $V(G) = \{v_1, \dots, v_n\}$, then we can define a relation $\mathrm{rel}(G) \subseteq 2^n$ by

$$ \mathrm{rel}(G)(x_1, \dots, x_n) = \bigwedge_{v_i v_j \in E(G)} \rho_{0,2}(x_i, x_j). $$

Note that if we enumerate the vertices of $G$ in a different way, then we obtain a different relation; however, these two relations differ only in the order of their rows, hence they are essentially the same. Clearly, $\mathrm{rel}(G) \in \langle \rho_{0,2} \rangle$ for every $G \in \mathcal{G}$; moreover, for any $\sigma \in \langle \rho_{0,2} \rangle$ there exists $G \in \mathcal{G}$ such that $\sigma$ and $\mathrm{rel}(G)$ are essentially the same. Indeed, $\sigma \in \langle \rho_{0,2} \rangle$ implies that $\sigma$ is of the form

$$ \sigma(x_1, \dots, x_n) = \bigwedge_{j=1}^{t} \rho_{0,2}(x_{u_j}, x_{v_j}) \wedge \bigwedge_{j=t+1}^{s} (x_{u_j} = x_{v_j}), $$

where $u_j, v_j \in \{1, 2, \dots, n\}$ ($j = 1, \dots, s$). Now if we define $G \in \mathcal{G}$ by $V(G) = \{1, 2, \dots, n\}$ and

$$ E(G) = \{u_1 v_1, \dots, u_t v_t\}, $$

then we have $\sigma \approx \mathrm{rel}(G/\varepsilon)$, where $\varepsilon$ is the least equivalence relation on $V(G)$ that contains the pairs $(u_{t+1}, v_{t+1})$, $\dots$, $(u_s, v_s)$.

It may happen that nonisomorphic graphs induce essentially the same relation. This is captured by the following equivalence relation. We say that the graphs $G, H \in \mathcal{G}$ are *loopvivalent* (notation: $G \circled{\sim} H$) if the following two conditions are satisfied:

* $G$ has a loop if and only if $H$ has a loop;

* the subgraphs spanned by the loopless vertices in $G$ and $H$ are isomorphic.

**Lemma 7.** For any $G, H \in \mathcal{G}$, we have $\mathrm{rel}(G) \approx \mathrm{rel}(H) \iff G \circled{\sim} H$.

*Proof.* Let $G \in \mathcal{G}$ be an arbitrary graph with $V(G) = \{v_1, \dots, v_n\}$. Since $\rho_{0,2} = 2^2 \setminus \{(1, 1)\}$, a tuple $\mathbf{a} = (a_1, \dots, a_n) \in 2^n$ belongs to $\mathrm{rel}(G)$ if and only if $\mathbf{a}^{-1}(1) := \{v_i : a_i = 1\} \subseteq V(G)$ is an independent set. Thus the tuples in $\mathrm{rel}(G)$ are in a one-to-one correspondence with the independent sets of $G$. Therefore, for any $G, H \in \mathcal{G}$ with $V(G) = V(H) = \{v_1, \dots, v_n\}$, we have $\mathrm{rel}(G) = \mathrm{rel}(H)$ if and only if $G$ and $H$ have the same independent sets. This holds if and only if $G$ and $H$ have the same loops and they have the same edges between loopless vertices. Indeed, a vertex $v_i$ has a loop if and only if the set $\{v_i\}$ is not independent, and there is an edge between loopless vertices $v_i$ and $v_j$ if and only if the set $\{v_i, v_j\}$ is not independent. Moreover, edges between a looped vertex and any other vertex are irrelevant in determining independent sets, since a set containing a looped vertex can never be independent.

Now let us determine the possible repeated rows of the matrix of $\mathrm{rel}(G)$. If two vertices $v_i$ and $v_j$ both have a loop, then the $i$-th and the $j$-th rows of the matrix of $\mathrm{rel}(G)$ are identical (in fact, they are constant 0, as a looped vertex cannot belong to any independent set). On the other hand, if, say, $v_i$ does not have a loop, then $\{v_i\}$ is an independent set, and the corresponding tuple $\mathbf{a} \in \mathrm{rel}(G)$ satisfies $1 = a_i \neq a_j = 0$, hence the $i$-th and the $j$-th rows of the matrix of $\mathrm{rel}(G)$ are different. Thus the matrix of $\mathrm{rel}(G)$ has repeated rows if and only if $G$ has more than one loop, and in this case the repeated rows are the constant 0 rows corresponding to the looped vertices.
From the above considerations it follows that for any $G, H \in \mathcal{G}$ we have $\mathrm{rel}(G) \approx \mathrm{rel}(H)$ if and only if $G \circled{H}$.

<figure><img src="image_1.png" /></figure>

We say that a class $\mathcal{K} \subseteq \mathcal{G}$ of graphs is closed if

1) if $G, H \in \mathcal{K}$, then $G \oplus H \in \mathcal{K}$;

2) if $G \in \mathcal{K}$ and $G \to H$, then $H \in \mathcal{K}$;

3) $K_0, K_1 \in \mathcal{K}$;

4) if $G \in \mathcal{K}$ and $G \circled{H}$, then $H \in \mathcal{K}$.

The closure of a class of graphs $\mathcal{K} \subseteq \mathcal{G}$ is the smallest closed class $\langle \mathcal{K} \rangle$ that contains $\mathcal{K}$.

**Remark 1.** For the following considerations it will be useful to observe that if a graph $G$ can be built by gluing together copies of given graphs $H_1, \dots, H_k$, then $G \in \langle H_1, \dots, H_k \rangle$. For instance, any graph can be built from edges, isolated vertices and looped vertices, hence $\mathcal{G} = \langle K_2, K_1, L \rangle = \langle K_2 \rangle$. (We can omit $K_1$, since it is automatically included in every closed class by definition, and we can omit $L$ as it is a homomorphic image of $K_2$.)

**Proposition 8.** *The lattice of closed subclasses of $\langle \rho_{0,2} \rangle$ is isomorphic to the lattice of closed subclasses of $\mathcal{G}$.*

*Proof.* For closed classes $\mathcal{K} \subseteq \mathcal{G}$ and $\mathcal{R} \subseteq \langle \rho_{0,2} \rangle$, let

$$ \Phi(\mathcal{K}) = \{\sigma \in \langle \rho_{0,2} \rangle : \exists G \in \mathcal{K} \text{ such that } \sigma \approx \mathrm{rel}(G)\}; $$

$$ \Psi(\mathcal{R}) = \{G \in \mathcal{G} : \mathrm{rel}(G) \in \mathcal{R}\}. $$

It is straightforward to verify that $\Phi(\mathcal{K})$ is a closed subclass of $\langle \rho_{0,2} \rangle$ and $\Psi(\mathcal{R})$ is a closed subclass of $\mathcal{G}$. It is clear that both $\Phi$ and $\Psi$ are order-preserving maps, hence it only remains to show that they are inverses of each other:

$$ \begin{aligned} \Psi\Phi(\mathcal{K}) &= \{G \in \mathcal{G} : \mathrm{rel}(G) \in \Phi(\mathcal{K})\} = \{G \in \mathcal{G} : \exists H \in \mathcal{K} \text{ such that } \mathrm{rel}(G) \approx \mathrm{rel}(H)\} \\ &= \{G \in \mathcal{G} : \exists H \in \mathcal{K} \text{ such that } G \circled{H}\} = \mathcal{K}; \end{aligned} $$

$$ \begin{aligned} \Phi\Psi(\mathcal{R}) &= \{\sigma \in \langle \rho_{0,2} \rangle : \exists G \in \Psi(\mathcal{R}) \text{ such that } \sigma \approx \mathrm{rel}(G)\} \\ &= \{\sigma \in \langle \rho_{0,2} \rangle : \exists G \in \mathcal{G} \text{ such that } \mathrm{rel}(G) \in \mathcal{R} \text{ and } \sigma \approx \mathrm{rel}(G)\} = \mathcal{R}. \end{aligned} $$

<figure><img src="image_2.png" /></figure>

**Corollary 9.** *The lattice of strong partial clones containing $T_{0,2}$ is dually isomorphic to the lattice of closed subclasses of $\mathcal{G}$.*

### 4. THE LATTICE OF CLOSED CLASSES

From now on, we focus on the lattice of closed subclasses of $\mathcal{G}$. We will first take a closer look at the bottom and the top of the lattice, and then we show that the “middle part” embeds the power set of a countably infinite set, hence it has continuum cardinality.

#### 4.1. The bottom and the top.
The smallest closed class is $\langle \emptyset \rangle = \langle K_1 \rangle$, which is just the set of edgeless graphs. Any graph containing an edge has $L$ (the graph having only one vertex with a loop on it) as a homomorphic image, hence the second smallest closed class is $\langle L \rangle$, which consists of graphs containing no edges between loopless vertices. In the next lemma we prove that the third smallest closed subclass of $\mathcal{G}$ is $\mathcal{G}_0 \cup \langle K_1 \rangle$, where $\mathcal{G}_0$ stands for the class of all graphs containing at least one loop.

**Lemma 10.** *At the bottom of the lattice of closed subclasses of $\mathcal{G}$ we have the three-element chain $\langle K_1 \rangle \prec \langle L \rangle \prec \langle K_2 \oplus L \rangle = \mathcal{G}_0 \cup \langle K_1 \rangle$. All other closed subclasses of $\mathcal{G}$ contain $\langle K_2 \oplus L \rangle$.*
*Proof.* Let $\mathcal{K} \subseteq \mathcal{G}$ be a closed class such that $\langle L \rangle \subset \mathcal{K}$. Then $\mathcal{K}$ contains a graph $G$ with an edge $uv$ where $u$ and $v$ are distinct loopless vertices. We form the disjoint union $G \oplus L$, and then we identify all vertices of this graph except for $u$ and $v$. Then we obtain a graph $G' \in \mathcal{K}$ with $V(G') = \{u, v, w\}$ and $\{uv, ww\} \subseteq E(G') \subseteq \{uv, ww, uw, vw\}$. Deleting the edges $uw$ and $vw$ (if they are present) we arrive at a graph $G''$ with $V(G'') = \{u, v, w\}$ and $E(G'') = \{uv, ww\}$. Since $G'' \circled{G'}$, we have $G'' \in \mathcal{K}$; moreover, $G''$ is isomorphic to $K_2 \oplus L$, hence $\langle K_2 \oplus L \rangle \subseteq \mathcal{K}$. This proves that $\langle K_2 \oplus L \rangle$ is the third smallest closed subclass of $\mathcal{G}$.

It only remains to prove that $\langle K_2 \oplus L \rangle = \mathcal{G}_0 \cup \langle K_1 \rangle$. It is clear that $\mathcal{G}_0 \cup \langle K_1 \rangle$ is closed and $K_2 \oplus L \in \mathcal{G}_0 \cup \langle K_1 \rangle$, therefore $\langle K_2 \oplus L \rangle \subseteq \mathcal{G}_0 \cup \langle K_1 \rangle$. For the containment $\mathcal{G}_0 \cup \langle K_1 \rangle \subseteq \langle K_2 \oplus L \rangle$, consider an arbitrary graph $G \in \mathcal{G}_0 \cup \langle K_1 \rangle$. If $G$ has no loops, then $G \in \langle K_1 \rangle \subseteq \langle K_2 \oplus L \rangle$. If $G$ has a loop, then let $G^* = H \oplus L$, where $H$ is the loopless part of $G$, and let $k = |E(G^*)| - 1 = |E(H)|$. Then an appropriate quotient of $k \cdot (K_2 \oplus L)$ is isomorphic to $G^*$ (we need to identify all $k$ copies of $L$, and identify the vertices of the $k$ copies of $K_2$ in such a way that we obtain the graph $H$). Thus $G \circled{G^*} \in \langle K_2 \oplus L \rangle$, and then we have $G \in \langle K_2 \oplus L \rangle$, proving that $\mathcal{G}_0 \cup \langle K_1 \rangle \subseteq \langle K_2 \oplus L \rangle$. $\square$

As we will see later, we have to stop our climbing up in the lattice here, as there is no fourth smallest closed class, so we now focus on the top of the lattice. The largest closed class is clearly $\mathcal{G}$, which, as we observed in Remark 1, can be generated by $K_2$. The following lemma describes the second largest closed class, for which we need a notation: let $\mathcal{G}_1$ denote the class of all loopless non-bipartite graphs without isolated vertices. Note that $\mathcal{G}_1 \oplus \langle K_1 \rangle$ consists of all loopless non-bipartite graphs (with or without isolated vertices).

**Lemma 11.** *At the top of the lattice of closed subclasses of $\mathcal{G}$ we have the two-element chain $\mathcal{G} = \langle K_2 \rangle \succ \mathcal{G}_0 \cup \langle K_1 \rangle \cup (\mathcal{G}_1 \oplus \langle K_1 \rangle)$. All other closed subclasses of $\mathcal{G}$ are contained in $\mathcal{G}_0 \cup \langle K_1 \rangle \cup (\mathcal{G}_1 \oplus \langle K_1 \rangle)$.*

*Proof.* Consider a closed class $\mathcal{K}$ such that $\mathcal{G}_0 \cup \langle K_1 \rangle \subseteq \mathcal{K} \subset \mathcal{G}$. If $\mathcal{K}$ contains a graph $G$ that is bipartite and has at least one edge (which cannot be a loop, because of bipartiteness), then we have $G \to K_2 \in \mathcal{K}$. Then we can conclude $\mathcal{K} \supseteq \langle K_2 \rangle = \mathcal{G}$ (cf. Remark 1). Thus the second largest closed class must be contained in $\mathcal{G}_0 \cup \langle K_1 \rangle \cup (\mathcal{G}_1 \oplus \langle K_1 \rangle)$. It remains to show that the class $\mathcal{G}_0 \cup \langle K_1 \rangle \cup (\mathcal{G}_1 \oplus \langle K_1 \rangle)$ is closed. To verify this, one just needs to observe that if at least one of $G$ and $H$ is not bipartite, then $G \oplus H$ is not bipartite either; furthermore, if $G$ is not bipartite and $G \to H$, then $H$ is not bipartite either (otherwise we would have $G \to H \to K_2$, hence $G \to K_2$, contradicting the non-bipartiteness of $G$). Therefore, the second largest closed class is indeed $\mathcal{G}_0 \cup \langle K_1 \rangle \cup (\mathcal{G}_1 \oplus \langle K_1 \rangle)$. $\square$

We will see in the next subsection that there is no third largest closed subclass of $\mathcal{G}$, therefore we finish our climbing down here and summarize our findings in the following theorem.

**Theorem 12.** *A class $\mathcal{K} \subseteq \mathcal{G}$ is closed if and only if either*

1) $\mathcal{K} = \langle K_1 \rangle$, or

2) $\mathcal{K} = \langle L \rangle$, or

3) $\mathcal{K} = \langle K_2 \oplus L \rangle = \mathcal{G}_0 \cup \langle K_1 \rangle$, or

4) $\mathcal{K} = \langle K_2 \rangle = \mathcal{G}$, or

5) $\mathcal{K} = \mathcal{G}_0 \cup \langle K_1 \rangle \cup (\mathcal{G}_1 \oplus \langle K_1 \rangle)$, or

6) $\mathcal{K} = \mathcal{G}_0 \cup \langle K_1 \rangle \cup (\mathcal{K}_1 \oplus \langle K_1 \rangle)$, where $\mathcal{K}_1 \subset \mathcal{G}_1$ satisfies

(a) if $G, H \in \mathcal{K}_1$, then $G \oplus H \in \mathcal{K}_1$;

(b) if $G \in \mathcal{K}_1$ and $G \to H$, then $H \in \mathcal{G}_0 \cup \mathcal{K}_1$.
Proof. By Lemmas 10 and 11, the classes listed in the first five items are closed, and any other closed class $\mathcal{K}$ satisfies $\mathcal{G}_0 \cup \langle K_1 \rangle \subset \mathcal{K} \subset \mathcal{G}_0 \cup \langle K_1 \rangle \cup (\mathcal{G}_1 \oplus \langle K_1 \rangle)$. Let $\mathcal{K}$ be such a class, let $G$ be a loopless non-bipartite member of $\mathcal{K}$, and let $G_1$ be the subgraph of $G$ spanned by its non-isolated vertices. Then we have $G \to G_1$ (identify all isolated vertices with another vertex), hence $G_1 \in \mathcal{K}$. This means that $\mathcal{K}$ can be written in the form $\mathcal{K} = \mathcal{G}_0 \cup \langle K_1 \rangle \cup (\mathcal{K}_1 \oplus \langle K_1 \rangle)$, where $\mathcal{K}_1 \subset \mathcal{G}_1$ is the set of all loopless non-bipartite members of $\mathcal{K}$ that have no isolated vertices. To finish the proof, one just has to verify that a class $\mathcal{K} = \mathcal{G}_0 \cup \langle K_1 \rangle \cup (\mathcal{K}_1 \oplus \langle K_1 \rangle)$, with $\mathcal{K}_1 \subseteq \mathcal{G}_1$ is closed if and only if $\mathcal{K}_1$ is closed under disjoint unions and loopless homomorphic images. $\square$

4.2. **The middle.** In this subsection we focus on the interval

$$[\mathcal{G}_0 \cup \langle K_1 \rangle, \mathcal{G}_0 \cup \langle K_1 \rangle \cup (\mathcal{G}_1 \oplus \langle K_1 \rangle)]$$

in the lattice of closed subclasses of $\mathcal{G}$. Therefore, from now on we consider only classes $\mathcal{J} \subseteq \mathcal{G}_1$, and we introduce a new closure operator for such classes: let $\langle \mathcal{J} \rangle_1$ stand for the class of all loopless graphs that can be built from elements of $\mathcal{J}$ by forming disjoint unions and homomorphic images. (Observe that $\langle \mathcal{J} \rangle_1 \subseteq \mathcal{G}_1$, since disjoint unions and homomorphic images cannot create isolated vertices.) We say that $\mathcal{J}$ is 1-closed if $\langle \mathcal{J} \rangle_1 = \mathcal{J}$. It follows from Theorem 12 that the interval $[\mathcal{G}_0 \cup \langle K_1 \rangle, \mathcal{G}_0 \cup \langle K_1 \rangle \cup (\mathcal{G}_1 \oplus \langle K_1 \rangle)]$ is isomorphic to the lattice of 1-closed subclasses of $\mathcal{G}_1$ under the isomorphism $\mathcal{G}_0 \cup \langle K_1 \rangle \cup (\mathcal{K}_1 \oplus \langle K_1 \rangle) \mapsto \mathcal{K}_1$. (Note that we allow $\mathcal{K}_1$ to be empty.)

In the sequel we will assume that all homomorphisms map to loopless graphs; in particular, we never identify vertices connected by an edge. It is easy to see that a disjoint union of quotients of graphs $H_1, \dots, H_k$ is also a quotient of $H_1 \oplus \cdots \oplus H_k$, thus we obtain the following description of 1-closure.

**Fact 13.** For arbitrary $\mathcal{J} \subseteq \mathcal{G}_1$ and $G \in \mathcal{G}_1$ we have $G \in \langle \mathcal{J} \rangle_1 \iff H_1 \oplus \cdots \oplus H_k \to G$ for some $k \in \mathbb{N}$ and $H_1, \dots, H_k \in \mathcal{J}$.

The following theorem shows that the lattice of 1-closed subclasses of $\mathcal{G}_1$ is uncountable, hence there is a continuum of strong partial clones containing $T_{0,2}$.

**Theorem 14.** There exist continuously many 1-closed classes $\mathcal{J} \subseteq \mathcal{G}_1$.

Proof. Note that if $\mathcal{J} \subseteq \mathcal{G}_1$ is an order filter (upset) with respect to the homomorphism order (i.e., $G \in \mathcal{J}, G \to H$ implies $H \in \mathcal{J}$ for all $H \in \mathcal{G}_1$), then $\mathcal{J}$ is 1-closed. It follows that if $\mathcal{A} \subseteq \mathcal{G}_1$ is an infinite antichain in the homomorphism order, then the order filters generated by different subsets of $\mathcal{A}$ yield a continuum of 1-closed subclasses of $\mathcal{G}_1$. The existence of such an antichain is well-known; for instance, let $\mathcal{A} = \{A_3, A_5, A_7, \dots\}$, where $A_k$ is a graph with chromatic number $k$ and odd girth $k$ (cf. [6]). $\square$

Now we turn to the proof of the promised fact that there is no “fourth smallest” element in the lattice of closed subclasses of $\mathcal{G}$. By Theorem 12, this is equivalent to the nonexistence of atoms in the lattice of 1-closed subclasses of $\mathcal{G}_1$.

**Lemma 15.** For every $G \in \mathcal{G}_1$ and $n \ge 3$ we have $K_n \in \langle G \rangle_1$ if and only if $\chi(G) \le n$.

Proof. If $K_n \in \langle G \rangle_1$, then, by Fact 13, there exists a complete homomorphism $\varphi: k \cdot G \to K_n$ for some $k \ge 1$. Restricting $\varphi$ to any one of the $k$ copies of $K_n$ we get a homomorphism (not necessarily complete) $G \to K_n$, and this show that $\chi(G) \le n$.

Now assume that $\chi(G) \le n$, and let us use the numbers $1, 2, \dots, n$ for the $n$ colors in proper $n$-colorings of $G$. Fix an edge $uv \in E(G)$, and for each pair of
colors $i \neq j$, choose a proper $n$-coloring of $G$ such that $u$ and $v$ receive the colors $i$ and $j$, respectively. Joining all these $\binom{n}{2}$ colorings we obtain a homomorphism $\binom{n}{2} \cdot G \to K_n$, which is complete, as each edge $ij \in E(K_n)$ is the image of one of the $\binom{n}{2}$ copies of the edge $uv$. This proves that $K_n \in \langle G \rangle_1$. $\square$

**Theorem 16.** The empty class is meet irreducible in the lattice of 1-closed subclasses of $G_1$, but it is not completely meet irreducible, as it is the intersection of the descending chain

$$ (1) \qquad \langle K_3 \rangle_1 \supset \langle K_4 \rangle_1 \supset \langle K_5 \rangle_1 \supset \dots $$

Therefore, there is no atom in the lattice of 1-closed subclasses of $G_1$.

*Proof.* By Fact 13, a graph $G \in G_1$ belongs to $\langle K_n \rangle_1$ if and only if $G$ is a quotient of $k \cdot K_n$ for some $k \ge 1$. Since $G$ has no loops, we cannot identify vertices within the same copy of $K_n$, i.e., $G$ is built by gluing together $k$ complete graphs of size $n$. This shows that $\langle K_n \rangle_1$ consists of those graphs that have the property that every vertex is contained in a complete subgraph (clique) of size $n$. Now, if the maximum clique size of $G \in G_1$ is $n$, then $G \notin \langle K_{n+1} \rangle_1$, hence the intersection of the chain (1) is indeed empty.

In order to prove that the empty class is meet irreducible, we consider two nonempty 1-closed classes $\mathcal{J}$ and $\mathcal{K}$. Choose arbitrary graphs $G \in \mathcal{J}$, $H \in \mathcal{K}$, and let $n = \max(\chi(G), \chi(H))$. From Lemma 15 we obtain

$$ K_n \in \langle G \rangle_1 \cap \langle H \rangle_1 \subseteq \mathcal{J} \cap \mathcal{K}, $$

hence $\mathcal{J} \cap \mathcal{K}$ is not empty.

The last statement of the theorem follows now from Lemma 6. $\square$

Finally, we prove that there is no “third largest” element in the lattice of closed subclasses of $G$. By Theorem 12, this is equivalent to the nonexistence of coatoms in the lattice of 1-closed subclasses of $G_1$.

**Lemma 17.** For every $G \in G_1$ and every odd number $n \ge 3$ we have $G \in \langle C_n \oplus K_2 \rangle_1$ if and only if the odd girth of $G$ is at most $n$.

*Proof.* If $G \in \langle C_n \oplus K_2 \rangle_1$, then, by Fact 13, there exists a complete homomorphism $\varphi: k \cdot (C_n \oplus K_2) \to G$ for some $k \ge 1$. Restricting $\varphi$ to any one of the $k$ copies of $C_n$ we get a homomorphism (not necessarily complete) $C_n \to G$, and this show that the odd girth of $G$ is at most $n$.

Now assume that the odd girth of $G$ is $g$ and $g \le n$. Let $H$ be a cycle of length $g$ in $G$, and let $k = |E(G)| - g = |E(G) \setminus E(H)|$. For every edge $uv \in E(G) \setminus E(H)$ let $\varphi_{uv}: C_g \oplus K_2 \to G$ be a homomorphism that maps $C_g$ to $H$ and (the edge of) $K_2$ to $uv$. Combining all these homomorphisms $\varphi_{uv}$ ($uv \in E(G) \setminus E(H)$) we obtain a homomorphism $\varphi: k \cdot (C_g \oplus K_2) \to G$, which is complete, as every edge of $H$ is the image of $k$ edges from the cycles $C_g$, and every other edge $uv \in E(G) \setminus E(H)$ is the image of the edge of one of the complete graphs $K_2$. Since $g \le n$, we have $C_n \to C_g$, hence $k \cdot (C_n \oplus K_2) \to k \cdot (C_g \oplus K_2) \to G$. This proves that $G \in \langle C_n \oplus K_2 \rangle_1$. $\square$

**Theorem 18.** The class $G_1$ is join irreducible in the lattice of 1-closed subclasses of $G_1$, but it is not completely join irreducible, as it is the join of the ascending chain

$$ (2) \qquad \langle C_3 \oplus K_2 \rangle_1 \subset \langle C_5 \oplus K_2 \rangle_1 \subset \langle C_7 \oplus K_2 \rangle_1 \subset \dots $$

Therefore, there is no coatom in the lattice of 1-closed subclasses of $G_1$.

*Proof.* Lemma 17 implies that the join of the chain (2) is $G_1$, as every non-bipartite graph contains an odd cycle.
In order to prove that $G_1$ is join irreducible, we consider two proper 1-closed subclasses $\mathcal{J}$ and $\mathcal{K}$ of $G_1$. Since $\mathcal{J} \neq G_1$, only finitely many of the graphs $C_3 \oplus K_2, C_5 \oplus K_2, \dots$ can belong to $\mathcal{J}$. A similar argument applies to $\mathcal{K}$, thus there exists an odd number $n \ge 3$ such that $C_n \oplus K_2 \notin \mathcal{J} \cup \mathcal{K}$. We claim that $C_n \oplus K_2 \notin \mathcal{J} \vee \mathcal{K}$. Suppose for contradiction that $C_n \oplus K_2 \in \mathcal{J} \vee \mathcal{K} = (\mathcal{J} \cup \mathcal{K})_1$. Then, by Fact 13, there is a complete homomorphism

$$ \varphi: G_1 \oplus \dots \oplus G_j \oplus H_1 \oplus \dots \oplus H_k \to C_n \oplus K_2, $$

where $G_1, \dots, G_j \in \mathcal{J}$, $H_1, \dots, H_k \in \mathcal{K}$. Since $\varphi$ is a complete homomorphism, $G := \varphi(G_1 \oplus \dots \oplus G_j) \in (\mathcal{J})_1 = \mathcal{J}$ and $H := \varphi(H_1 \oplus \dots \oplus H_k) \in (\mathcal{K})_1 = \mathcal{K}$ are subgraphs of $C_n \oplus K_2$ such that every edge of $C_n \oplus K_2$ is contained in at least one of $G$ and $H$. We may assume without loss of generality that the edge of $K_2$ is contained in $G$. If all edges of $C_n$ also belong to $G$, then we have $C_n \oplus K_2 = G \in \mathcal{J}$, contrary to our assumption. If at least one of the edges of $C_n$ does not belong to $G$, then $G \in \mathcal{J}$ is a bipartite graph, which is again a contradiction, as $\mathcal{J} \subseteq G_1$. These contradictions imply that $C_n \oplus K_2 \notin \mathcal{J} \vee \mathcal{K}$, hence $\mathcal{J} \vee \mathcal{K} \neq G_1$, and this proves that $G_1$ is indeed join irreducible.

The last statement of the theorem follows now from the dual of Lemma 6. $\square$

## 5. ACKNOWLEDGMENTS

L. Haddad is supported by Academic Research Program of RMC. K. Schölzel is supported by the internal research project MRDO2 of the University of Luxembourg. T. Waldhauser is supported by the Hungarian National Foundation for Scientific Research under grants no. K83219 and K104251. The present project is supported by the European Union and co-funded by the European Social Fund under the project "Telemedicine-focused research activities on the field of Mathematics, Informatics and Medical sciences" of project number "TÁMOP-4.2.2.A-11/1/KONV-2012-0073".

## REFERENCES

[1] V. B. Alekseev and L. L. Voronenko, Some closed classes in the partial two-valued logic (Russian), *Diskret. Mathematika* **6**, 4 (1994), 58–79

[2] M. Couceiro, L. Haddad. Intersections of finitely generated maximal partial clones, *Multiple-Valued Logic Soft Computing* **19**:1-3 (2012) 85–94.

[3] M. Couceiro, L. Haddad and I. G. Rosenberg, Partial clones containing all Boolean monotone self-dual partial functions. Preprint 2011.

[4] M. Couceiro, L. Haddad, K. Schölzel, T. Waldhauser. A complete solution to a problem by D. Lau on partial Boolean clones. *43rd IEEE International Symposium on Multiple-Valued Logic* (ISMVL 2013), IEEE Computer Society, 123–128.

[5] B. A. Davey and H. A. Priestley. *Introduction to Lattices and Order*. Cambridge University Press, New York, second edition, 2002.

[6] P. Erdös, Graph theory and probability, Canad. J. Math., **11** (1959), 34–38.

[7] R. V. Freivald, Completeness criteria for functions of the algebra of logic and many-valued logics. *Dokl. Akad. Nauk. SSSR*, **167**, **6** (1966) 1249-1250.

[8] G. Grätzer. *General Lattice Theory*. Birkhäuser Verlag, Berlin, 2003. Second edition.

[9] L. Haddad, On the depth of the intersection of two maximal partial clones, *Multi. Val. Logic, an International Journal*, **3**, No 3 (1998), 259–270.

[10] L. Haddad and D. Lau, Pairwise intersections of Slupecki type maximal partial clones. *Contributions to Algebra and Geometry*, Volume 41 (2000), No. 2, 537–555.

[11] L. Haddad and G. E. Simons, Interval of Boolean Partial Clones. *Italian Journal of Pure and App. Math.*, No 21 (2007), pp 147-162.

[12] L. Haddad, Partial clones containing all self-dual monotonic Boolean partial functions. *Proc. 39th IEEE International Symposium on Multiple-Valued Logic*, pp 173–178, Okinawa, Japan, May 2009. Detailed paper to appear in *Journal of Multiple-Valued Logic and Soft Computing*.

[13] F. Harary, R.C. Read, Is the null-graph a pointless concept?, Graphs and Combinatorics, Lecture Notes in Mathematics 406, pp. 37–44. Springer, 1974.
[14] D. Lau, *Function Algebras on Finite Sets*, a basic course on Multiple-Valued Logic and Clone Theory, 670 pages, Springer Monograph in Mathematics, 2006.

[15] D. Lau and K. Schölzel, A Classification of Partial Boolean Clones. *Proc.* 40th *IEEE International Symposium on Multiple-Valued Logic*, pp 198 – 194, Barcelona, Spain, May 2010.

[16] B. A. Romov, The algebras of partial functions and their invariants, *Kibernetika*; English translation in *Cybernetics* **17** (1981) 157–167.

[17] B. A. Romov, Maximal subalgebras of algebras of partial multivalued logic functions, *Kibernetika*; English translation in *Cybernetics* **16** (1980) 31–41.

[18] B. Strauch, On partial classes containing all monotone and zero-preserving total Boolean functions. *Math. Log. Quart.* **43** (1997).

[19] B. Strauch, The classes which contain all monotone and idempotent total Boolean functions, Universität Rostock, preprint 1996.