Median algebra

In mathematics, a median algebra is a set with a ternary operation ${\displaystyle \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. ${\displaystyle \langle x,y,y\rangle =y}$
2. ${\displaystyle \langle x,y,z\rangle =\langle z,x,y\rangle }$
3. ${\displaystyle \langle x,y,z\rangle =\langle x,z,y\rangle }$
4. ${\displaystyle \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

• ${\displaystyle \langle x,y,y\rangle =y}$
• ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle 0}$ and ${\displaystyle 1}$ satisfying ${\displaystyle \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 ${\displaystyle x}$, ${\displaystyle y}$, and ${\displaystyle z}$ there is a unique vertex ${\displaystyle \langle x,y,z\rangle }$ that belongs to shortest paths between any two of ${\displaystyle x}$, ${\displaystyle y}$, and ${\displaystyle z}$. If this is the case, then the operation ${\displaystyle \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 ${\displaystyle [x,z]}$ to be the set of elements ${\displaystyle y}$ such that ${\displaystyle \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 ${\displaystyle (x,z)}$ such that the interval ${\displaystyle [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

• Birkhoff, Garrett; Kiss, S.A. (1947). "A ternary operation in distributive lattices". Bull. Amer. Math. Soc. 53 (8): 749–752. doi:10.1090/S0002-9904-1947-08864-9.
• Isbell, John R. (August 1980). "Median algebra". Trans. Amer. Math. Soc. American Mathematical Society. 260 (2): 319–362. doi:10.2307/1998007. JSTOR 1998007.
• Knuth, Donald E. (2008). Introduction to combinatorial algorithms and Boolean functions. The Art of Computer Programming. 4.0. Upper Saddle River, NJ: Addison-Wesley. pp. 64–74. ISBN 0-321-53496-4.

External links

• Median Algebra Proof