HEIGHT-TWO CONCEPT LATTICES: GRAPH
DECOMPOSITION AND HORN
AXIOMATIZABILITY

A O Basheyeva, A M Nurakunov, Y K Nurlibayev, A T Zhussupova

► To cite this version:

A O Basheyeva, A M Nurakunov, Y K Nurlibayev, A T Zhussupova. HEIGHT-TWO CONCEPT LATTICES: GRAPH DECOMPOSITION AND HORN AXIOMATIZABILITY. 2026. hal-05521375

HAL Id: hal-05521375

https://hal.science/hal-05521375v1

Preprint submitted on 20 Feb 2026

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

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

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
HEIGHT-TWO CONCEPT LATTICES: GRAPH DECOMPOSITION
AND HORN AXIOMATIZABILITY

A. O. BASHEYEVA, A. M. NURAKUNOV, Y. K. NURLIBAYEV, AND A. T. ZHUSSUPOVA

ABSTRACT. We characterize subdirect formal contexts whose concept lattices are isomorphic to the lattices of height two, proving that this holds precisely when the context graph decomposes into disjoint complete bipartite components, equivalently when the incidence relation admits a partition-inducing multivalued functional representation, and when the clarified context relation is bijective. We also show that the class of context graphs whose concept lattices have height two forms a finitely axiomatizable universal Horn class. These results connect lattice structure, graph decomposition, and logical definability within Formal Concept Analysis.

# 1. INTRODUCTION

Formal Concept Analysis (FCA) provides a fundamental bridge between order
theory, lattice theory, and discrete structures by assigning to every formal context
$\mathbb{K} = (G, M, I)$ a complete lattice $L(\mathbb{K})$ of formal concepts (see. [1, 2]). The struc-
tural properties of $L(\mathbb{K})$ reflect combinatorial features of the incidence relation $I$,
and conversely, lattice-theoretic conditions often admit precise interpretations in
terms of the underlying context. Understanding when a concept lattice belongs
to a prescribed class of lattices is therefore a problem linking FCA with universal
algebra, graph theory, and structural combinatorics. One natural line of investi-
gation is to characterize contexts whose concept lattices are isomorphic to specific
canonical lattices. Such characterizations typically reveal hidden regularities of the
incidence relation and lead to structural decompositions of contexts. In particular,
representations of contexts via graphs often expose algebraic constraints that are
not immediately visible from the definition of concepts.

Our first main result provides a complete characterization of subdirect contexts
whose concept lattice is isomorphic to the lattice of height two. The theorem es-
tablishes the equivalence of four descriptions of such contexts: a lattice-theoretic
condition, a graph-theoretic decomposition of the context graph into disjoint com-
plete bipartite components, a functional representation of the incidence relation via
a surjective multivalued map inducing an *n*-partition of attributes, and a bijec-
tive correspondence between objects and attributes in the clarified context. These
equivalences reveal that the lattice structure of height two arises precisely when the

<footnote n="2020">2020 Mathematics Subject Classification. 06A15, 06C99, 08C15, 05C99,
Key words and phrases. Formal concept analysis, lattice, concept lattice, bipartite graph, uni-
versal Horn class.</footnote>

<footnote>The authors are funded by the Science Committee of MSHE RK (Grant no. AP23485395).</footnote>
incidence relation decomposes into independent blocks exhibiting perfect bipartite symmetry.

Our second main result concerns a broader model-theoretic perspective. We show that the class of all context graphs whose concept lattices are isomorphic to lattices of height two forms a finitely axiomatizable universal Horn class. Thus, this family admits a purely logical description by a finite set of universal Horn sentences in the language of directed graphs.

These results strengthen the connections between FCA, graph decompositions, and universal algebraic methods, and they supply practical criteria for recognizing when a dataset generates lattices of specific types. In particular, the Horn axiomatizability result shows that certain lattice-theoretic constraints on data can be captured by finitely many local graph conditions.

For more information on the basic notions and results of FCA, lattice theory, graph theory and universal algebra introduced below, and used throughout this paper, we refer the reader to [2, 3, 4, 5].

