Median algebra

In mathematics, a median algebra is a set with a ternary operation $⟨x,y,z⟩$ satisfying a set of axioms which generalise the notions of medians of triples of real numbers and of the Boolean majority function.

The axioms are

1. $⟨x,y,y⟩=y$
2. $⟨x,y,z⟩=⟨z,x,y⟩$
3. $⟨x,y,z⟩=⟨x,z,y⟩$
4. $⟨⟨x,w,y⟩,w,z⟩=⟨x,w,⟨y,w,z⟩⟩$

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

• $⟨x,y,y⟩=y$
• $⟨u,v,⟨u,w,x⟩⟩=⟨u,x,⟨w,u,v⟩⟩$

also suffice.

In a Boolean algebra, or more generally a distributive lattice, the median function $⟨x,y,z⟩=(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 $⟨0,x,1⟩=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 $⟨x,y,z⟩$ that belongs to shortest paths between any two of $x$, $y$, and $z$. If this is the case, then the operation $⟨x,y,z⟩$ 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 $⟨x,y,z⟩=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.

References

• Template:Cite journal
• Template:Cite journal
• Template:Cite book

External links

• Median Algebra Proof