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

HAL
open science

# Median preserving aggregation functions

Miguel Couceiro, Jean-Luc Marichal, Bruno Teheux

► To cite this version:

Miguel Couceiro, Jean-Luc Marichal, Bruno Teheux. Median preserving aggregation functions. 8th International Summer School on Aggregation Operators and their Applications (AGOP 2015), Michal Baczyński, Bernard De Baets, Radko Mesiar, Jul 2015, Katowice, Poland. pp.85-89. hal-01184116

HAL Id: hal-01184116

https://hal.science/hal-01184116

Submitted on 13 Aug 2015

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

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

Public Domain
# MEDIAN PRESERVING AGGREGATION FUNCTIONS

Miguel Couceiro

LORIA

(CNRS - Inria G. E. - U. Lorraine)

Bat. B, Campus Sci. - B.P. 239

F-54506 Vandoeuvre-lès-Nancy

miguel.couceiro[at]inria.fr

Jean-Luc Marichal

Mathematics Research Unit,

University of Luxembourg

6, rue Coudenhove-Kalergi

L-1359 Luxembourg

jean-luc.marichal[at]uni.lu

Bruno Teheux

Mathematics Research Unit,

University of Luxembourg

6, rue Coudenhove-Kalergi

L-1359 Luxembourg

bruno.teheux[at]uni.lu

## Summary

A median algebra is a ternary algebra that satisfies every equation satisfied by the median terms of distributive lattices. We present a characterization theorem for aggregation functions over conservative median algebras. In doing so, we give a characterization of conservative median algebras by means of forbidden substructures and by providing their representation as chains.

**Keywords:** Median algebras, Aggregation Functions, Distributive lattices.

# 1 INTRODUCTION AND PRELIMINARIES

Informally, an aggregation function $f: A^n \to B$ may be thought of as a mapping that preserves the structure of $A$ into $B$. It is common to consider that $B$ is equal to $A$ and is equipped with a partial order so that aggregation functions are thought of as order-preserving maps [8].

If $\mathbf{L} = (L, \wedge, \vee)$ is a distributive lattice then the ternary term operation defined on $\mathbf{L}$ by

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

is symmetric and self dual, and is called the median term over $\mathbf{L}$. If $\mathbf{L}$ is a total order, then $\mathbf{m}(a, b, c)$ is the element among $a, b$ and $c$ that is between the two other ones if $a, b, c$ are mutually distinct, and is the majority element otherwise.

Median algebras are ternary algebras that were introduced in order to abstract this notion of betweenness. Formally, a median algebra is an algebra $\mathbf{A} = (A, \mathbf{m})$

with a single ternary operation $\mathbf{m}$ that satisfies the equations

$$ \begin{aligned} \mathbf{m}(x, x, y) &= x, \\ \mathbf{m}(x, y, z) &= \mathbf{m}(y, x, z) = \mathbf{m}(y, z, x), \\ \mathbf{m}(\mathbf{m}(x, y, z), t, u) &= \mathbf{m}(x, \mathbf{m}(y, t, u), \mathbf{m}(z, t, u)), \end{aligned} $$

and that is called a median operation. In particular, every median algebra satisfies the equation

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

Examples of median operations are given by median term operations over distributive lattices. If $\mathbf{L}$ is a distributive lattice and if $\mathbf{m}_{\mathbf{L}}$ is the operation defined on $\mathbf{L}$ by (1.1) then the algebra $\langle L, \mathbf{m}_{\mathbf{L}} \rangle$ is called the median algebra associated with $\mathbf{L}$. If $\mathbf{A}$ is a median algebra, the median operation is extended to $\mathbf{A}^n$ pointwise.

A median algebra $\mathbf{A} = (A, \mathbf{m})$ is said to be conservative if

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

for every $x, y, z \in A$. It is not difficult to observe that a median algebra is conservative if and only if each of its subsets is a median subalgebra. Moreover, the median term associated with a total order is a conservative median operation. This fact was observed in §11 of [12], which presents the four element Boolean algebra as a counter-example.

The results of this paper, which were previously exposed in [5], are twofold. First, we present a description of conservative median algebras in terms of forbidden substructures (in complete analogy with BIRKHOFF's characterization of distributive lattices with $M_5$ and $N_5$ as forbidden substructures and KRATOWSKI's characterization of planar graphs in terms of forbidden minors), and that leads to a representation of conservative median algebras (with at least five elements) as chains. In fact, the only conservative median algebra that is not representable as a chain is the four element Boolean algebra.
Second, we characterize functions $f: \mathbf{B} \to \mathbf{C}$ that satisfy the equation

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