## 2. PRELIMINARIES

Firstly, we recall the main definitions. Standard notions are highlighted in bold-face, while less familiar ones are presented as definitions.

A lattice $L$ is a **height-two lattice** (or lattice of height two) if every maximal chain in $L$ consist of three elements. It easy to see that any height-two lattice is isomorphic to a lattice in which every atom is a coatom.

A graph $G$ is an ordered pair $G = (V, E)$, where $V$ is a nonempty set of vertices, and $E \subseteq V \times V$ is a set of edges. For any $(a, b) \in E$, the element $a$ is called a **starting point**, and $b$ the **endpoint**.

For a graph $G = (V, E)$, let

$$E^{-1} = \{(u, v) \mid (v, u) \in E\}.$$

A graph $G = (V, E)$ is called **undirected** if $E = E^{-1}$, and **directed** or a **digraph** if $E \cap E^{-1} = \emptyset$. An element $a \in V$ is a **loop** if $(a, a) \in E$. In particular, by definition, a digraph has no loops.

A graph $G = (V, E)$ is called **bipartite** if its vertex set $V$ can be partitioned into two disjoint subsets $V_1$ and $V_2$ such that $E \subseteq V_1 \times V_2 \cup V_2 \times V_1$. Note that, by definition, a graph $G = (V, \emptyset)$ is bipartite.

A **biclique** (or a complete bipartite graph) $G = (V, E)$ is a bipartite graph for which $E = V_1 \times V_2$ for some partition $\{V_1, V_2\}$ of the vertex set $V$. Note that, by definition, a graph $G = (V, \emptyset)$ is a biclique.

**Definition 2.1.** A multivalued function from a set $X$ to a set $Y$ is a mapping

$$F: X \to P(Y)$$

that assigns to each point $x \in X$ a non-empty set $F(x) \subseteq Y$.

Equivalently, a multivalued function $F$ can be understood as a relation $F \subseteq X \times Y$ such that for every $x \in X$ there exists at least one $y \in Y$ with $(x, y) \in F$.
**Definition 2.2.** A graph of a multivalued function $F$ is the set

$$gr(F) = \{(x, y) \in X \times Y \mid y \in F(x)\}.$$

**Definition 2.3.** A multivalued function $F: X \to P(Y)$ is **surjective** if

$$Y = \cup \{F(x) \mid x \in X\}.$$

Equivalently, every element of the set $Y$ occurs as a value of $F(x)$ for at least one $x \in X$.

The preliminaries on Formal Concept Analysis follow the textbook [2].

A **formal context** $\mathbb{K} = (G, M, I)$ consists of the set of objects $G$, the set of attributes $M$, and the incidence relation $I \subseteq G \times M$.

For a formal context $\mathbb{K} = (G, M, I)$ and subsets $A \subseteq G$, $B \subseteq M$, we define

$$\alpha_{\mathbb{K}}(A) = \{m \in M \mid (\forall g \in A) [(g, m) \in I]\},$$

$$\beta_{\mathbb{K}}(B) = \{g \in G \mid (\forall m \in B) [(g, m) \in I]\}.$$

The mappings $\beta_{\mathbb{K}} \circ \alpha_{\mathbb{K}}: \mathcal{P}(G) \to \mathcal{P}(G)$ and $\alpha_{\mathbb{K}} \circ \beta_{\mathbb{K}}: \mathcal{P}(M) \to \mathcal{P}(M)$ are closure operators. The set $\mathcal{L}_{\mathbb{K}}(G)$ ($\mathcal{L}_{\mathbb{K}}(M)$) of subsets of $G$ ($M$) that are closed under $\beta_{\mathbb{K}} \circ \alpha_{\mathbb{K}}$ ($\alpha_{\mathbb{K}} \circ \beta_{\mathbb{K}}$) forms a lattice under inclusion $\subseteq$ (under reverse inclusion $\supseteq$). Moreover, $\mathcal{L}_{\mathbb{K}}(G)$ is dually isomorphic to $\mathcal{L}_{\mathbb{K}}(M)$.

