Loïc Mazo Icube

A framework for digital label images *

Digital label images -partitions of a discrete space -need a specific topological model to take into account not only the topologies of the regions but also the topology of the partition. In this article, we propose a topological framework for label images in which all the regions of the initial partition and of any coarser partition of the space can be explicitly represented accordingly to any classical adjacency relation. Moreover, we define a notion of simple point which enables atomic changes in the partition without breaking any topology. Finally, we discuss about the implementation of the framework.

Introduction

In this paper, we study, from a topological viewpoint, digital label images, that is, images whose domain is Z n and whose codomains are sets on which there generally exists no meaningful order relation (unlike grey-level images for instance). Actually, a digital label image is nothing but a labelled partition of Z n . Label images need a specific approach in topology. Indeed, a label image is much more than a collection of independent objects and we are also interested in the spatial relations between these objects. Thereby, any topologically sound label image processing must pay attention to each object and to the partition itself. Nevertheless, as far as we know, the literature devoted to the topology of label images is not well developed and essentially oriented towards specific applications. The most commonly used approach is to process one label at a time while rejecting temporarily the other labels in the background, coming down to a binary image (e.g. [START_REF] Poupon | Multi-object deformable templates dedicated to the segmentation of brain deep structures[END_REF][START_REF] Bazin | Topology-preserving tissue classification of magnetic resonance brain images[END_REF][START_REF] Liu | Registration of brain atlas to MR images using topology preserving front propagation[END_REF]). With this method, the topology of the partition is generally ignored. Sometimes another structure, like a region adjacency graph, is adjoined. But, except in 2D, this kind of structure can rarely encompass all the topological information of the partition. Furthermore, most of the time, in the applications (see, e.g., [START_REF] Pham | Digital topology in brain imaging[END_REF]) the value of the image on a picture element changes from the background to a particular label, or vice versa, but more seldom it goes from a label to another label. The approach proposed in [START_REF] Cointepas | A cellular model for multi-objects multi-dimensional homotopic deformations[END_REF] makes it possible to change the label of a point in a 3D cellular space by choosing a new label among several ones with the assurance that the homotopy types of the two labels, the new one and the former one, are preserved. Nevertheless, no attention is paid to the topology of the partition. To take this latter topology in consideration, it is proposed in [START_REF] Damiand | Fully deformable 3D digital partition model with topological control[END_REF] to monitor the boundaries between the regions. Besides the fact that the article is restricted to the (6, 18)-adjacency pair in Z 3 (for voxels and regions), it seems difficult to bring out a theoretical model from this framework which mixes notions of digital topology (geodesic neighborhoods), combinatorial topology (collapses on cubical complexes) and discrete surfaces (sets of surfels). In order to take into account the topology of the partition, it is required in [START_REF] Bazin | Digital homeomorphisms in deformable registration[END_REF] that the unions of two labels (in 2D spaces), or two or three labels (in 3D spaces), are watched in any process as well as single labels. However, a careful examination of the examples provided by the authors shows that these conditions are not sufficient to maintain the topology of the partition. In particular, the unions of three labels should also be watched in a 2D space.

In a previous work [START_REF] Mazo | Topology on digital label images[END_REF], we have proposed an extensive theoretical framework to deal with label images. In our model, we have retained the idea to consider unions of objects of the initial partition together with the idea found in [START_REF] Ronse | Morphology on label images: Flat-type operators and connections[END_REF][START_REF] Ronse | Geodesy on label images, and applications to video sequence processing[END_REF], to equip the set of labels with a lattice structure. In other words, with this framework we propose to see a label image as an initial partition together with some meaningful coarser partitions whose labels are provided by the lattice. Accordingly, we described in our previous article some kinds of simple points for label images, that is points whose labels can be changed while preserving the topologies (actually, the weak homotopy types) of the regions of all these partitions. In order to use classical "continuous topology" (as opposed to "discrete topology"), the label images are defined on a poset (partially ordered set), typically the space of cubical complexes equipped with the inclusion, and we use the Alexandroff-Birkhoff topology [START_REF] Alexandroff | Diskrete Räume[END_REF][START_REF] Birkhoff | Rings of sets[END_REF].

Unfortunately, the model described in our previous work has an important drawback at the first stage: the embedding of the digital space in a poset. If the digital objects are not modeled by closed subsets of R n (i.e. if the adjacency relation for the objects is not the (3 n -1)-adjacency), the proposed embedding cannot preserve the topology of each label. More precisely, we cannot generally define, for each label of the lattice, isomorphisms between the discrete topology structures and the continuous topology structures as illustrated on Figure 1. To overcome this issue, we have been led to develop another model that we describe in this article.

The remainder of this article is organized as follows. In Section 2, we define the covering images, the kind of abstract image that we propose to model a label digital image. In Section 3, we present a notion of simple point for covering images, that is an atomic change on a label image that preserves the topologies of the regions identified by the labels of the lattice. Section 4 explains how the whole framework can be implemented and Section 5 concludes the paper. (a) A digital image λ in Z 2 with 2 labels r (red), g (green) and a background (not depicted). (b) The embedding of the image λ in F 2 , the space of cubical 2-complexes, obtained by applying the following membership rule: the label of a 0-, or 1-, dimensional point is the infimum, in the lattice (2 {r,g} , ⊆), of the labels of the surrounding 2-dimensional points. We have proved in [START_REF] Mazo | Digital imaging: A unified topological framework[END_REF] that this embedding preserves the connected components and the fundamental groups of the object and its complement when a binary digital image is interpreted with the (2n, 3 n -1)-adjacency pair. But, if we identify the two labels, that is if we consider a coarser partition of the space, the topology is not the same on these two images (we have one component on the left and two components on the right).

Covering images

In order to model all the topological relations that can be found in a digital label image λ (defined on Z n ), we propose two steps.

1. We split the image λ in a collection of binary images such that each binary image represents a region of interest, that is a region that has been previously labelled (for instance during a segmentation process) or represents a meaningful union of some labeled regions. The unions are labeled thanks to a lattice structure on labels: the label of an union of regions is the supremum of the labels of the regions. No other labels are needed for our purpose, so the lattice of labels, noted T , is an atomistic finite lattice1 whose atoms are the initial labels that we call proto-labels and there is a one-to-one correspondence between this lattice and the collection of binary images (we write λ t for the binary image associated to the label t in the collection built from the digital label image λ). Figure 2 exemplifies this first stage (in the sequel, the infimum and supremum operators on T are denoted ∧ and ∨ while ⊥ and ⊤ are the minimum and the maximum of T ; furthermore, for any t ∈ T , we write A(t) for the set of atoms under t).

2.

In each binary digital image λ t created in the previous step, we introduce inter-xels elements (pointels, linels, surfels and so on) to have a topology available. The space in which we embed the digital images is the space of nD cubical complexes, F n , but it could be another cellular decomposition of the space2 . The inter-xels elements must be labeled with membership rules with respect to the desired interpretation of the image. Such rules can be found in the literature (see e.g. [START_REF] Ayala | Digital lighting functions[END_REF]). We have proposed in [START_REF] Mazo | Digital imaging: A unified topological framework[END_REF] our own rules which preserve the connected components for the classical adjacency pairs and result in isomorphisms between the digital fundamental groups as defined by Kong [START_REF] Kong | A digital fundamental group[END_REF] and the usual fundamental groups of the regions of F n . Our rules are defined as follows. If x, y, z ∈ F n are three points such that x is incident to y and z, dim(y) = dim(z) = dim(x) + 1 and y and z are not incident to the same xel, we say that y and z are opposite with respect to the point x and we denote by opp(x) the set of all pairs {y, z} for y opposite to z with respect to x (see Figure 3). Finally, for a sequence ε of n elements in {-1, 1}, we define the ε-regular (binary) image µ t by µ t (x) = λ t (x) if x is a xel (dim(x) = n) and, otherwise,

