# Median algebra

In mathematics, a median algebra is a set with a ternary operation $\langle x,y,z\rangle$ satisfying a set of axioms which generalise the notion of median or majority function, as a Boolean function.

The axioms are

1. $\langle x,y,y\rangle =y$ 2. $\langle x,y,z\rangle =\langle z,x,y\rangle$ 3. $\langle x,y,z\rangle =\langle x,z,y\rangle$ 4. $\langle \langle x,w,y\rangle ,w,z\rangle =\langle x,w,\langle y,w,z\rangle \rangle$ The second and third axioms imply commutativity: it is possible (but not easy) to show that in the presence of the other three, axiom (3) is redundant. The fourth axiom implies associativity. There are other possible axiom systems: for example the two

• $\langle x,y,y\rangle =y$ • $\langle u,v,\langle u,w,x\rangle \rangle =\langle u,x,\langle w,u,v\rangle \rangle$ also suffice.

In a Boolean algebra, or more generally a distributive lattice, the median function $\langle x,y,z\rangle =(x\vee y)\wedge (y\vee z)\wedge (z\vee x)$ satisfies these axioms, so that every Boolean algebra and every distributive lattice forms a median algebra.

Birkhoff and Kiss showed that a median algebra with elements $0$ and $1$ satisfying $\langle 0,x,1\rangle =x$ is a distributive lattice.

## Relation to median graphs

A median graph is an undirected graph in which for every three vertices $x$ , $y$ , and $z$  there is a unique vertex $\langle x,y,z\rangle$  that belongs to shortest paths between any two of $x$ , $y$ , and $z$ . If this is the case, then the operation $\langle x,y,z\rangle$  defines a median algebra having the vertices of the graph as its elements.

Conversely, in any median algebra, one may define an interval $[x,z]$  to be the set of elements $y$  such that $\langle x,y,z\rangle =y$ . One may define a graph from a median algebra by creating a vertex for each algebra element and an edge for each pair $(x,z)$  such that the interval $[x,z]$  contains no other elements. If the algebra has the property that every interval is finite, then this graph is a median graph, and it accurately represents the algebra in that the median operation defined by shortest paths on the graph coincides with the algebra's original median operation.