A **formal concept** of the context $\mathbb{K}$ is a pair $(A, B)$ such that $A \subseteq G$, $B \subseteq M$, $B = \alpha_{\mathbb{K}}(A)$, and $A = \beta_{\mathbb{K}}(B)$.

The ordering $\preceq$ of the concepts of $\mathbb{K}$ is defined as follows:

$$(A_0, B_0) \preceq (A_1, B_1) \Leftrightarrow A_0 \subseteq A_1 \Leftrightarrow B_0 \supseteq B_1.$$

The Basic Theorem on Concept Lattices (see [1]) states that ordering $\preceq$ on the set of all concepts of $\mathbb{K}$ induces a complete lattice, called the **concept lattice** of $\mathbb{K}$, which we denote by $\mathcal{L}(\mathbb{K})$.

From the definition of the partial order $\preceq$, it follows that for a formal context $\mathbb{K} = (G, M, I)$ the mapping $\varphi: \mathcal{L}(\mathbb{K}) \to \mathcal{L}_{\mathbb{K}}(G)$ defined by $\varphi((A, B)) = A$ is an isomorphism between $\mathcal{L}(\mathbb{K})$ and $\mathcal{L}_{\mathbb{K}}(G)$.

For the sets $A, B$ and a binary relation $R \subseteq A \times B$, we define

$$\pi_A(R) = \{a \in A \mid \exists b [(a, b) \in R]\}, \quad \pi_B(R) = \{b \in B \mid \exists a [(a, b) \in R]\}.$$

**Definition 2.4.** A context $\mathbb{K} = (A, B, I)$ is **subdirect** if $\pi_A(I) = A$ and $\pi_B(I) = B$.

For a formal context $\mathbb{K} = (A, B, I)$, we define the formal context $\mathbb{K}^s = (A^s, B^s, I^s)$ as follows:

$$(1) A^s = \pi_A(I) - \beta_{\mathbb{K}}(\pi_B(I)),$$

$$(2) B^s = \pi_B(I) - \alpha_{\mathbb{K}}(\pi_A(I)),$$

$$(3) I^s = I \cap A^r \times B^r.$$

One can see that $\mathbb{K}^s$ is subdirect. Moreover,

**Proposition 2.5.** For a formal context $\mathbb{K} = (A, B, I)$, the concept lattice $\mathcal{L}(\mathbb{K})$ is isomorphic to $\mathcal{L}(\mathbb{K}^s)$ if $\alpha_{\mathbb{K}}(\pi_A(I)) = \emptyset$ and $\beta_{\mathbb{K}}(\pi_B(I)) = \emptyset$.

For a formal context $\mathbb{K} = (A, B, I)$ we define the graph $\mathbf{G}_{\mathbb{K}} = (A \cup B; I)$ whose vertex set is $A \cup B$ and whose edge set is $I \subseteq A \times B$.
**Definition 2.6.** A graph $G$ is called a **context graph** if there is a context $\mathbb{K} =$ $(A, B, I)$ with $A \cap B = \emptyset$ such that $G \cong G_K$.

It easy to see that a context graph is a bipartite digraph. We also note that any bipartite digraph $\mathbf{G} = (A \cup B; I)$ with $I \subseteq A \times B$ defines the formal context $\mathbb{K}_G = (A, B, I)$.

Note that various bipartite undirected graphs derived from contexts have been introduced and studied in many articles and textbooks (see, for example [2, 6, 7]).

For any graph $\mathbf{G} = (G, R)$, we define the formal context $\mathbb{K}_G = (G, G, R)$ and the concept lattice $\mathcal{L}(\mathbb{K}_G)$, respectively.

**Definition 2.7.** A lattice $L$ is called a **graph concept lattice** if there is a graph $\mathbf{G} = (G, R)$ such that $L \cong \mathcal{L}(\mathbb{K}_G)$.

### 3. REPRESENTATION OF $M_n$

For a cardinal $n > 0$, let $M_n$ be a height-two lattice with $n$ atoms.