⊥ (b) (c) (d) (e) (f) (g) (h) (i) (j)
(a) (b) (c)
µ t (x) = inf{sup{µ t (a), µ t (b)} | {a, b} ∈ opp(x)} if ε(m + 1) = 1 sup{inf{µ t (a), µ t (b)} | {a, b} ∈ opp(x)} if ε(m + 1) = -1
where m = dim(x) and ε(i) denotes the i-th element of the sequence ε. For instance, to extend on F 2 a digital image initially defined on Z 2 , we set ε = (-1, -1) if the image has to be interpreted with the (4, 8)adjacency pair, or ε = (1, 1) if the image has to be interpreted with the (8, 4)-adjacency pair (the sequences (1, -1) and (-1, 1) correspond respectively to sections of 3D-images equipped with the (6, 18)-, or the (18, 6)-, adjacency pair). Note that distinct rules can be applied to distinct labels provided no inconsistency is introduced: for instance, if two voxels are connected in the region R, they cannot be disconnected in a region including R; this leads us to the notion of fiber described below.

After these two steps have been achieved, we get a collection (µ t ) t∈T (actually a lattice) of binary images, the sheets, defined on F n (see Figure 4). Now, we can see this collection of binary images as a unique image µ by setting that µ(x) is equal to the set (we say the fiber ) whose elements are the labels t such that µ t (x) = 1 (in other words, the labels attached to x, or, equivalently, the regions of interest x belongs to). For instance, let x 0 be the horizontal linel between the label r (red) and the label g (green) on Figure 2(a). If we set ε = (-1, -1), we find that µ r (x 0 ) = { {b, r, g}, ⊤} while setting ε = (1, 1), we find that µ r (x 0 ) = {{r}, {g}, {b, r, g}, ⊤} (provided the same membership rule is applied on all the sheets). When a point in F n has not been labeled, for instance, a point in the infinite region surrounding the image, then its fiber is set to ∅. Since the region obtained by identifying two labels t and u, that is, the region associated to the supremum of the labels t and u, contains all the points that are in the region t or in the region u plus, possibly, some other ponts (like the point x 0 when ε = (-1, -1) and we take for t the red label and for u the green one), the fibers are up-sets (or filters), that is for any fiber S, t ∈ S and t ≤ u ⇒ u ∈ S.

We write t ↑ for the upset generated by a label t (t ↑ = {u ∈ T | t ≤ u}) -such a set is called a principal upset (or principal filter) -and we write G T for the family of the up-sets over the lattice T :

G T = t∈A t ↑ | A ⊆ T = t∈A u∈A(t) u ↑ | A ⊆ T . Note that ∅ ∈ G T .
Eventually, we can define a covering image.

Definition 1 (Covering image). Let T be an atomistic finite lattice. A covering image µ is a function from F n to G T . For any t ∈ T , the sheet µ t is the binary image defined on F n by µ t (x) = 1 if t ∈ µ(x) and µ t (x) = 0 otherwise. For any x ∈ F n , the set µ(x) is the fiber over x. A covering image is ε-regular if for any t ∈ T the sheet µ t is ε-regular.

Thanks to the next proposition, a ε-regular covering image µ can be defined without resorting to the sheets µ t , t ∈ T . This is an important point for the implementation since it enables the encoding of a regular covering image directly from a digital label image (see Section 4). Proposition 1. Let T be an atomistic lattice and ε a sequence of n elements in {-1, 1}. A covering image µ :

F n → G T is ε-regular iff, for all x ∈ F n such that dim(x) < n: µ(x) = {a,b}∈opp(x) µ(a) ∪ µ(b) if ε(dim(x) + 1) = 1 {a,b}∈opp(x) µ(a) ∩ µ(b) if ε(dim(x) + 1) = -1.
Proof. Let us assume that dim(x) = m -1 and ε(m) = 1. Then, from Definition 1, for all label t ∈ T , one has

µ t (x) = inf{sup{µ t (a), µ t (b)} | {a, b} ∈ opp(x)}. Thereafter, t ∈ µ(x) ⇔ µ t (x) = 1 ⇔ ∀{a, b} ∈ opp(x), µ t (a) = 1 or µ t (b) = 1 ⇔ ∀{a, b} ∈ opp(x), t ∈ µ(a) ∪ µ(b) ⇔ t ∈ {a,b}∈opp(x) µ(a) ∪ µ(b).
The case ε(m) = -1 is similar.

Let t ∈ T be a label. The set t µ = µ -1 t ({1}) is the support of t in the covering image µ. Thereby, the expressions x ∈ t µ , µ t (x) = 1 and t ∈ µ(x) are synonymous. We write t c µ for the set F n \ t µ . When there is no ambiguity, we write also t and t c instead of t µ and t c µ . The set ⊤ c = µ -1 (∅) is the background of µ. The support ⊥ contains the points in F n that are in the supports of every labels, in particular every proto-labels. Thus ⊥ is empty in a covering image obtained from a digital label image (since a digital label image is a partition of Z n , or a partition of a finite region of Z n ). Nevertheless, thanks to ⊥ , the dual of a covering image, defined by swapping the foreground and the background in each sheet of the image, is a covering image for the dual order on the lattice T , provided the lattice T is a power set lattice (otherwise, T is not atomistic for its dual order).

Simplicity

First, we recall some definitions and properties of the Alexandroff-Birkhoff topology of the cubical complexes. A more detailed presentation of these notions of topology can be found in our previous work on label images [START_REF] Mazo | Topology on digital label images[END_REF].

We write B(x) for the boundary of the face x, N(x) for the set of faces in F n whose boundary contains x. A point x ∈ F n is unipolar if N(x) has a minimum (for the incidence relation) or B(x) has a maximum. A subset X of F n is contractible (it has the homotopy type of a point) iff it can be shrunk to a unique point by a sequential (and greedy) removal of unipolar points.

In a binary image, a point x in the object is simple if its removal from the object "preserves topology" [START_REF] Kong | Digital topology: Introduction and survey[END_REF]. Since a covering image is a collection of binary images (the sheets), we can extend the notion of simple point to covering images: roughly speaking, in a covering image, a point is simple for a fiber S if it is simple in any sheet modified by the assignment µ(x) = S. In our framework, we use β-simple points. A point x ∈ F n is a β-simple point for a subset X of F n if one of the sets N(x) ∩ X or B(x) ∩ X is contractible. The β-simple points have the advantage to preserve topology twice. Indeed, in the one hand, F n can be equipped with the Alexandroff-Birkhoff topology whose open sets are the upsets of F n . Then, the deletion of a β-simple point x from a subset X of F n is a weak homotopy equivalence, that is, the inclusion i : X \ {x} → X induces a one-to-one correspondence between the connected components of both spaces and induces also isomorphisms between the homotopy groups of X \ {x} and X. Moreover, this is also true for the dual inclusion i ′ : F n \ X → F n \ (X \ {x}). On the other hand, one can associate to any subset X of F n an Euclidean set, denoted |K(X)|, which is the realization of a simplicial complex. The deletion from X of a β-simple point x induces a strong deformation retraction from |K(X)| to |K(X \ {x})|. Furthermore, this is also true for the complements (in R n ) of these realizations but, possibly, in a non-monotonic manner.