where $\mathbf{B}$ and $\mathbf{C}$ are finite products of (non necessarily finite) chains, as superposition of compositions of monotone maps with projection maps (Theorem 4.5). Particularized to aggregation functions $f: \mathbf{A}^n \to \mathbf{A}$, where $\mathbf{A}$ is a chain, we obtain an ARROW-like theorem: *f satisfies equation (1.3) if and only if it is dictatorial and monotone* (Corollary 4.6).

Throughout the paper we employ the following notation. For each positive integer $n$, we set $[n] = \{1, \dots, n\}$. Algebras are denoted by bold roman capital letters $\mathbf{A}, \mathbf{B}, \mathbf{X}, \mathbf{Y}$... and their universes by italic roman capital letters $A, B, X, Y$.... To simplify our presentation, we will keep the introduction of background to a minimum, and we will assume that the reader is familiar with the theory of lattices and ordered sets. We refer the reader to [7, 9] for further background. Proofs of the results presented in the fourth section are omitted because they rely on arguments involving a categorical duality that are beyond the scope of this paper. The missing proofs and details can be found in [6].

## 2 MEDIAN ALGEBRAS, MEDIAN SEMILATTICES AND MEDIAN GRAPHS

Median algebras have been investigated by several authors (see [4, 10] for early references on median algebras and see [2, 11] for some surveys) who illustrated the deep interactions between median algebras, order theory and graph theory.

For instance, take an element $a$ of a median algebra $\mathbf{A}$ and consider the relation $\leq_a$ defined on $\mathbf{A}$ by

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

Endowed with this relation, $\mathbf{A}$ is a $\wedge$-semilattice order with bottom element $a$ [13]: the associated operation $\wedge$ is defined by $x \wedge y = \mathbf{m}(a, x, y)$.

Semilattices constructed in this way are called *median semilattices*, and they coincide exactly with semilattices in which every principal ideal is a distributive lattice and in which any three elements have a join whenever each pair of them is bounded above. The operation $\mathbf{m}$ on $\mathbf{A}$ can be recovered from the median semilattice order $\leq_a$ using identity (1.1) where $\wedge$ and $\vee$ are defined with respect to $\leq_a$. Semilattices associated with conservative median algebras are called *conservative median semilattices*.

Note that if a median algebra $\mathbf{A}$ contains two elements 0 and 1 such that $\mathbf{m}(0, x, 1) = x$ for every $x \in \mathbf{A}$, then $(A, \leq_0)$ is a distributive lattice order bounded by 0 and 1, and where $x \wedge y$ and $x \vee y$ are given by $\mathbf{m}(x, y, 0)$ and $\mathbf{m}(x, y, 1)$, respectively. It is noteworthy that equations satisfied by median algebras of the form $\langle L, \mathbf{m}_L \rangle$ are exactly those satisfied by median algebras. In particular, every median algebra satisfies the equation

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

Moreover, covering graphs (i.e., undirected HASSE diagram) of median semilattices have been investigated and are, in a sense, equivalent to median graphs. Recall that a median graph is a (non necessarily finite) connected graph in which for any three vertices $u, v, w$ there is exactly one vertex $x$ that lies on a shortest path between $u$ and $v$, on a shortest path between $u$ and $w$ and on a shortest path between $v$ and $w$. In other words, $x$ (the median of $u, v$ and $w$) is the only vertex such that

$$\begin{align*}d(u, v) &= d(u, x) + d(x, v), \\d(u, w) &= d(u, x) + d(x, w), \\d(v, w) &= d(v, x) + d(x, w).\end{align*}$$

Every median semilattice whose intervals are finite has a median covering graph [1] and conversely, every median graph is the covering graph of a median semilattice [1, 13]. This connection is deeper: median semilattices can be characterized among the ordered sets whose bounded chains are finite and in which any two elements are bounded below as the ones whose covering graph is median [3]. For further background see, e.g., [2].

## 3 CHARACTERIZATIONS OF CONSERVATIVE MEDIAN ALGEBRAS