For brevity, we write $\alpha(A)$ and $\beta(A)$ instead of $\alpha_{\mathbb{K}}(A)$ and $\beta_{\mathbb{K}}(A)$, respectively, whenever the context $\mathbb{K}$ is clear from the discussion. We also write $\alpha(a)$ and $\beta(a)$ in place $\alpha(\{a\})$ and $\beta(\{a\})$.

**Theorem 3.1.** Let $\mathbb{K} = (A, B, I)$ be a subdirect formal context with $A \cap B = \emptyset$. Then the concept lattice $\mathcal{L}(\mathbb{K})$ is isomorphic to $M_n$ for some $n > 0$ if and only if $I$ is a graph of some surjective multivalued function $f : A \to 2^B$ such that the set $\{f(a) \subseteq B \mid a \in A\}$ forms a partition of $B$.

*Proof.* $\Rightarrow$. Since $\mathcal{L}(\mathbb{K}) \cong (\mathcal{L}(B))'$ and $M_n \cong (M_n)',$ then $\mathcal{L}(B) \cong M_n$.

Let $f : A \to 2^B$ be a mapping defined by $f(a) = \alpha(a)$ for all $a \in A$. Since $\mathbb{K}$ is subdirect then for any $b \in B$ there is $a \in A$ such that $(a, b) \in I$. Hence, $B = \cup\{f(a) \mid a \in A\}$, and $f$ is a surjective multivalued function. Let $S = \{f(a) \mid a \in A\}$. Since $S$ consists of the closed sets because $f(a) = \alpha(a)$, and $\mathcal{L}(\mathbb{K}) \cong M_n$, it follows $B_0 \cap B_1 = \emptyset$ for any distinct non-empty sets $B_0, B_1 \in S$. Since $B = \cup\{f(a) \mid a \in A\}$, it follows that $S$ is a partition of $B$.

By definition, $\mathrm{gr}(f) = \{(a, b) \mid a \in A, b \in f(a)\}$. Let $(a, b) \in \mathrm{gr}(f(x))$. By $f(x) = \alpha(x)$, we have $b \in \alpha(a)$. By definition, $\alpha(a) = \{y \in B \mid (a, y) \in I\}$. Hence $(a, b) \in I$. It follows $\mathrm{gr}(f) \subseteq I$.

Now, let $(a, b) \in I$. Then $b \in \alpha(a) = f(a)$. Hence $(a, b) \in \mathrm{gr}(f)$. Thus, $I \subseteq \mathrm{gr}(f)$. Therefore, $I = \mathrm{gr}(f)$.

$\Leftarrow$. By condition of theorem $I = \mathrm{gr}(f)$, whence $\mathbb{K} = (A, B, \mathrm{gr}(f))$. Consider the context graph $G_K = (A \cup B; \mathrm{gr}(f))$. We assume that $A \cap B = \emptyset$, otherwise we reinterpret the elements of $B$.

For any $b \in A$, put $A_b = \{a \in A \mid f(a) = f(b)\}$. The set $\{A_b \mid b \in A\}$ forms a partition. Indeed, since the set $\{f(a) \subseteq B \mid a \in A\}$ forms a partition of the set $B$, then $f(a) = f(b)$ or $f(a) \cap f(b) = \emptyset$. These implies $A_b = A_a$ or $A_a \cap A_b = \emptyset$. And $\cup\{A_b \mid b \in A\} = A$, as $a \in A_a$ for all $a \in A$.

Thus, we have that the sets $\{A_b \mid b \in A\}$ and $\{f(a) \subseteq B \mid a \in A\}$ constitute the partitions of the sets $A$ and $B$, respectively. Since $f(a) = f(b)$ for any $a \in A_b$, then $\mathrm{gr}(f) \cap (A_b \times f(b)) = A_b \times f(b)$. These implies $\mathrm{gr}(f) = \cup\{(A_b \times f(b)) \mid b \in A\}$.
Thus, $G_K = (\cup_{i \le n} A_i, \cup_{i \le n} B_i; \cup_{i \le n} I_i)$ for some partitions $\{A_i | i \le n\}$, $\{B_i | i \le n\}$ of the sets A and B respectively, and $gr(f) = \cup_{i \le n} I_i$ where $I_i = A_i \times B_i$.