Eventually, we can give the definition of a simple point in a covering image.

Definition 2 (Simple point). Let S ∈ G T be a fiber. A point x ∈ F n is simple for (the fiber) S if the following two conditions are verified:

(i) for any label u ∈ µ(x) such that u / ∈ S, x is β-simple for the set u or for the set u c ∪ {x};

(ii) for any label u / ∈ µ(x) such that u ∈ S, x is β-simple for the set u ∪ {x} or for the set u c .

The previous definition, and the properties of β-simple points, ensures that, if a point is simple for the fiber S in the image µ, we can set µ(x) = S while preserving the topology of any region of interest, including the unions pointed out by the choice of the lattice T . Moreover, since the β-simplicity of a point x relies only on the examination of the sets N(x) and B(x), modifications of fibers over points in F n having the same dimension can be done in parallel, leading to well-balanced algorithms. Figure 5 gives some examples of thinnings, or growings, on a covering image using simple points.

Observe that most of the time the use of simple points to modify a covering image will lose the regularity of the image and will disable the possibility to extract from the covering image a digital label image (defined on Z n ) in a topologically sound manner (Figure 6 illustrates this point). Keeping the possibility to go back to Z n is a difficult issue. Some results can be found in our Ph.D. thesis [START_REF] Mazo | Déformations homotopiques dans les images digitales n-aires[END_REF], in French, but they concern only three dimensional images equipped with the (6, 18) adjacency pair, or its dual, and the statements are really tedious (fortunately, the implementation has turned out to be less painful than the statements and the proofs).

Implementation

In this section, we discuss the implementation of the framework.

We need to encode the lattice T , the fibers and some operations or predicates on fibers (at least union, intersection, is included in). Since the lattice T is atomistic, it is natural to encode the atoms, the proto-labels of the initial digital image, with a single bit in a bit field. Then the other labels in T can be encoded by a bitwise OR on the codes of the atoms of which they are the supremum. Table 1 gives the codes for the labels in the lattice T 1 defined on Figure 5.

In the sequel, we write [t] for the bit field representation of the label t. When the lattice T is the power set of the proto-labels, the supremum, resp. the Table 1: Label encoding for the lattice T 1 defined on Figure 5.

infimum, of a pair of labels is obtained by an OR, resp. an AND, operation on the codes of the two labels. Otherwise, we need an ordered list L of the elements of T for the order defined by the number of atoms, then the lexicographic order on the codes. For instance, the ordered list L for the lattice T 1 (Figure 5) is the one induced by Table 1. The code of the supremum of two labels t and u is the smallest element in the list L greater than the bitwise OR of [t] and [u]. Alike, the code of the infimum of t and u is the greatest element in the list L smaller than the bitwise AND of [t] and [u].

The fibers are unions of principal upsets t ↑ , t ∈ T . The upset t ↑ is encoded as the label t. In other words, an upset is encoded by the code of its minimal element. The other non-empty fibers, which are unions of principal upsets, are encoded as ordered lists of principal upsets (for the same order used for the list L). For a regular image, the length of the list depends on the choice of the adjacency relation and on the number of distinct labels in the neighborhood. For the digital image of Figure 5(a), the mean length of the lists of the ε-regular covering image is 1.13 when ε = (1, 1) and all the fibers are principal upsets when ε = (-1, -1). We need also a code for the empty fiber. Observe that in Table 1 the bit field 000000 codes the label ⊥, or the fiber T = ⊥ ↑ . Hence, it cannot be used to code the empty set. This is the reason why we adjoin another bit. Then, the bit field 1 . . . 1 (all bits set to '1') codes the empty set (the greater the code, the lesser the fiber).

To obtain a regular image from an initial digital label image, we need to compute iteratively unions and/or intersections of fibers (see Definition 1). The unions are performed by concatenating the lists of principal upsets and reordering. Moreover, from the list we delete the principal upsets that are included in an other element of the list: a principal upset t ↑ is included in the upset u ↑ iff the bit field ([t] AND [u]) is equal to [u]. The code of the intersection of two principal upsets t ↑ and u ↑ is the code of the supremum of the labels t and u (for t ↑ ∩ u ↑ = (t ∨ u) ↑ ). To intersect two fibers, we compute all the intersections of their principal upsets, delete the unnecessary elements and sort the resulting list.

The extraction of a sheet µ t (t ∈ T ) is done by testing for each x ∈ F n whether t ↑ is included in some principal upset u ↑ ∈ µ(x) .

To test whether a point x is simple for a fiber S, we have to examine the sets N(x) and B(x) in each sheet µ t where t ∈ (µ(x) \ S) ∪ (S \ µ(x)). This implies,a priori, to scan the lattice T , check whether each label is in µ(x) and not in S, or the converse, and, when the answer is positive, to look over the neighborhood of the face x in the selected sheet. If the lattice is the power set of a large amount of proto-labels, this could be long. Fortunately, the following proposition allows us to scan only a subset of the lattice T . The idea is that atoms that cannot be detected in the neighborhood of the point x are not 'useful' for the simplicity test. Hence, we collect all the atoms in the neighborhood of x together with those in S, that is we make an 'OR' on all the bit fields (but the empty set). Let A be the result. Clearly, for each point y in the neighborhood of x and for each minimal element v of µ(y), we have A(v) ⊆ A. Then, thanks to Proposition 2, we can ignore the atoms that are not in A since, for each label t such that A(t) A, there exists a label u in the sublattice of T generated by the atoms in A such that the two sheets µ t and µ u coincide in the neighborhood of x. In a standard label image, the test falls down to inspect labels which are supremums of very few atoms. Proposition 2. Let A ⊂ A(⊤) be a set of atoms in T and b ∈ A(⊤) be an atom not in A. Then, for any t ∈ T such that b ∈ A(t), there exists a label u ∈ T such that

• u ∈ { A ′ | A ′ ⊆ A} ;
• for any fiber S such that, for any minimal element v ∈ S, A(v) ⊆ A, we have t ∈ S ⇔ u ∈ S.

Proof. Let t be a label such that b ∈ A(t). We set A(t) = A 0 ∪ B where A 0 ⊆ A and B ∩ A = ∅ (obviously, we have b ∈ B). We set u = A 0 (thus u t). It is plain that u ∈ { A ′ | A ′ ⊆ A}.

Let S be a fiber such that, for any minimal element v ∈ S, A(v) ⊆ A. If u ∈ S, then t ∈ S (for u t and S is a fiber). Conversely, let us assume that t ∈ S. Let s be a minimal element in S such that s t. Clearly, we have A(s) ⊆ A(t). Since, by hypothesis, A(s) ⊆ A, we derive that A(s) ⊆ A 0 . Hence, s u. Thus, u ∈ S.

Conclusion

