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

HAL
open science

# On a special class of median algebras

Miguel Couceiro, Gerasimos C. Meletiou

► To cite this version:

Miguel Couceiro, Gerasimos C. Meletiou. On a special class of median algebras. Miskolc Mathematical Notes, 2017, 18 (1), pp.167-171. 10.18514/MMN.2017.1799. hal-01248142

HAL Id: hal-01248142

https://inria.hal.science/hal-01248142

Submitted on 23 Dec 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
# ON A SPECIAL CLASS OF MEDIAN ALGEBRAS

MIGUEL COUCEIRO AND GERASIMOS C. MELETIOU

**Abstract.** In this short note we consider a class of median algebras, called (1, 2 : 3)-semilattices, that is pertaining to cluster analysis. Such median algebras arise from a natural generalization of conservativeness, and their description is given in terms of forbidden substructures.

## 1. PRELIMINARIES: MEDIAN ALGEBRAS

Recall that a median algebra is a structure $\mathbf{A} = \langle A, \mathbf{m} \rangle$ for a nonempty set $A$ and a ternary symmetric operation $\mathbf{m}: A^3 \to A$, called median, that is a near-unamplitude (i.e., $\mathbf{m}(x, x, y) = x$) and such that for every $x, y, z, t, u \in A$,

$$ \mathbf{m}(\mathbf{m}(x, y, z), t, u) = \mathbf{m}(x, \mathbf{m}(y, t, u), \mathbf{m}(z, t, u)). $$

Alternative axiomatizations were also proposed [2, 9, 10]. In particular, it can be shown that the following equation

$$ \mathbf{m}(\mathbf{m}(x, y, z), y, z) = \mathbf{m}(x, y, z) $$

holds in every median algebra.

Such algebras have been studied by several authors and they were shown to be tightly related to several ordered structures such as semilattices and distributive lattices. Indeed, Sholander [14] showed that each element $a$ of a median algebra $\mathbf{A}$ gives rise to a median semilattice $\langle A, \leq_a \rangle$ where $\leq_a$ defined by

$$ x \leq_a y \iff \mathbf{m}(a, x, y) = x. $$

In such a semilattice, $a$ is the bottom element $\mathbf{A}_a := \langle A, \leq_a \rangle$ and the induced semilattice operation $\wedge_a$ is then given by $x \wedge_a y = \mathbf{m}(a, x, y)$. Furthermore, its principal ideals

$$ \downarrow x := \{y \in A : y \leq_a x\} $$

are distributive lattices. Conversely, if a $\wedge$-semilattice has the property that for any $a, b, c \in A$, the three elements $a \wedge b, b \wedge c, c \wedge a$ have a supremum whenever each pair of them is bounded above, then a median operation can be defined by

$$ (1.1) \qquad \mathbf{m} \leq (x, y, z) = (x \wedge y) \vee (x \wedge z) \vee (z \wedge y), $$

for every $x, y, z \in A$. In fact, as shown in [1], for every median algebra $\mathbf{A} = \langle A, \mathbf{m} \rangle$ and every $a \in A$, we have that $\mathbf{m} = \mathbf{m}_{\leq_a}$.

Similarly, every distributive lattice gives rise to a median algebra using (1.1), and the converse also holds whenever there are $a, b \in A$ such that $\mathbf{m}(a, x, b) = x$ for every $x \in A$.

In the case of discrete structures, median algebras can also be thought of as certain special graphs. A median graph is a connected connected graph (i.e., for every pair of vertices there is a path connecting them) that has the property that for any three vertices $a, b, c$, there is exactly one vertex $x$ that minimizes the sum of the distances to $a, b$ and $c$. It was shown in [1] that every median semilattice whose intervals are finite has a covering graph (i.e., undirected HASSE diagram) that is median, and

<footnote>Date: August 20, 2015, 10:43.</footnote>
<figure><img src="image_2.png" /><figcaption>FIGURE 1. Examples of median semilattices: **A** is a (1 : 3)-median semilattice, **A'** is a (2 : 3)-median semilattice that is not (1 : 3), and **A''** is a (1, 2 : 3)-median semilattice that is not (2 : 3).</figcaption></figure>