The conditions $I = \cup_{i \le n} I_i = \cup_{i \le n} A_i \times B_i$, $A = \cup_{i \le n} A_i$ and $B = \cup_{i \le n} B_i$ give us that $\pi_A(I) = A$, $\pi_B(I) = B$ and the sets $\{b \in B | (a, b) \in I \text{ for all } a \in A\}$ and $\{a \in A | (a, b) \in I \text{ for all } b \in B\}$ are empties. These mean that $\alpha(\pi_A(I)) = \emptyset$ and $\beta(\pi_B(I)) = \emptyset$. By Proposition 2.5, $\mathcal{L}(\mathbb{K}) \cong \mathcal{L}(\mathbb{K}_G)$. Thus, we need to show that $\mathcal{L}(\mathbb{K}_G) \cong M_n$.

For the formal context $\mathbb{K}_G$ we have

$$ \alpha_{\mathbb{K}_G}(X) = \begin{cases} B_i, & \text{if } X \subseteq A_i \\ \emptyset, & \text{otherwise.} \end{cases} \quad \text{and} \quad \beta_{\mathbb{K}_G}(X) = \begin{cases} A_i, & \text{if } X \subseteq B_i \\ \emptyset, & \text{otherwise.} \end{cases} $$

Thus, for any $A_i$ and $X \supset A_i$, we have

$$ \beta_{\mathbb{K}_G} \circ \alpha_{\mathbb{K}_G}(A_i) = A_i, \quad \text{and} \quad \beta_{\mathbb{K}_G} \circ \alpha_{\mathbb{K}_G}(X) = A \cup B. $$

That is, $A_i$, $1 \le i \le n$, and $A \cup B$ are the closed subsets in $A \cup B$ with respect to closure operator $\beta_{\mathbb{K}_G} \circ \alpha_{\mathbb{K}_G}$. Therefore, $A_i \cup A_j = A \cup B$. Since $\{A_i | i \le n\}$ forms a partition of A then $A_i \cap A_j = \emptyset$ for all $i \ne j \le n$. It means that $\mathcal{L}(A) \cong M_n$. Hence $\mathcal{L}(\mathbb{K}_G) \cong M_n$ because $\mathcal{L}(\mathbb{K}_G) \cong \mathcal{L}(A)$. $\square$

**Corollary 3.2** (cf. Example 1 [8], and Theorem 1 [9]). For a surjection function $f: A \to B$, the concept lattice $\mathcal{L}(\mathbb{K}) \cong M_n$, where $\mathbb{K} = (A, B, gr(f))$ and $n = |B|$.

*Proof.* By surjectivity of function $f$, the set $\{\{f(a)\} \subseteq B | a \in A\}$ constitutes a partition of the set $B$ and the context $\mathbb{K} = (A, B, gr(f))$ is subdirect. Hence, according to the Theorem 3.1, $\mathcal{L}(\mathbb{K}) \cong M_n$. $\square$

Recall that a context $\mathbb{K} = (G, M, I)$ is called **clarified**, if for any $g, h \in G$ and $m, n \in M$, from $\alpha(g) = \alpha(h)$ and $\beta(m) = \beta(n)$ it always follows that $g = h$ and $m = n$.

**Corollary 3.3.** Let $\mathbb{K} = (G, M, I)$ be a subdirect clarified context with $G \cap M = \emptyset$. Then, $L(\mathbb{K}) \cong M_n$ iff $I$ is a graph of the bijective function from $G$ to $M$.