The model presented in this paper gives a way to encompass all the topological relations that characterize a label image. It provides a notion of simple point for a label which is based on solid foundations. From a theoretical point of view, it can help us to check what is precisely preserved or modified by a procedure. Furthermore, though the complexity of a label image (with all the intra-labels and inter-labels relations) is much higher than the complexity of a single object, we have seen that the implementation of a space of fibers can be done in an efficient way.

The next step will be to find procedures to get a regular covering image from a non-regular one. This will allow the extraction of a label image defined on Z n homotopically equivalent to a given covering image.

We would like to thank Professor C. Ronse who kindly reread this manuscript.

Figure 1 :

 1 Figure 1: (Color online) Motivation for a new framework.(a) A digital image λ in Z 2 with 2 labels r (red), g (green) and a background (not depicted). (b) The embedding of the image λ in F 2 , the space of cubical 2-complexes, obtained by applying the following membership rule: the label of a 0-, or 1-, dimensional point is the infimum, in the lattice (2 {r,g} , ⊆), of the labels of the surrounding 2-dimensional points. We have proved in[START_REF] Mazo | Digital imaging: A unified topological framework[END_REF] that this embedding preserves the connected components and the fundamental groups of the object and its complement when a binary digital image is interpreted with the (2n, 3 n -1)-adjacency pair. But, if we identify the two labels, that is if we consider a coarser partition of the space, the topology is not the same on these two images (we have one component on the left and two components on the right).

Figure 2 :

 2 Figure 2: (Color online) A lattice of binary images associated to a label image. (a) A digital label image with five (proto-)labels c, y, b, r, g respectively depicted in cyan, yellow, blue, red and green. (b) A lattice structure T whose atoms are c, y, b, r, g. (c-j) The collection of binary images associated to the lattice T (the binary image associated to ⊥ is not represented for it is a constant image, with no object).

Figure 3 :

 3 Figure 3: (Color online) Opposite points. Two opposite points in F 3 with respect to (a) a 2-point, (b) a 1-point, (c) a 0-point. The dashed boxes in (b) and (c) show other pairs of opposite points.

Figure 4 :

 4 Figure 4: Adjacency pairs and ε-regularity. The sheet µ r associated to the label r of the digital label image depicted on Figure 2. (a) The sequence ε is equal to (-1, -1) which corresponds to the choice of the (4, 8)-adjacency pair (the object of the binary image is open, it does not include its boundary). (b) The sequence ε is equal to (1, 1) which corresponds to the (8, 4)-adjacency pair (the object is closed so it includes its boundary).

2 Figure 5 :Figure 6 :

 256 Figure 5: (Color online) Thinning and growing using simple points.(a) A label image λ defined on Z 2 . There are six proto-labels: b (blue), g (green), o (orange), y (yellow), r (red) and p (pink). (b) The image λ has been transformed in a ε-regular covering image µ (with the sequence ε = (1, 1), which is associated to the (8, 4)-adjacency pair, and the proto-label power set lattice) then the support of the green label has been shrunk by use of simple points. More precisely, for each point x whose fiber µ(x) has a minimal element greater than the green proto-label, we look for a fiber S in its neighborhood that have all its minimal elements not greater than the green label. Then, if x is simple for S, we set µ(x) = S. (c-e) The image λ has been transformed in a ε-regular covering image µ with the sequence ε = (-1, -1) and the proto-label power set lattice (Figure (c)), the lattice T 1 (Figure (d)), the minimal lattice T 2 (Figure (e)). Then we have grown the background: for each point x that has a non-empty fiber and that is simple for the empty fiber, we set µ(x) = ∅.

A lattice is atomistic if any element, but the minimum, is a supremum of atoms.

A formal description of F n can be found in[START_REF] Mazo | Topology on digital label images[END_REF] but no knowledge of cubical complexes is needed to understand the remainder of the article.

* This work was supported by the Agence Nationale de la Recherche through contract ANR-2010-BLAN-0205-01.


Pierre Gillibert
email: gilliber@karlin.mff.cuni.cz

Miroslav Plo
email: miroslav.ploscica@upjs.sk

Š Čica

CONGRUENCE FD-MAXIMAL VARIETIES OF ALGEBRAS

Keywords: 2010 Mathematics Subject Classification. primary 06B10, secondary 08A30 distributive lattice, variety, congruence lattice

We study the class of finite lattices that are isomorphic to the congruence lattices of algebras from a given finitely generated congruencedistributive variety. If this class is as large as allowed by an obvious necessary condition, the variety is called congruence FD-maximal. The main results of this paper characterize some special congruence FD-maximal varieties.

Introduction

The study of congruence lattices is one of the central topics in universal algebra. For a class K of algebras we denote by Con K the class of all lattices isomorphic to Con A (the congruence lattice of an algebra A) for some A ∈ K. There are many papers investigating Con K for various classes K. However, the full description of Con K has proved to be a very difficult (and probably intractable) problem, even for the most common classes of algebras, like groups or lattices. A recent evidence of this is the solution of the Congruence Lattice Problem (CLP) by F. Wehrung [START_REF] Wehrung | A solution to Dilworth's congruence lattice problem[END_REF].

The difficulty in describing Con K leads to the consideration of the following problem.

Problem 1. Given the classes K and L of algebras, decide whether Con K ⊆ Con L.

Note that Problem 1 is a loosely formulated array of problems. A "real" problem which arises from Problem 1 is, for example, whether the containment Con K ⊆ Con L is decidable, for finitely generated varieties K and L.

The problem seems more tractable when both K and L are congruence-distributive varieties (equational classes) of algebras. In this case many partial results are available, as well as several promising strategies, for instance topological ( [START_REF] Ploščica | Separation properties in congruence lattices of lattices[END_REF]) or categorical ( [START_REF] Gillibert | Critical points of pairs of varieties of algebras[END_REF]).

The knowledge obtained so far shows the importance of critical points in the sense of the following definition. Let L c denote the set of all compact elements of an algebraic lattice L. Definition 1.1. (See [START_REF] Gillibert | Critical points of pairs of varieties of algebras[END_REF].) Let K and L be classes of algebras. The critical point of K under L, denoted by crit(K; L), is the smallest cardinality of L c for L ∈ Con K \ Con L (if Con K Con L) or ∞ (if Con K ⊆ Con L).

For most K and L, the critical point is finite or countably infinite. Examples of varieties with uncountable crit(K; L) has been found in [START_REF] Gillibert | Critical points of pairs of varieties of algebras[END_REF], [START_REF] Gillibert | Critical points between varieties generated by subspace lattices of vector spaces[END_REF] and [START_REF] Ploščica | Dual spaces of some congruence lattices[END_REF].

So far, most of the work on critical points has been devoted to distinguishing Con K and Con L in the case of an infinite critical point. The methods include using algebraic and topological invariants ( [START_REF] Ploščica | Separation properties in congruence lattices of lattices[END_REF], [START_REF] Ploščica | Separation in distributive congruence lattices[END_REF], [START_REF] Ploščica | Iterative separation in distributive congrurnce lattices[END_REF]), refinement properties( [START_REF] Wehrung | Non-measurability properties of interpolation vector spaces[END_REF], [START_REF] Ploščica | Congruence lattices of free lattices in non-distributive varieties[END_REF], [START_REF] Ploščica | Local separation in distributive semilattices[END_REF]) and lifting of diagrams by the Con functor ( [START_REF] Gillibert | Critical points of pairs of varieties of algebras[END_REF], [START_REF] Gillibert | Critical points between varieties generated by subspace lattices of vector spaces[END_REF]). The case where K and L are both finitely generated varieties of lattices has been particularly studied. For instance, if K is neither contained in L nor its dual then crit(K; L) ≤ ℵ 2 ([3]).