Let $C_0 = \langle C_0, \leq_0, c_0 \rangle$ and $C_1 = \langle C_1, \leq_1, c_1 \rangle$ be chains with bottom elements $c_0$ and $c_1$, respectively. The $\perp$-coalesced sum $C_0 \perp C_1$ of $C_0$ and $C_1$ is the poset obtained by amalgamating $c_0$ and $c_1$ in the disjoint union of $C_0$ and $C_1$. Formally,

$$C_0 \perp C_1 = \langle C_0 \sqcup C_1 / \equiv, \leq \rangle,$$

where $\sqcup$ is the disjoint union, where $\equiv$ is the equivalence generated by $\{(c_0, c_1)\}$ and where $\leq$ is defined by

$$x/\equiv \leq y/\equiv \iff (x \in \{c_0, c_1\} \text{ or } x \leq_0 y \text{ or } x \leq_1 y).$$
<figure><img src="image_2.png" /><figcaption>Figure 1: Examples of ∧-semilattices that are not conservative.</figcaption></figure>

**Proposition 3.1.** The partially ordered sets $\mathbf{A}_1, \dots, \mathbf{A}_4$ depicted in Fig. 1 are not conservative median semilattices.

*Proof.* The poset $\mathbf{A}_1$ is a bounded lattice (also denoted by $N_5$ in the literature on lattice theory, e.g., in [7, 9]) that is not distributive. In $\mathbf{A}_2$ the center is equal to the median of the other three elements. The poset $\mathbf{A}_3$ contains a copy of $\mathbf{A}_2$, and $\mathbf{A}_4$ is a distributive lattice that contains a copy of the dual of $\mathbf{A}_2$ and thus it is not conservative as a median algebra. $\square$

The following Theorem provides descriptions of conservative semilattices with at least five elements, both in terms of forbidden substructures and in the form of representations by chains. Note that any semilattice with at most four elements is conservative, but the poset depicted in Fig. 1(b).

**Theorem 3.2.** Let $\mathbf{A}$ be a median algebra with $|\mathbf{A}| \ge 5$. The following conditions are equivalent.

(1) $\mathbf{A}$ is conservative.

(2) For every $a \in A$ the ordered set $\langle A, \le_a \rangle$ does not contain a copy of the poset depicted in Fig. 1(b).

(3) There is an $a \in A$ and lower bounded chains $C_0$ and $C_1$ such that $\langle A, \le_a \rangle$ is isomorphic to $C_0 \perp C_1$.

(4) For every $a \in A$, there are lower bounded chains $C_0$ and $C_1$ such that $\langle A, \le_a \rangle$ is isomorphic to $C_0 \perp C_1$.

*Proof.* (1) $\implies$ (2): Follows from Proposition 3.1.

(2) $\implies$ (1): Suppose that $\mathbf{A}$ is not conservative, that is, there are $a, b, c, d \in A$ such that $d := \mathbf{m}(a, b, c) \notin \{a, b, c\}$. Clearly, $a, b$ and $c$ must be pairwise distinct. By (1.2), $a$ and $b$ are $\le_c$-incomparable, and $d <_c a$ and $d <_c b$. Moreover, $c <_c d$ and thus $\langle \{a, b, c, d\}, \le_c \rangle$ is a copy of $A_2$ in $\langle A, \le_c \rangle$.

(1) $\implies$ (4): Let $a \in A$. First, suppose that for every $x, y \in A \setminus \{a\}$ we have $\mathbf{m}(x, y, a) \neq a$. Since $\mathbf{A}$ is conservative, for every $x, y \in A$, either $x \le_a y$ or $y \le_a x$. Thus $\le_a$ is a chain with bottom element $a$, and we can choose $C_1 = \langle A, \le_a, a \rangle$ and $C_2 = \langle \{a\}, \le_a, a \rangle$.

Suppose now that there are $x, y \in A \setminus \{a\}$ such that $\mathbf{m}(x, y, a) = a$, that is, $x \wedge y = a$. We show that

$$ z \neq a \implies \left( \begin{array}{l} \mathbf{m}(x, z, a) \neq a \\ \text{or } \mathbf{m}(y, z, a) \neq a \end{array} \right), \quad z \in A. \quad (3.1) $$

For the sake of a contradiction, suppose that $\mathbf{m}(x, z, a) = a$ and $\mathbf{m}(y, z, a) = a$ for some $z \neq a$. By equation (2.1), we have