*Proof.* $\Rightarrow$. Since, $\mathbb{K} = (G, M, I)$ is subdirect then, by Theorem 3.1, $I$ is a graph of some multivalued function $f$ from $G$ to $M$. From the proof of Theorem 3.1, $f$ is defined as $f(a) = \alpha(a)$ for $a \in G$. Since, $\mathbb{K}$ is clarified, then $\alpha(a) = \alpha(b)$ implies $a = b$. Let $c, d \in M$ and $c, d \in \alpha(a)$. Then $\beta(c) = \{a\}$ and $\beta(d) = \{a\}$. Since, $\mathbb{K}$ is clarified, then $\beta(c) = \beta(d)$ implies $c = d$. Hence, for any $a \in G$ there is unique $c \in M$ such that $f(a) = \{c\}$. Therefore, the mapping $f': G \to M$ defined by the rule $f'(a) = c$, where $f(a) = \{c\}$, is bijective mapping.

$\Leftarrow$. It is a partial case of Corollary 3.2 $\square$

Summarizing Theorem 3.1 and Corollary 3.3 we are proving the following theorem that is one of the main result of the paper.

**Theorem 3.4.** Let $\mathbb{K} = (A, B, I)$ be a subdirect formal context. Then the following are equivalent:

$$ (1) \quad L(\mathbb{K}) \cong M_n; $$
(2) the context graph $G_K = (A \cup B; I)$ is a disjoint union of $n$ complete bipartite digraphs;

(3) $I$ is a graph of some surjective multivalued function $f: A \to 2^B$ such that the set $\{f(a) \subseteq B \mid a \in A\}$ forms $n$-partition of the set $B$;

(4) for a clarified context $K^c = (A^c, B^c, I^c)$ of $K$, the set $I^c$ is a graph of some bijective function from $A^c$ to $B^c$.

*Proof.* (1) $\Leftrightarrow$ (3) and (1) $\Leftrightarrow$ (4) are Theorem 3.1 and Corollary 3.3, respectively. Hence (4) $\Leftrightarrow$ (3). To complete the proof, it suffices to show that conditions (2) and (3) are equivalent.

(2) $\Rightarrow$ (3). Let $G_K = \cup_{i \le n} (A_i \cup B_i; I_i)$ be a disjoint union of $n$ complete bipartite digraphs $(A_i \cup B_i, I_i)$. Define a mapping $f: A \to 2^K$ by the rule $f(a) = B_i$ for all $a \in A_i$ and $i \le n$. One can see that the mapping $f$ constitutes a manyvalued function. Since $B = \cup_{i \le n} B_i$ then $f$ is surjective. Moreover, since $f(a) = B_i$ for all $a \in A_i$, $i \le n$, and $B_i \cap B_j = \emptyset$, $i \ne j \le n$, then the set $\{f(a) \mid a \in A\}$ forms an $n$-partition of the set $B$.

(3) $\Rightarrow$ (2). Let $f(a) = B_a$ for $a \in A$. Since $f$ is surjective then $\cup\{B_a \mid a \in A\} = B$. Let $b \in B_a$ and $A_b = \{x \in A \mid b \in f(x)\}$. Since $a \in A_b$ then $A_b \ne \emptyset$. For every $u \in A_b$ we have $b \in f(u)$. Hence $B_a \cap f(u) \ne \emptyset$. Since $\{B_a \mid a \in A\}$ is a partition of $B$ then $B_a = f(u)$ for all $u \in A_b$, and $f(u) \cap B_a = \emptyset$ for every $u \notin A_b$. It follows that $\{A_b \mid b \in B\}$ is a partition of the set $A$, and $f(A_b) = B_a$ for all $b \in B_a$. Hence $A_b \times B_a \subseteq gr(f) = I$. It means that the graph $(A_b \cup B_a, A_b \times B_a)$ is a complete bipartite digraph. Also we note that $(A_b \times B_a) \cap (A_d \times B_c) = \emptyset$ for any $d \notin A_b$ or $c \notin B_a$. Therefore, $G_K = \cup_{a \in A}(A_b \cup B_a; A_b \times B_a)$ is a disjoint union of $n$ complete bipartite digraphs $(A_b \cup B_a, A_b \times B_a)$, $a \in A$. $\square$

We note that equivalence of items (2) and (3) of Theorem 3.4 was established in [8] (Theorem 2).

## 4. AXIOMS OF THE CONTEXT GRAPHS