The case of a finite critical point is also interesting. If K is a finitely generated congruence-distributive variety and L is a finite distributive lattice, then there is an algorithm deciding whether L ∈ Con K. (For instance, see [START_REF] Ploščica | Finite congruence lattices in congruence distributive varieties[END_REF].) However, this does not provide a description of the class Con K and we have no algorithm deciding whether crit(K; L) is finite, even if both K and L are finitely generated and congruence-distributive.

This paper is devoted to the finite version of the Problem 1, that is, to the characterization of the finite members of Con K and to comparing the finite parts of Con K and Con L for different K and L. Even this task is difficult and we can present a satisfactory solution only in some very special cases. However, we believe that the ideas contained in this paper can be applied in more general situations and can contribute significantly to the solution of Problem 1 (for congruence-distributive and finitely generated varieties K and L).

Basic Concepts

Now we recall basic denotations and facts. We assume familiarity with basic concepts from lattice theory and universal algebra. For all undefined concepts and unreferenced facts we refer to [START_REF] Grätzer | General Lattice Theory[END_REF] and [START_REF] Mckenzie | Algebras, lattices, varieties I[END_REF].

If f : X → Y is a mapping and Z ⊆ X, then f ↾Z denotes the restriction of f to Z. Furthermore, Ker f (the kernel of f ) is the binary relation on X defined by Ker

f = {(x, y) ∈ X 2 | f (x) = f (y)}. If f is a homomorphism of algebras, then Ker f is a congruence. Given maps f, g : A → B and X ⊆ A, we denote (f, g)[X] = {(f (x), g(x)) | x ∈ X}.
For α ∈ Con A and x ∈ A, we denote by x/α the congruence class containing x.

We denote by SI(V) the class of all subdirectly irreducible members of a variety V.

If a is an element of a lattice (or an ordered set) L, then we denote ↑a = {b ∈ L | b ≥ a}. The smallest and the greatest element of any lattice (if they exist) will be denoted by 0 and 1, respectively. The two-element lattice will be denoted by 2 = {0, 1}. An element a of a lattice L is called completely meet-irreducible iff a = X implies that a ∈ X, for every subset X of L. The greatest element of L is not completely meet-irreducible. Let M(L) denote the set of all completely meet-irreducible elements of L. Clearly, α ∈ Con A is completely meet-irreducible if and only if the quotient algebra A/α is subdirectly irreducible. Hence, we have the following easy fact. Lemma 2.1. Let V be a variety and L = Con A for some A ∈ V. Then for every x ∈ M(L), the lattice ↑x is isomorphic to Con T for some T ∈ SI(V).

This lemma provides a basic information about congruence lattices of algebras in V. It is especially effective in the case of a congruence-distributive variety V and a finite lattice L, because finite distributive lattices are determined uniquely by the ordered sets of their meet-irreducible elements.

There are varieties for which the necessary condition of Lemma 2.1 (for distributive lattices) is also sufficient on the finite level. We call such varieties congruence FD-maximal Hence V is congruence FD-maximal if for every finite distributive lattice L the following conditions are equivalent:

(i) L ∈ Con V; (ii) ↑x ∈ Con V for each x ∈ M(L).
Remark 2.2. Notice that the equivalence of (i) and (ii) in the definition of congruence FD-maximality, only holds for finite distributive lattices. For example D, the variety of distributive lattices, is congruence FD-maximal. The finite congruence lattices in Con D are the finite Boolean algebras. The only subdirectly irreducible lattice in D is the two-element lattice.

Denote by M 3 the lattice of length two with three atoms. It is easy to see that ↑x is the two-element lattice, for each meet-irreducible x ∈ M 3 , which is isomorphic to Con 2. However M 3 does not belong to Con D.

There also exists an infinite algebraic distributive lattice L, such that ↑x is the two-element lattice, for each meet-irreducible x ∈ L, but L does not belongs to Con D.

Example 2.3. The variety of all lattices is congruence FD-maximal, as each finite distributive lattice is isomorphic to the congruence lattice of a lattice (the first published proof is due to G. Grätzer and E. T. Schmidt in [START_REF] Grätzer | On congruence lattices of lattices[END_REF]). For similar reason the variety of all modular lattices is congruence FD-maximal (see [START_REF] Schmidt | Every finite distributive lattice is the congruence lattice of some modular lattice[END_REF]).

The limit construction

The algebras with a prescribed congruence lattices can be often constructed as limits of suitable diagrams. Let us recall the construction from [START_REF] Ploščica | Finite congruence lattices in congruence distributive varieties[END_REF].

An ordered diagram of sets is a triple (P, A, F), where P is a partially ordered set, A = (A p ) p∈P is a family of sets indexed by P and F = (f pq ) p≤q in P is a family of functions f pq : A p → A q such that (1) f pp is the identity map for every p ∈ P ;

(2) f qr f pq = f pr for every p, q, r ∈ P , p ≤ q ≤ r. For any ordered diagram of sets we define its limit as lim(P, A, F) = {a ∈ p∈P A p | a q = f pq (a p ) for every p ≤ q in P }.

Thus, our limit is the limit in the sense of the category theory (applied to the category of sets). Moreover, if A p are algebras of the same type and f p,q are homomorphisms, then the limit is a subalgebra of the direct product. In universal algebra, this construction is often called the inverse limit (see [START_REF] Grätzer | Universal Algebra[END_REF]). Definition 3.1. An ordered diagram of sets (P, A, F) is called admissible if the following conditions are satisfied:

(i) for every p ∈ P and every u ∈ A p there exists a ∈ lim(P, A, F) such that a p = u; (ii) for every p ≤ q in P , there exist a, b ∈ lim(P, A, F) such that a p = b p and a q = b q .