$$ \mathbf{m}(x, y, z) = \mathbf{m}(\mathbf{m}(\mathbf{m}(x, y, z), x, a), \mathbf{m}(\mathbf{m}(x, y, z), z, a), \mathbf{m}(\mathbf{m}(x, y, z), y, a)). \quad (3.2) $$

Assume that $\mathbf{m}(x, y, z) = x$. Then (3.2) is equivalent to

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

which yields the desired contradiction. By symmetry, we derive the same contradiction in the case $\mathbf{m}(x, y, z) \in \{y, z\}$.

We now prove that

$$ z \neq a \implies (\mathbf{m}(x, z, a) = a \text{ or } \mathbf{m}(y, z, a) = a), \quad z \in A. \quad (3.3) $$

For the sake of a contradiction, suppose that $\mathbf{m}(x, z, a) \neq a$ and $\mathbf{m}(y, z, a) \neq a$ for some $z \neq a$. Since $\mathbf{m}(x, y, a) = a$ we have that $z \notin \{x, y\}$.

If $\mathbf{m}(x, z, a) = z$ and $\mathbf{m}(y, z, a) = y$, then $y \le_a z \le_a x$ which contradicts $x \wedge y = a$. Similarly, if $\mathbf{m}(x, z, a) = z$ and $\mathbf{m}(y, z, a) = z$, then $z \le_a x$ and $z \le_a y$ which also contradicts $x \wedge y = a$. The case $\mathbf{m}(x, z, a) = x$ and $\mathbf{m}(y, z, a) = z$ leads to similar contradictions.

Hence $\mathbf{m}(x, z, a) = x$ and $\mathbf{m}(y, z, a) = y$, and the $\le_a$-median semilattice arising from the subalgebra $\mathbf{B} = \{a, x, y, z\}$ of $\mathbf{A}$ is the median semilattice associated with the four element Boolean algebra. Let $z' \in A \setminus \{a, x, y, z\}$. By (3.1) and symmetry we may assume that $\mathbf{m}(x, z', a) \in \{x, z'\}$. First, suppose that $\mathbf{m}(x, z', a) = z'$. Then $\langle \{a, x, y, z, z'\}, \le_a \rangle$ is $N_5$ (Fig. 1(a)) which is not a median semilattice. Suppose then that $\mathbf{m}(x, z', a) = x$. In this case, the restriction of $\le_a$ to $\{a, x, y, z, z'\}$ is depicted in Fig. 1(c) or 1(d), which contradicts Proposition 3.1, and the proof of (3.3) is thus complete.
Now, let $C_0 = \{z \in A \mid (x, z, a) \neq a\}$, $C_1 = \{z \in A \mid (y, z, a) \neq a\}$ and let $\mathbf{C}_0 = \langle C_0, \le_a, a \rangle$ and $\mathbf{C}_1 = \langle C_1, \le_a, a \rangle$. It follows from (3.1) and (3.3) that $\langle \mathbf{A}, \le_a \rangle$ is isomorphic to $\mathbf{C}_0 \perp \mathbf{C}_1$.

(4) $\implies$ (3): Trivial.

(3) $\implies$ (1): Let $x, y, z \in \mathbf{C}_0 \perp \mathbf{C}_1$. If $x, y, z \in C_i$ for some $i \in \{0, 1\}$ then $\mathbf{m}(x, y, z) \in \{x, y, z\}$. Otherwise, if $x, y \in C_i$ and $z \notin C_i$, then $\mathbf{m}(x, y, z) \in \{x, y\}$. $\square$

The equivalence between (3) and (1) in Proposition 3.2 gives rise to the following representation of conservative median algebras.

**Theorem 3.3.** Let $\mathbf{A}$ be a median algebra with $|A| \ge 5$. Then $\mathbf{A}$ is conservative if and only if there is a totally ordered set $\mathbf{C}$ such that $\mathbf{A}$ is isomorphic to $\langle \mathbf{C}, \mathbf{m}_{\mathbf{C}} \rangle$.

*Proof.* Sufficiency is trivial. For necessity, consider the universe of $\mathbf{C}_0 \perp \mathbf{C}_1$ in condition (3) of Proposition 3.2 endowed with $\le$ defined by $x \le y$ if $x \in C_1$ and $y \in C_0$ or $x, y \in C_0$ and $x \le_0 y$ or $x, y \in C_1$ and $y \le_1 x$. $\square$