that every median graph is the covering graph of a median semilattice. For further background see, e.g., [2].

In this short note we are interested in some special classes of median algebras that are pertaining to cluster analysis, e.g., in the case of overlapping clusters. We say that a median semilattice $\mathbf{A} := \langle A, \leq \rangle$ (thought of as a median algebra $\mathbf{A} = \langle A, \mathbf{m} \rangle$) is

(i) a (1 : 3)-median semilattice if for every $x, y, z \in A$,

$$ \mathbf{m}(x, y, z) \in \{x, y, z\}; $$

(ii) a (2 : 3)-median semilattice if for every $x, y, z \in A$,

$$ \mathbf{m}(x, y, z) \in \{x \wedge y, y \wedge z, z \wedge x\}; $$

(iii) a (1, 2 : 3)-median semilattice if for every $x, y, z \in A$,

$$ \mathbf{m}(x, y, z) \in \{x, y, z, x \wedge y, y \wedge z, z \wedge x\}. $$

Note that, apart from the 4-element Boolean lattice, every (1 : 3)-median semilattice is a (2 : 3)-median semilattice. Also, every (1 : 3)-median semilattice and every (2 : 3)-median semilattice is a (1, 2 : 3)-median semilattice.

However, the converse statements are not true as it is illustrated by Figure 1.

**Remark 1.1.** Note that (1 : 3)-median semilattices are exactly those median algebras whose subsets are themselves median (sub)algebras. In the terminology of [3], they are median algebras with *msd* (median stabilization degree) equal to 0.

The median semilattices in (i) and (ii) were described in terms of forbidden forbidden substructures in [6] and [5], respectively. In this paper we provide a similar description for (1, 2 : 3)-median semilattices.

## 2. MAIN RESULT

In [6], (1 : 3)-median semilattice were referred to as *conservative* median algebras, and it was shown that, apart from the 4-element Boolean algebra, they can be thought of as chains. (Curiously, the 4-element Boolean algebra also appears as an exceptional in another area of the theory of ordered sets; see e.g. [8].) Equivally, (1 : 3)-median semilattices were shown to coincide exactly with those ordered structures that do not contain the the 4-element star $\mathbf{A}'$ (see Figure 1(b)).

Recently, (2 : 3)-median semilattices were explicitly described in [5]. It was shown that (2 : 3)-median semilattices coincide with those median semilattices that are trees: a $\wedge$-semilattice (resp. $\vee$-semilattice) is said to be a *tree* if no pair of incomparable elements have an upper (resp. lower) bound.
<figure><img src="image_3.png" /><figcaption>FIGURE 2. $\mathbf{A}_1$ is a (1, 2 : 3)-median semilattice, whereas the semilattice $\mathbf{A}_2$ is not.</figcaption></figure>

In particular, it follows that if a median algebra is a (1 : 3)- or a (2 : 3)-semilattice, then the same holds for any associated semilattice order $\leq_a$. As illustrated by the ordered structures in Figure 2, this invariance no longer holds for (1, 2 : 3)-median semilattices.

As mentioned above, (1 : 3)-median semilattices and (2 : 3)-median semilattices can be thought of as ordered structures that do not contain the 4-element star and the 4-element Boolean algebra, respectively. The following proposition provides a similar description for (1, 2 : 3)-median semilattices.