Theorem 3.2 ([12, Theorem 2.4]). Let V be a congruence-distributive variety and let L be a finite distributive lattice. Set P = M(L). For every p ∈ P let A p ∈ V and for every p ≤ q in P let f pq : A p → A q be a homomorphism such that (P, A, F) is an admissible ordered diagram of sets (with A = (A p ) p∈P and F = (f pq ) p≤q in P and, moreover, (*) for all p ∈ P , the sets {Ker(f pq ) | q ≥ p in P } and M (Con A p ) coincide.

Then lim(P, A, F) is an algebra whose congruence lattice is isomorphic to L.

We demonstrate the use of this theorem in the following easy case.

Theorem 3.3. Let V be a congruence-distributive variety such that Con C is a finite chain for every C ∈ SI(V). Suppose that n = max{length(Con C) | C ∈ SI(V)} exists. Let L be a finite distributive lattice. The following conditions are equivalent.

(i) L ∈ Con V;

(ii) For every x ∈ M(L), the poset ↑x is a chain of length at most n.

Proof. The necessity of (ii) follows directly from Lemma 2.1. Conversely, suppose that L satisfies (ii). We construct an algebra A ∈ V with Con A isomorphic to L.

There exist C ∈ V whose congruence lattice is an (n + 1)-element chain

α 0 > α 1 > • • • > α n .
For every i = 1, . . . , n the quotient algebra C i = C/α i is subdirectly irreducible and Con C i is the (i + 1)-element chain. Further, for every j ≤ i we have a natural (surjective) homomorphism

g ij : C i → C j .
We define the following diagram indexed by the ordered set P = M(L). For every p ∈ P , ↑p is a chain. We denote the cardinality of this chain by i(p) and set A p = C i(p) . For every p ≤ q in P , we have i(p) ≥ i(q); we set f pq = g i(p),i(q) . Let A be the limit of this diagram. It remains to check that the assumptions of Theorem 3.2 are satisfied.

For every x ∈ C consider (x/α i(p) ) p∈P ∈ p∈p A p . It is clear that this is an element of A. All such elements show that all projections A → A p are surjective.

To prove the second admissibility condition, let p, q ∈ P such that p ≤ q. Let j = i(q). Since j > 0 and α j α j-1 , it is possible to choose x, y ∈ C with x/α j = y/α j and x/α j-1 = y/α j-1 . We define elements a = (a t ), b = (b t ) ∈ t∈P A t by

a t = x/α i(t) if t ≤ q y/α i(t) if t ≤ q, b t = y/α i(t)
, for every t ∈ P .

It is easy to see that a, b ∈ A, a p = b p , a q = b q . Indeed, the only nontrivial point is to show that f rs (a r ) = a s when r ≤ q, s ≤ q, r ≤ s. Since ↑r is a chain, we have q < s, so j = i(q) > i(s), and

f rs (a r ) = f qs (f rq (a r )) = f qs (a q ) = g j,i(s) (x/α j ) = g j-1,i(s) (x/α j-1 ) = g j-1,i(s) (y/α j-1 ) = y/α i(s) = a s .
Thus, our diagram is admissible. Finally, we check the condition (*). For every p ∈ P we have M(Con A p ) = {α j /α i(p) | j = 1, . . . , i(p)}, which is exactly the set of the kernels of homomorphisms f pq = g ij .

The assumptions of Theorem 3.3 are satisfied for instance for any finitely generated variety of modular lattices. Every finite subdirectly irreducible modular lattice is simple, hence its congruence lattice is the two-element chain.

Another example is the variety of Stone algebras, generated by the three-element pseudocomplemented lattice S = ({0, b, 1}; ∧, ∨, 0, 1, ′ ), with 0 < b < 1. The congruence lattice of S is the three-element chain. The only other irreducible member in this variety is the two-element Boolean algebra, which is simple.

So, in the terminology from the introduction, any finitely generated variety of modular lattices, and the variety of Stone algebras are all congruence FD-maximal.

α β ❅ ❅ ❅ ❅ ❅ ❅ ✉ ✉ ✉ ✉ ✉ Figure 1. The lattice V .

The case of V-varieties

In this section we discuss the simplest case not covered by Theorem 3.3. We consider finitely generated congruence-distributive varieties, in which every subdirectly irreducible algebra is simple, or has its congruence lattice isomorphic to the lattice V depicted in Figure 1.

In the sequel, such varieties will be called V-varieties. The similarity type of a V-variety is not assumed finite. If V is a V-variety then, by Lemma 2.1, every finite distributive L ∈ Con V satisfies (**) the ordered set M(L) is a disjoint union of two antichains N ∪ D such that for every n ∈ N there are exactly two d ∈ D with n < d.

Indeed, if L = Con A, A ∈ V, and α ∈ M(L), then α ∈ N when Con(A/α) ∼ = V and α ∈ D when A/α is simple. It follows that for a V-variety V, if every finite distributive lattice satisfying (**) belongs to Con V, then V is congruence FDmaximal.

Consider the smallest nonmodular lattice variety N 5 generated by the lattice N 5 depicted in Figure 2. By [12, Theorem 3.1] the condition (**) is equivalent to saying that L belongs to Con N 5 . Therefore N 5 is congruence FD-maximal. It follows that a V-variety V is congruence FD-maximal if and only if each finite lattice in Con N 5 belongs to Con V.

Denote by L 1 the variety of lattices generated by L 1 , and by L 2 the variety of lattices generated by L 2 . Given any finitely generated variety of modular lattices M, the varieties of lattices M∨N 5 , M∨L 1 , and M∨L 2 are congruence FD-maximal V-varieties.

Let E be a subset of B × B for some set B. Further, let X be a set and let F be a set of functions X → B. We say that F is E-compatible if there exists a linear order (i) There exist arbitrarily large finite E-compatible sets of functions.

⊏ on F such that (f, g)[X] = E for all f ⊏ g in F. The set F is called strongly E-compatible if, in addition, Ker f {Ker g | g ∈ F \ {f }} for every f ∈ F.
(ii) There exist arbitrarily large finite strongly E-compatible sets of functions.

(iii) For every (a, b) ∈ E there are x, y, z ∈ B such that (x, x), (y, y), (z, z), (x, y), (x, z), (y, z), (x, a), (x, b), (a, y), (y, b), (a, z), (b, z) ∈ E.

N 5 ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ✉ ✉ ✉ ✉ ✉ 0 1 b a c L 1 ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ✉ ✉ ✉ ✉ ✉ ✉ ✉ L 2 ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ❅ ✉ ✉ ✉ ✉ ✉ ✉ ✉ Figure 2.
Small lattices generating V-varieties.

Proof. Suppose first that (i) holds. Let (a, b) in E. Let n = 3k + 5, where k is the cardinality of B. By our assumption, there exists a set X and an E-compatible

set F = {f 1 , . . . , f n } of functions X → B such that (f i , f j )[X] = E for all i < j in {1, . . . , n}. Especially, set i = k + 2, j = 2k + 4. Since (a, b) ∈ E = (f i , f j )[X], there exists t ∈ X such that f i (t) = a and f j (t) = b.
By the pigeonhole principle, there are l < m in {1, . . . , k

+ 1} such that f l (t) = f m (t). We put x = f m (t), so (x, x) = (f l (t), f m (t)) ∈ E, (x, a) = (f m (t), f i (t)) ∈ E, and (x, b) = (f m (t), f j (t)) ∈ E.
Further, there are p < q in {k + 3, . . . , 2k + 3} such that f p (t) = f q (t). We put y = f p (t). Similarly as above we can check that (y, y), (a, y), (y, b), (x, y) ∈ E.

Finally, there are r < s in {2k + 5, . . . , 3k + 5} such that f r (t) = f s (t). We put z = f r (t) and obtain that (z, z), (x, z), (y, z), (a, z), (b, z) ∈ E. This completes the proof of the implication (i)=⇒(iii).

Suppose now that (iii) holds. Let k be a natural number. We need to construct a set X and a strongly E-compatible set {f 1 , . . . , f k } of functions X → B.

Given (a, b) ∈ E, we fix x ab , y ab , z ab ∈ B that satisfy (iii). We set

H = {1/2, 1, 3/2, 2, 5/2, . . ., k, k + 1/2} and U = {(i, j) | i < j in H} Put X = E × U . Given m ∈ {1, . . . , k}, (a, b) ∈ E, and (i, j) ∈ U , we set f m (a, b, i, j) =                x ab if m < i a if m = i y ab if i < m < j b if m = j z ab if m > j.
This defines a map f m : X → B for each m ∈ {1, . . . , k}. Let m < n in {1, . . . , k}. Given (a, b) ∈ E and (i, j) ∈ U , it is easy to see that (f m (a, b, i, j), f n (a, b, i, j

)) ∈ E, therefore the containment (f m , f n )[X] ⊆ E holds. Conversely let (a, b) ∈ E, notice that f m (a, b, m, n) = a and f n (a, b, m, n) = b, it follows that (a, b) ∈ (f m , f n )[X]. We deduce that (f m , f n )[X] = E for all n < m in {1, . . . , k}. Therefore the set {f 1 , . . . , f k } is E-compatible.
Further, choose (a, b) ∈ E with a = b. Then for every m ∈ {1, . . . , k} we have f m (a, b, m -1/2, m) = b = a = f m (a, b, m, m + 1/2), so the pair ((a, b, m -1/2, m), (a, b, m, m + 1/2)) does not belong to Ker f m . On the other hand, it is easy to see that this pair belongs to Ker f n for every n = m. Thus, our set is strongly E-compatible and we have proved the implication (iii)=⇒(ii). Since the implication (ii)=⇒(i) is trivial, the proof is complete. Theorem 4.2. Let V be a V-variety. The following conditions are equivalent.

(1) V is congruence FD-maximal.

(2) There exist B, C ∈ V and surjective homomorphisms h 0 , h 1 :

C → B such that (i) B is simple, Con C ∼ = V ;
(ii) Ker(h 0 ) = Ker(h 1 ); (iii) there are arbitrarily large E-compatible sets of functions for the set

E = (h 0 , h 1 )[C] = {(h 0 (c), h 1 (c)) | c ∈ C} ⊆ B × B.
Remark 4.3. Let us note, in the context of Theorem 4.2 that Ker(h 0 ) and Ker(h 1 ) correspond to congruences α, β ∈ V . Also note that, V being a finitely generated congruence-distributive variety, the algebras B and C are both finite.

Proof of Theorem 4.2. Suppose that (1) holds. As V is congruence-distributive and finitely generated, it can only contain finitely many (up to isomorphism) algebras C 1 , . . . , C m whose congruence lattice is isomorphic to V , and finitely many (up to isomorphism) simple algebras B 1 , . . . , B l . Moreover the algebras C 1 , . . . , C m and B 1 , . . . , B l are all finite. Let Q be the set of all ordered pairs Q = (h 0 , h 1 ) of surjective homomorphisms h 0 : C i → B i0 , h 1 : C i → B i1 for some i, i 0 , i 1 , such that Ker(h 0 ) = Ker(h 1 ). For every such Q = (h 0 , h 1 ) we denote

E Q = (h 0 , h 1 )[C i ].
Clearly, every C i occurs in some Q. Notice that some C i can occur more than twice. This is because the algebras B i can have proper automorphisms and then the homomorphisms h 0 , h 1 are not determined uniquely by their kernels. Denote by r the cardinality of Q.

For contradiction, suppose that (2) is not valid, that is, for every Q = (h 0 , h 1 ) ∈ Q either h 0 and h 1 have distinct ranges or the size of a set of E Q -compatible functions is bounded, say by a number n Q . Choose a natural number n with n > 2 and n > n Q for every defined n Q . By the Ramsey's Theorem, we can choose k such that every complete graph with k vertices and edges colored by r (the cardinality of Q) colors has a full subgraph with n vertices, in which every edge has the same color.

Consider the finite distributive lattice L such that M(L) is the disjoint union of two discrete sets D = {d 1 , . . . , d k } and N = {x ij | 1 ≤ i < j ≤ k}, with the d i (resp., the x ij ) pairwise distinct, and the only relations

x ij < d i , d j for 1 ≤ i < j ≤ k.
According to our assumption, L is representable as Con A for some finite A ∈ V. Every quotient A/x ij must be isomorphic to some C t and every quotient A/d i is isomorphic to some B u . Let us fix the isomorphisms g i : A/d i → B u and

g ij : A/x ij → C t . Further, let p ij : A/x ij → A/d i and q ij : A/x ij → A/d j be the natural projections. Then (g i p ij g -1 ij , g j q ij g -1 ij ) is an element of Q.
Let us consider the complete graph with vertices d 1 , . . . , d k . To every edge {d i , d j }, i < j, we have assigned an element of Q. By the definition of k, there is a n-element subset I ⊆ {1, . . . , k} such that the same Q = (h 0 , h 1 ) ∈ Q is assigned to every i < j in I. To simplify the notation, assume that I = {1, . . . , n}.

The algebras A/x ij (i < j in I) are all isomorphic to the same algebra C ∈ {C 1 , . . . , C m }. Since n ≥ 3, the algebras A/d i (i ∈ I) must be isomorphic to the same algebra B ∈ {B 1 , . . . , B l }, hence both h 0 and h 1 have range B. Therefore, the set E Q ⊆ B 2 is defined. For every i ∈ I let f i be the natural projection A → A/d i composed with the isomorphism g i : A/d i → B. The maps f i are pairwise distinct (they have different kernels) and we claim that the family

{f i | i ∈ I} is E Q - compatible. Let i < j in I, hence h 0 = g i p ij g -1 ij and h 1 = g j q ij g -1 ij . For every a ∈ A we have (f i (a), f j (a)) = (h 0 (b), h 1 (b)) ∈ E Q , where b = g ij (a xij ) ∈ C. Since every element of E Q is of this form, we obtain that (f i , f j )[A] = {(f i (a), f j (a)) | a ∈ A} = E Q .
So, we have proved that the family

{f i | i ∈ I} is E Q -compatible. This is a contradiction with the inequality n > n Q .
Conversely, suppose that (2) holds. Let L be a finite distributive lattice with the property that the ordered set M(L) consists of two antichains N and D such that for every n ∈ N there are exactly two

d 1 , d 2 ∈ D with n < d 1 , d 2 . We construct a finite algebra A ∈ V such that Con A is isomorphic to L.
According to our assumption, there are algebras B, C ∈ V and homomorphisms h 0 , h 1 : C → B satisfying (i), (ii), and (iii). There is a set X and an E-compatible family of functions X → B of cardinality equal to the cardinality of D. To simplify the notation, we identify these functions with elements of D. Because of Lemma 4.1 we can assume that the family is strongly E-compatible. We fix a linear order ⊏ on D such that (d, e)[X] = E for all d ⊏ e in D, such order exists by the definition of E-compatibility.

We use the limit construction described in the previous section, with M(L) as the index set. We put

A p = B if p ∈ D C if p ∈ N .
For every n ∈ N there are d ⊏ e in D, with n < d, e. We set f nd = h 0 and f ne = h 1 . Let A be the limit of the above defined diagram.

Our diagram clearly satisfies the condition (*) of Theorem 3.2. We need to check the admissibility. Given x ∈ X, we denote by U (x) the set of all y ∈ p∈M(L) A p such that y d = d(x) for all d ∈ D and (h 0 (y n ), h 1 (y n )) = (d(x), e(x)) for all n ∈ N , where d ⊏ e in D with n < d, e.

Let e(y n )). This defines an element y ∈ U (x), therefore U (x) is not empty.

