Miguel Couceiro

Gerasimos C Meletiou

ON A SPECIAL CLASS OF MEDIAN ALGEBRAS

In this short note we consider a class of median algebras, called p1, 2 : 3q-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.

Preliminaries: median algebras

Recall that a median algebra is a structure A " xA, my for a nonempty set A and a ternary symmetric operation m : A 3 Ñ A, called median, that is a near-unaminity (i.e., mpx, x, yq " x) and such that for every x, y, z, t, u P A, mpmpx, y, zq, t, uq " mpx, mpy, t, uq, mpz, t, uqq.

Alternative axiomatizations were also proposed [START_REF] Bandelt | Median algebras[END_REF][START_REF] Isbell | Median algebra[END_REF][START_REF] Kolibiar | On a question of J. Hashimoto[END_REF]. In particular, it can be shown that the following equation mpmpx, y, zq, y, zq " mpx, y, zq 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 [START_REF] Sholander | Medians, lattices, and trees[END_REF] showed that each element a of a median algebra A gives rise to a median semilattice xA, ď a y where ď a defined by x ď a y ðñ mpa, x, yq " x.

In such a semilattice, a is the bottom element A a :" xA, ď a y and the induced semilattice operation ^a is then given by x ^a y " mpa, x, yq. Furthermore, its principal ideals Ó x :" ty P A : y ď a xu are distributive lattices. Conversely, if a ^-semilattice has the property that for any a, b, c P A, the three elements a ^b, b ^c, c ^a have a supremum whenever each pair of them is bounded above, then a median operation can be defined by (1.1) m ď px, y, zq " px ^yq _ px ^zq _ pz ^yq, for every x, y, z P A. In fact, as shown in [START_REF] Avann | Metric ternary distributive semi-lattices[END_REF], for every median algebra A " xA, my and every a P A, we have that m " m ďa . Similarly, every distributive lattice gives rise to a median algebra using (1.1), and the converse also holds whenever there are a, b P A such that mpa, x, bq " x for every x P A.

In the case of discrete structures, median algeras 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 [START_REF] Avann | Metric ternary distributive semi-lattices[END_REF] that every median semilattice whose intervals are finite has a covering graph (i.e., undirected Hasse diagram) that is median, and

' a ' b ' c (a) A ' a ' b ' c ' d (b) A 1 ' d 1 ' a ' b ' c ' d (c) A 2 Figure 1.
Examples of median semilattices: A is a p1 : 3q-median semilattice, A 1 is a p2 : 3q-median semilattice that is not p1 : 3q, and A 2 is a p1, 2 : 3q-median semilattice tha is not p2 : 3q.

that every median graph is the covering graph of a median semilattice. For further background see, e.g., [START_REF] Bandelt | Median algebras[END_REF].

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 A :" xA, ďy (thought of as a median algebra A " xA, my) is piq a p1 : 3q-median semilattice if for every x, y, z P A, mpx, y, zq P tx, y, zu; piiq a p2 : 3q-median semilattice if for every x, y, z P A, mpx, y, zq P tx ^y, y ^z, z ^xu; piiiq a p1, 2 : 3q-median semilattice if for every x, y, z P A, mpx, y, zq P tx, y, z, x ^y, y ^z, z ^xu.

Note that, apart from the 4-element Boolean lattice, every p1 : 3q-median semilattice is a p2 : 3q-median semilattice. Also, every p1 : 3q-median semilattice and every p2 : 3q-median semilattice is a p1, 2 : 3q-median semilattice.

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

Remark 1.1. Note that p1 : 3q-median semilattices are exactly those median algebras whose subsets are themselves median (sub)algebras. In the terminology of [START_REF] Bandelt | The median stabilization degree of a median algebra[END_REF], they are median algebras with msd (median stabilization degree) equal to 0.

The median semilattices in piq and piiq were described in terms of forbidden forbidden substructures in [START_REF] Couceiro | Conservative median algebras and semilattices[END_REF] and [START_REF] Couceiro | Arrow type impossibility theorems over median algebras[END_REF], respectively. In this paper we provide a similar description for p1, 2 : 3q-median semilattices.

Main Result

In [START_REF] Couceiro | Conservative median algebras and semilattices[END_REF], p1 : 3q-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. [START_REF] Foldes | A half-space approach to order dimension[END_REF].) Equivalently, p1 : 3q-median semilattices were shown to coincide exactly with those ordered structures that do not contain the the 4-element star A 1 (see Figure 1(b)).

Recently, p2 : 3q-median semilattices were explicitly described in [START_REF] Couceiro | Arrow type impossibility theorems over median algebras[END_REF]. It was shown that p2 : 3q-median semilattices coincide with those median semilattices that are trees: a ^-semilattice (resp. _-semilattice) is said to be a tree if no pair of incomparable elements have an upper (resp. lower) bound.

' a ' b ' c ' d ' d 1 (a) A 1 ' d 1 ' a ' b ' c ' d (b) A 2 Figure 2.
A 1 is a p1, 2 : 3q-median semilattice, whereas the semilattice A 2 is not.

In particular, it follows that if a median algebra is a p1 : 3q-or a p2 : 3qsemilattice, then the same holds for any associated semilattice order ď a . As illustrated by the ordered structures in Figure 2, this invariance no longer holds for p1, 2 : 3q-median semilattices.

As mentioned above, p1 : 3q-median semilattices and p2 : 3q-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 p1, 2 : 3q-median semilattices. Hence the condition is necessary.

To show that the condition is sufficient, suppose that A is not a p1, 2 : 3q-median semilattice. Hence, there are x, y, z, d P A such that d " mpx, y, zq R tx, y, z, x ^y, y ^z, z ^xu. . So we may assume that d " d 1 " px ^yq _ py ^zq " y ^px _ zq. But in this case, ty, x ^y, y ^z, x ^y ^z, du is a copy of Figure 2(b). As these were the only two possible cases, the proof of Proposition 2.1 is now complete.

Thus, examples of p1, 2 : 3q-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 p1, 2 : 3q-median semilattice in Figure 1(c) and replacing d 1 by the the 4-element Boolean lattice.

Proposition 2 . 1 .

 21 Let A :" xA, ďy be a median semilattice. Then A is a p1, 2 : 3qmedian semilattice if and only if it does not contain a copy of the median semilattice in Figure2(b) as a semilattice (in fact, only need to consider b, c, d and d 1 ). Proof. Note that if A " xA, ďy contains a copy of the median semilattice in Figure 2(b), then taking tx, y, zu " td 1 , b, cu have that mpx, y, zq R tx, y, z, x ^y, y ^z, z ^xu.

  Using the fact that d " px ^yq _ py ^zq _ pz ^xq, we have that b ^c ă d, for every b, c P tx, y, zu with b ‰ c. Consider d 1 " px ^yq _ py ^zq. Clearly, d 1 ď d. Now if d 1 ă d, then tx ^y, y ^z, x ^y ^z, d, d 1 u is a copy of Figure 2(b)