**Proposition 2.1.** Let $\mathbf{A} := \langle A, \leq \rangle$ be a median semilattice. Then $\mathbf{A}$ is a (1, 2 : 3)-median semilattice if and only if it does not contain a copy of the median semilattice in Figure 2(b) as a semilattice (in fact, only need to consider $b, c, d$ and $d'$).

*Proof.* Note that if $\mathbf{A} = \langle A, \leq \rangle$ contains a copy of the median semilattice in Figure 2(b), then taking $\{x, y, z\} = \{d', b, c\}$ have that

$$ \mathbf{m}(x, y, z) \notin \{x, y, z, x \wedge y, y \wedge z, z \wedge x\}. $$

Hence the condition is necessary.

To show that the condition is sufficient, suppose that $\mathbf{A}$ is not a (1, 2 : 3)-median semilattice. Hence, there are $x, y, z, d \in A$ such that

$$ d = \mathbf{m}(x, y, z) \notin \{x, y, z, x \wedge y, y \wedge z, z \wedge x\}. $$

Using the fact that

$$ d = (x \wedge y) \vee (y \wedge z) \vee (z \wedge x), $$

we have that $b \wedge c < d$, for every $b, c \in \{x, y, z\}$ with $b \neq c$. Consider

$$ d' = (x \wedge y) \vee (y \wedge z). $$

Clearly, $d' \leq d$.

Now if $d' < d$, then $\{x \wedge y, y \wedge z, x \wedge y \wedge z, d, d'\}$ is a copy of Figure 2(b). So we may assume that $d = d' = (x \wedge y) \vee (y \wedge z) = y \wedge (x \vee z)$. But in this case, $\{y, x \wedge y, y \wedge z, x \wedge y \wedge z, d\}$ is a copy of Figure 2(b). As these were the only two possible cases, the proof of Proposition 2.1 is now complete. $\square$

Thus, examples of (1, 2 : 3)-median semilattices (non-exhaustive) can be obtained from bottom-rooted trees by substituting some leaves (maximal elements) for any graph not containing Figure 2(b), for instance, as in Figure 2(a). A further example that is not subsumed by this construction, can be obtained by taking, e.g., the (1, 2 : 3)-median semilattice in Figure 1(c) and replacing $d'$ by the 4-element Boolean lattice.
REFERENCES

[1] S. P. Avann. Metric ternary distributive semi-lattices. *Proceedings of the American Mathematical Society*, **12**:407–414, 1961.

[2] H. J. Bandelt and J. Hedlíková. Median algebras. *Discrete mathematics*, **45**:1–30, 1983.

[3] H.-J. Bandelt, M. Van De Vel. The median stabilization degree of a median algebra. *Journal of Algebraic Combinatorics*, **9**(2):115–127, 1999.

[4] G. Birkhoff and S. A. Kiss. A ternary operation in distributive lattices. *Bulletin of the American Mathematical Society*, **53**:749–752, 1947.

[5] M. Couceiro, S. Foldes, G. C. Meletiou. Arrow type impossibility theorems over median algebras. Manuscript, 2015 (arXiv:1508.04741v1).

[6] M. Couceiro, J.-L. Marichal and B. Teheux, Conservative median algebras and semilattices. To appear in *Order*.

[7] E. Evans. *Median lattices and convex subalgebras*. In *Universal Algebra*, volume 29 of Colloquia Mathematica Societatis János Bolyai, pages 225–240. North-Holland, Amsterdam, 1982.

[8] S. Foldes, J. Szigeti. A half-space approach to order dimension. *Order* **24** 59–73, 2007.

[9] J. R. Isbell. Median algebra. *Transactions of the American Mathematical Society*, **260**(2):319–362, 1980.

[10] M. Kolibiar, T. Marcisová. On a question of J. Hashimoto. *Mat. Časopis*, **24**:179–185, 1974.

[11] B. Monjardet. Théorie et applications de la médiane dans les treillis distributifs finis. *Annals Discrete Math.*, **9**:87–91, 1980.

[12] H.M. Mulder, A. Schrijver. Median graphs and Helly hypergraphs. *Discrete Math.*, **25**, 41–50, 1979.

[13] M. Sholander. Trees, lattices, order, and betweenness. *Proceedings of the American Mathematical Society*, **3**(3):369–381, 1952.

[14] M. Sholander. Medians, lattices, and trees. *Proceedings of the American Mathematical Society*, **5**(5):808–812, 1954.

[15] P.J. Slater. Medians of arbitrary graphs. *J. Graph Theory*, **4**:389–392, 1980.

LORIA (CNRS - INRIA NANCY GRAND EST - UNIVERSITÉ DE LORRAINE), ÉQUIPE OR- PAILLEUR, BATIMENT B, CAMPUS SCIENTIFIQUE, B.P. 239, F-54506 VANDOEUVRE LES NANCY
*E-mail address: miguel.couceiro[at]inria.fr*

TEI OF EPIRUS, PO BOX 110, 47100 ARTA, GREECE
*E-mail address: gmelet[at]teiep.gr*