y ∈ U (x), let n ∈ N , let d ⊏ e in D such that n < d, e. Notice that f nd (y n ) = h 0 (y n ) = d(x) = y d and f ne (y n ) = h 1 (y n ) = e(x) = y e . It follows easily that y belongs to A. Therefore U (x) ⊆ A. Set U = x∈X U (x), note that U ⊆ A. Let x ∈ X. Given d ∈ D, set y d = d(x). Let n ∈ N and d ⊏ e in D such that n < d, e, notice that (h 0 , h 1 )[X] = E = (d, e)[C], therefore there is y n ∈ C such that (h 0 (x), h 1 (x)) = (d(y n ),
Let c 0 ∈ C, let n 0 ∈ N , let d 0 ⊏ e 0 in D such that n 0 < d 0 , e 0 . As (h 0 , h 1 )[C] = E = (d 0 , e 0 )[X], there is x ∈ X such that (d 0 (x), e 0 (x)) = (h 0 (c 0 ), h 1 (c 0 )). With a construction similar to the previous one we obtain y ∈ U (x), moreover we can choose y such that y n0 = c 0 . Therefore, for all c ∈ C, for all n ∈ N , there is y ∈ U such that y n = c. With a similar argument we obtain that, for all b ∈ B, for all d ∈ D, there is y ∈ U such that y d = b.

This shows Definition 3.1(i). To show the second admissibility condition, let p q in M(L). We distinguish several cases. a) Let p, q ∈ D. The strong compatibility implies that Ker p Ker q, so there is (x, y) ∈ Ker p \ Ker q. Pick x * ∈ U (x) and y * ∈ U (y), then x * p = y * p and x * q = y * q . b) Let p ∈ N , q ∈ D. There are d ⊏ e in D with p < d, e. Clearly, q / ∈ {d, e} and by the strong compatibility there exists (x, y) ∈ Ker d ∩ Ker e, with (x, y) / ∈ Ker q. Then (d(x), e(x)) = (d(y), e(y)), so there are x * ∈ U (x) and y * ∈ U (y) such that x * p = y * p . On the other hand, (x, y) / ∈ Ker q means that x * q = y * q . c) Finally, let q ∈ N . Since the algebra A q = C is subdirectly irreducible, there are elements u, v ∈ A q such that u = v and the pair (u, v) belongs to the monolith of A q . There is y ∈ U with y q = u. Define an element t ∈ r∈M(L) A r by t r = v if r = q y r otherwise.