In this section, we prove the following

**Theorem 4.1.** The class of all context graphs whose graph concept lattices are isomorphic to lattices of height two is a finitely axiomatizable universal Horn class.

*Proof.* Let $\mathcal{R}$ be a class of all context graphs whose graph concept lattices are isomorphic to lattices of height two. And let $\Sigma$ be a set of sentences consisting of the following sentences:

$$ \begin{array}{l} \forall xy [\neg I(x, x)]; \\ \forall xy [\neg I(x, y) \lor \neg I(y, x)]; \\ \forall xyz [\neg I(x, y) \lor \neg I(y, z)]; \\ \forall xyzu [I(x, y) \land I(x, z) \land I(u, y) \rightarrow I(u, z)]; \end{array} $$

From definitions of loop and direction, it follows that the first and second sentences hold for a graph $G$ if and only if $G$ contains no loops and is directed. And the third sentence hold for a graph $G$ if and only if no endpoint of an edge serves as the starting point of any edge.
From the definition of context graph it follows that every context graph has no loops, directed and no endpoint of an edge serves as the starting point of any edge. Hence every context graph satisfies the first three sentences from Σ.

Now we show that every context graph from $\mathcal{R}$ satisfies the fourth sentence of Σ.

Let $\mathbb{K} = (G, M, I)$ be a context whose context graph $G_K$ belongs to $\mathcal{R}$. Suppose that $(a, b), (a, c)$ and $(d, b) \in I$ for some $a, b, c, d \in G \cup M$. By Theorem 3.4, $G_K = \cup_{i \le n} (A_i \cup B_i; I_i)$ is a disjoint union of $n$ complete bipartite digraphs $(A_i \cup B_i, I_i)$. Hence $(a, b), (a, c)$ and $(d, b) \in I_i$ for some $i \le n$. It follows that $a, d \in A_i$ and $b, c \in B_i$. Since $(A_i \cup B_i, I_i)$ is a complete bipartite digraph, then $(d, c) \in I_i$, whence $(d, c) \in I$. It follows that

$$G_K \models \forall xyzu [I(x, y) \wedge I(x, z) \wedge I(u, y) \rightarrow I(u, z)].$$

Thus, we have $\mathcal{R} \models \Sigma$.

To complete the proof, it remains to show that every context graph satisfying $\Sigma$ belongs to $\mathcal{R}$.

Let $G_K \models \Sigma$ for some context $\mathbb{K} = (G, M, I)$.

By the first and second sentences, $G_K$ has no loops and it is directed.

Let $G$ be a set of all starting points of $G_K$, $M$ a set of all end points of $G$, and $V$ a set of all vertices that have no starting and end points. Since the third sentence means that, if it holds in a nontrivial digraph $G$, then no end point of an edge is the starting point of any edge, it follows from definition of $G$ and $M$ that $G \cap M = \emptyset$. Thus, $(G \cup M, I)$ is a bipartite digraph.

Let $b \in M$ and $A_b = \{x \in G | (x, b) \in I\}$. For $a \in A_b$, define $B_a = \{y \in M | (a, y) \in I\}$. By definition of $G$ and $M$, the both $A_b$ and $B_a$ are not empties. Suppose that $(a, b), (a, c)$ and $(d, b) \in I$ for some $a, d \in A_b$ and $b, c \in B_a$. Then, by the fourth quasi-identity, $(d, c) \in I$. It follows that $A_b \times B_a \subseteq I$, which implies that $(A_b \cup B_a, A_b \times B_a)$ is a complete bipartite graph.

