Median algebra
In mathematics, a median algebra is a set with a ternary operation [math]\displaystyle{ \langle x,y,z \rangle }[/math] 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
- [math]\displaystyle{ \langle x,y,y \rangle = y }[/math]
- [math]\displaystyle{ \langle x,y,z \rangle = \langle z,x,y \rangle }[/math]
- [math]\displaystyle{ \langle x,y,z \rangle = \langle x,z,y \rangle }[/math]
- [math]\displaystyle{ \langle \langle x,w,y\rangle ,w,z \rangle = \langle x,w, \langle y,w,z \rangle\rangle }[/math]
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
- [math]\displaystyle{ \langle x,y,y \rangle = y }[/math]
- [math]\displaystyle{ \langle u,v, \langle u,w,x \rangle\rangle = \langle u,x, \langle w,u,v \rangle\rangle }[/math]
also suffice.
In a Boolean algebra, or more generally a distributive lattice, the median function [math]\displaystyle{ \langle x,y,z \rangle = (x \vee y) \wedge (y \vee z) \wedge (z \vee x) }[/math] 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 [math]\displaystyle{ \langle0,x,1 \rangle = x }[/math] is a distributive lattice.
Relation to median graphs
A median graph is an undirected graph in which for every three vertices [math]\displaystyle{ x }[/math], [math]\displaystyle{ y }[/math], and [math]\displaystyle{ z }[/math] there is a unique vertex [math]\displaystyle{ \langle x,y,z \rangle }[/math] that belongs to shortest paths between any two of [math]\displaystyle{ x }[/math], [math]\displaystyle{ y }[/math], and [math]\displaystyle{ z }[/math]. If this is the case, then the operation [math]\displaystyle{ \langle x,y,z \rangle }[/math] defines a median algebra having the vertices of the graph as its elements.
Conversely, in any median algebra, one may define an interval [math]\displaystyle{ [x, z] }[/math] to be the set of elements [math]\displaystyle{ y }[/math] such that [math]\displaystyle{ \langle x,y,z \rangle = y }[/math]. One may define a graph from a median algebra by creating a vertex for each algebra element and an edge for each pair [math]\displaystyle{ (x, z) }[/math] such that the interval [math]\displaystyle{ [x, z] }[/math] 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.
- Knuth, Donald E. (2008). Introduction to combinatorial algorithms and Boolean functions. The Art of Computer Programming. 4. Upper Saddle River, NJ: Addison-Wesley. pp. 64–74. ISBN 978-0-321-53496-5.
External links
 |  |