Then t ∈ A. Indeed, let r, s ∈ M(L), r < s. The equality f rs (t r ) = t s follows from y ∈ A, except for the case r = q. However, f qs is either h 0 or h 1 , and the pair (u, v) belongs to the kernels of both, so f qs (t q ) = f qs (v) = f qs (u) = f qs (y q ) = y s = t s . Thus, t ∈ A. Clearly, t q = y q and t p = y p . The proof is complete.

Theorem 4.2 in connection with Lemma 4.1 enables to decide whether a given V-variety is congruence FD-maximal. As an example, consider the variety N 5 . The algebra N 5 has congruence lattice isomorphic to V , both its simple quotients are isomorphic to {0, 1}, and the homomorphisms h 0 , h 1 : N 5 → {0, 1} are given by h 0 (0

) = h 0 (a) = h 0 (c) = 0, h 0 (b) = h 0 (1) = 1, h 1 (b) = h 1 (0) = 0, h 1 (a) = h 1 (c) = h 1 (1) = 1.
Hence, E = {(0, 0), (0, 1), (1, 0), (1, 1)} and it is easy to see that 4.1(iii) is satisfied. (Indeed, 4.1(iii) always holds for reflexive E.) As seen at the beginning of this section, we already knew, from [12, Theorem 3.1], that N 5 is congruence FD-maximal.

Congruence non FD-maximal examples

It is not difficult to construct a V-variety which is not congruence FD-maximal. For instance, consider the lattice N 5 endowed with the additional unary operation f with f 2) This algebra has the same congruences as the lattice N 5 , so its congruence lattice is isomorphic to V . One of the simple quotient of this algebra is isomorphic to the lattice {0, 1} with the identity as additional operation. The other simple quotient is the lattice {0, 1} with the map permuting 0 and 1 as additional operation. The two simple quotients of this algebra are not isomorphic. By Theorem 4.2, the variety V generated by this algebra is not congruence FD-maximal. (Of course, a detailed proof of this fact requires checking that V does not contain any other algebra with congruence lattice isomorphic to V , but this is an easy consequence of Jónsson's Lemma.)

(0) = f (b) = b, f (a) = f (c) = f (1) = 1. (See the picture of N 5 in Figure
Now we present a more sophisticated example. Let C be the lattice depicted in Figure 3 with two additional unary operations f and g. uniquely (up to interchanging) by h 0 (0) = h 0 (x) = h 0 (y) = h 0 (z) = 0, h 0 (u) = h 0 (v) = h 0 (w) = a, h 0 (t) = b, h 0 (1) = 1, h 1 (1) = h 1 (t) = h 1 (w) = h 1 (z) = 1, h 1 (u) = h 1 (v) = h 1 (y) = b, h 1 (x) = a, h 1 (0) = 0. Hence, E = {(0, 0), (0, a), (0, b), (0, 1), (a, b), (a, 1), (b, 1), (1, 1)}.

0 x y u v z w t 1 f, g f, g f, g f f g g g g g g f f f f f (0) = 0, f (x) = y, f (y) = f (z) = z f (u) = f (v) = f (w) = t, f (t) = f (1) = 1 g(1) = 1, g(t) = w, g(w) = g(z) = z g(u) = g(v) = g(y) = x, g(x) = g(0) = 0
The pair (a, b) ∈ E shows that 4.1(iii) is not satisfied, as there is no t ∈ B such that (a, t) ∈ E and (t, b) ∈ E. So the set E does not allow arbitrarily large sets of E-compatible functions. Since the variety C does not provide any other candidates for C, B, h 0 and h 1 , 4.2(2) is not satisfied, so C is not congruence FD-maximal.

Conclusion

The characterization of congruence FD-maximal V-varieties helps to decide whether several critical points are finite or not.

Let V be a V-variety. Let W be a congruence FD-maximal V-variety. It is easy to see that crit(V; W) ≥ ℵ 0 , moreover crit(W; V) ≥ ℵ 0 if and only if V is congruence FD-maximal. For example, denote by V the variety generated by the algebra C in Section 5 (see Figure 3). We have seen that N 5 is congruence FD-maximal and V is not congruence FD-maximal, it follows that crit(N 5 ; V) < ℵ 0 .

When both varieties are not congruence FD-maximal, we cannot even decide whether the critical point is finite or not.

Problem 2. Given a V-variety V, which is not congruence FD-maximal. Find a characterization of the finite lattice in Con V.

The lattice V (cf. Figure 1) is the smallest distributive lattice, which is not a chain, isomorphic to the congruence lattice of a subdirectly irreducible algebra. It would be interesting to study other examples. Problem 3. Characterize finitely generated congruence FD-maximal varieties.

Lemma 4 . 1 .

 41 Let B be a finite set, let E ⊆ B × B and suppose that there is (u, v) ∈ E with u = v. Then the following condition are equivalent.

Figure 3 .

 3 Figure 3. An algebra generating a V-variety.

Figure 4 .

 4 Figure 4. A simple quotient of C.

Supported by VEGA Grant 2/0194/10 and the institutional grant MSM 0021620839.