As stated in the next result, the totally ordered set $\mathbf{C}$ given in Theorem 3.3 is unique, up to (dual) isomorphism.

**Theorem 3.4.** Let $\mathbf{A}$ be a median algebra. If $\mathbf{C}$ and $\mathbf{C}'$ are two chains such that $\mathbf{A} \cong \langle \mathbf{C}, \mathbf{m}_{\mathbf{C}} \rangle$ and $\mathbf{A} \cong \langle \mathbf{C}', \mathbf{m}_{\mathbf{C}'} \rangle$, then $\mathbf{C}$ is order isomorphic or dual order isomorphic to $\mathbf{C}'$.

# 4 HOMOMORPHISMS BETWEEN CONSERVATIVE MEDIAN ALGEBRAS

In view of Theorem 3.3 and Theorem 3.4, we introduce the following notation. Given a conservative median algebra $\mathbf{A}$ ($|\mathbf{A}| \ge 5$), we denote a chain representation of $\mathbf{A}$ by $\mathbf{C}(\mathbf{A})$, that is, $\mathbf{C}(\mathbf{A})$ is a chain such that $\mathbf{A} \cong \langle \mathbf{C}(\mathbf{A}), \mathbf{m}_{\mathbf{C}(\mathbf{A})} \rangle$, and we denote the corresponding isomorphism by $f_{\mathbf{A}}: \mathbf{A} \to \langle \mathbf{C}(\mathbf{A}), \mathbf{m}_{\mathbf{C}(\mathbf{A})} \rangle$. If $f_{\mathbf{A}}: \mathbf{A} \to \mathbf{B}$ is a map between two conservative median algebras with at least five elements, the map $f': \mathbf{C}(\mathbf{A}) \to \mathbf{C}(\mathbf{B})$ defined as $f' = f_{\mathbf{B}} \circ f \circ f_{\mathbf{A}}^{-1}$ is said to be induced by $f$.

A function $f: \mathbf{A} \to \mathbf{B}$ between median algebras $\mathbf{A}$ and $\mathbf{B}$ is called a median homomorphism if it satisfies equation (1.3). We use the terminology introduced above to characterize median homomorphisms between conservative median algebras. Recall that a map between two posets is monotone if it is isotone or antitone.

**Theorem 4.1.** Let $\mathbf{A}$ and $\mathbf{B}$ be two conservative median algebras with at least five elements. A map $f: \mathbf{A} \to \mathbf{B}$ is a median homomorphism if and only if the induced map $f': \mathbf{C}(\mathbf{A}) \to \mathbf{C}(\mathbf{B})$ is monotone.

<figure><img src="image_3.png" /><figcaption>(a) A monotone map which is not a median homomorphism.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>(b) A median homomorphism which is not monotone.</figcaption></figure>

<caption>Figure 2: Examples for Remark 4.3.</caption>

**Corollary 4.2.** Let $\mathbf{C}$ and $\mathbf{C}'$ be two chains. A map $f: \mathbf{C} \to \mathbf{C}'$ is a median homomorphism if and only if it is monotone.

*Remark 4.3.* Note that Corollary 4.2 only holds for chains. Indeed, Fig. 2(a) gives an example of a monotone map that is not a median homomorphism, and Fig. 2(b) gives an example of median homomorphism that is not monotone.

Since the class of conservative median algebras is clearly closed under homomorphic images, we obtain the following corollary.

**Corollary 4.4.** Let $\mathbf{A}$ and $\mathbf{B}$ be two median algebras and $f: \mathbf{A} \to \mathbf{B}$. If $\mathbf{A}$ is conservative, and if $|\mathbf{A}|, |f(\mathbf{A})| \ge 5$, then $f$ is a median homomorphism if and only if $f(\mathbf{A})$ is a conservative median subalgebra of $\mathbf{B}$ and the induced map $f': \mathbf{C}(\mathbf{A}) \to \mathbf{C}(f(\mathbf{A}))$ is monotone.

We are actually able to lift the previous result to finite products of chains. If $f_i: A_i \to A'_i$ ($i \in [n]$) is a family of maps, let $(f_1, \dots, f_n): A_1 \times \dots \times A_n \to A'_1 \times \dots \times A'_n$ be defined by

$$(f_1, \dots, f_n)(x_1, \dots, x_n) := (f_1(x_1), \dots, f_n(x_n)).$$

The following theorem characterizes median homomorphisms between finite products of chains.

**Theorem 4.5.** Let $\mathbf{A} = \mathbf{C}_1 \times \dots \times \mathbf{C}_k$ and $\mathbf{B} = \mathbf{D}_1 \times \dots \times \mathbf{D}_n$ be two finite products of chains. Then $f: \mathbf{A} \to \mathbf{B}$ is a median homomorphism if and only if there exist $\sigma: [n] \to [k]$ and monotone maps $f_i: \mathbf{C}_{\sigma(i)} \to \mathbf{D}_i$ for $i \in [n]$ such that $f = (f_{\sigma(i)}, \dots, f_{\sigma(n)})$.

As an immediate consequence, it follows that aggregation functions compatible with median functions on
ordinal scales are dictatorial.

If $A = A_1 \times \cdots \times A_n$ and $i \in [n]$, then we denote the
projection map from $A$ onto $A_i$ by $\pi_i^A$, or simply by
$\pi_i$ if there is no danger of ambiguity.

**Corollary 4.6.** Let $C_1, \dots, C_n$ and $D$ be chains. A map $f : C_1 \times \dots \times C_n \to D$ is a median homomorphism if and only if there is a $j \in [n]$ and a monotone map $g : C_j \to D$ such that $f = g \circ \pi_j$.

In the particular case of Boolean algebras (i.e., powers of a two element chain), Theorem 4.5 can be restated as follows.

**Corollary 4.7.** *Assume that $f: 2^n \to 2^m$ is a map between two finite Boolean algebras.*

(1) The map $f$ is a median homomorphism if and only if there are $\sigma : [m] \to ([n] \cup \{\perp\})$ and $\epsilon : [m] \to \{\text{id}, \neg\}^n$ such that

$$
f : (x_1, \dots, x_n) \mapsto (\epsilon_1 x_{\sigma_1}, \dots, \epsilon_m x_{\sigma_m}),
$$

where $x_\perp$ is defined as the constant map 0.

In particular,

(2) A map $f: 2^n \to 2$ is a median homomorphism if and only if it is a constant function, a projection map or the negation of a projection map.

(3) A map $f: 2^n \to 2^n$ is a median isomorphism if and only if there is a permutation $\sigma$ of $[n]$ and an element $\epsilon$ of $\{\text{id}, \neg\}^n$ such that $f(x_1, \dots, x_n) = (\epsilon_1 x_{\sigma(1)}, \dots, \epsilon_n x_{\sigma(n)})$ for any $(x_1, \dots, x_n) \text{ in A.}$

5 CONCLUDING REMARKS AND
FURTHER RESEARCH
DIRECTIONS

In this paper we have described conservative median algebras and semilattices with at least five elements in terms of forbidden configurations and have given a representation by chains. We have also characterized median-preserving maps between finite products of these algebras, showing that they are essentially determined componentwise. The next step in this line of research is to extend our results to larger classes of median algebras and their ordered counterparts.

Acknowledgements

This work was supported by the internal research
project F1R-MTH-PUL-15MRO3 of the University of
Luxembourg.

**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. Discrete ordered sets whose covering graphs are median. *Proceedings of the American Mathematical Society*, 91(1):6–8, 1984.

[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 and B. Teheux, An Arrow-like theorem over median algebras, *Proceedings of the DA2PL 2014 Conference*, Ecole Centrale de Paris, France, November 20–21 2014, pp. 72 – 75.

[6] M. Couceiro, J.-L. Marichal and B. Teheux, Conservative Median Algebras, arXiv:1405.0935.

[7] B. A. Davey and H. A. Priestley. *Introduction to lattices and order*. Cambridge University Press, New York, second edition, 2002.

[8] M. Grabisch, J.-L. Marichal, R. Mesiar, and E. Pap. *Aggregation functions*. Encyclopedia of Mathematics and its Applications, vol. 127. Cambridge University Press, Cambridge, 2009.

[9] G. Grätzer. *General lattice theory*. Birkhäuser Verlag, Basel, second edition, 1998. New appendices by the author with B. A. Davey, R. Freese, B. Ganter, M. Greferath, P. Jipsen, H. A. Priestley, H. Rose, E. T. Schmidt, S. E. Schmidt, F. Wehrung and R. Wille.

[10] A. A. Grau. Ternary Boolean algebra. *Bulletin of the American Mathematical Society*, (May 1944):567–572, 1947.

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

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

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