Suppose that $(A_b \cup B_a, A_b \times B_a) \cap (A_c \cup B_d, A_c \times B_d)$ is not empty for some bicliques $(A_b \cup B_a, A_b \times B_a)$ and $(A_c \cup B_d, A_c \times B_d)$. That is, there are $u \in A_b \cap A_c$ and $v \in B_a \cap B_d$ with $(u, v) \in A_b \times B_a \cap A_c \times B_d$. Since $(A_b \cup B_a, A_b \times B_a)$ and $(A_c \cup B_d, A_c \times B_d)$ are bicliques, then $A_b = \{x \in A | (x, v) \in I\}$ and $A_c = \{x \in A | (x, v) \in I\}$ because $(u, v) \in A_b \times B_a \cap A_c \times B_d$. Hence $A_b = A_c$. Similar, $B_a = B_d$. Therefore, $A_b \times B_a = A_c \times B_d$. Since $(V, \emptyset)$ is biclique, and $G = \cup\{A_b | b \in M\}$, $M = \cup\{B_b | a \in G\}$, then $G_K$ is a disjoint union of the bicliques $(A_b \cup B_a, A_b \times B_a)$, $a \in G$, and $(V, \emptyset)$. It follows $G_K \in \mathcal{R}$. $\square$

At the end, we note that the class of all lattices of height two is finitely axiomatizable. This raises the following question: if a class of concept graphs is a (finitely axiomatizable) universal Horn class, is the class of all their graph concept lattices also (finitely) axiomatizable?

## REFERENCES

[1] Wille, R. (1982). *Restructuring lattice theory: An approach based on hierarchies of concepts*. In: I. Rival (ed.) *Ordered Sets*, pp. 445-470. Reidel, Dordrecht-Boston. DOI: 10.1007/978-94-009-7798-3-15.
[2] Ganter, B., Wille, R. (1999). *Formal Concept Analysis: Mathematical Foundations*. Springer, Berlin/Heidelberg. DOI: 10.1007/978-3-642-59830-2

[3] Gorbunov, V.A. (1998). *Algebraic theory of quasivarieties*, Springer Science & Business Media. ISBN 9780306110634, 0306110636

[4] Bondy, J. A., Murty, U. S. R. (1976). *Graph Theory with Applications*. New York: Elsevier Science Ltd/North-Holland. DOI: 10.1007/978-1-349-03521-2.

[5] Gratzer, G. (2003). *General Lattice theory*. Second edition, Birkhäuser Verlag. DOI: 10.1007/978-3-0348-7633-9.

[6] Doerfel, S., Hanika, T., Stumme, G. (2018). *Clones in Graphs*. In: Ceci, M., Japkowicz, N., Liu, J., Papadopoulos, G., Raś, Z. (eds) Foundations of Intelligent Systems. Lecture Notes in Computer Science(), vol 11177. Springer, Cham.

[7] Berry, A., Sigayret, A. (2004). *Representing a concept lattice by a graph*. Discrete Applied Mathematics 144, pp. 27-42. DOI: 10.1016/S0166-218x(04)00183-0.

[8] Basheyeva, A.O., Zhussupova, A.T., and Nurlibayev, Y.K. (2025). *Bipartite Digraphs with Mod- ular Concept Lattices of height 2*. Bulletin of the Karaganda University-Mathematics. 119. 68-74. DOI: 10.31489/2025m3/68-74.

[9] Bazhenov N., Mustafa, M., and Nurakunov, A.M. (2024). *On Concept Lattices for Numberings*. Tsinghua Science and Technology 29(6), pp. 1642-1650. DOI: 10.26599/TST.2023.9010102.

(A. O. Basheyeva) L. N. GUMILEV EURASIAN NATIONAL UNIVERSITY, SATPAYEV 2, ASTANA, KAZAKHSTAN

Email address: basheyeva3006@gmail.com

(A. M. Nurakunov) INSTITUTE OF MATHEMATICS, NAN KR, CHU PR. 265A, 720071 BISHKEK, KYRGYZSTAN

Email address: a.nurakunov@gmail.com

(Y. K. Nurlibayev) L. N. GUMILEV EURASIAN NATIONAL UNIVERSITY, SATPAYEV 2, ASTANA, KAZAKHSTAN

Email address: ynurlibayev@gmail.com

(A. T. Zhussupova) L. N. GUMILEV EURASIAN NATIONAL UNIVERSITY, SATPAYEV 2, ASTANA, KAZAKHSTAN

Email address: aiman240390@gmail.com