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 notions of medians of triples of real numbers and of the Boolean majority function.

The axioms are

$\langle x,y,y \rangle = y$
$\langle x,y,z \rangle = \langle z,x,y \rangle$
$\langle x,y,z \rangle = \langle x,z,y \rangle$
$\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 $\langle0,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.

References

{{cite journal | last1=Birkhoff | first1=Garrett | authorlink=Garrett Birkhoff | last2=Kiss | title=A ternary operation in distributive lattices | journal=Bull. Amer. Math. Soc. | volume=53 | date=1947 | issue=8 | pages=749–752 | doi=10.1090/S0002-9904-1947-08864-9 | first2=S.A. | doi-access=free }}
{{cite journal | last=Isbell | first=John R. | authorlink = John R. Isbell | title=Median algebra | journal=Trans. Amer. Math. Soc. | volume=260 | issue=2 | date=August 1980 | pages=319–362 | doi=10.2307/1998007 | jstor=1998007 | publisher=American Mathematical Society | doi-access=free }}
{{ cite book | last=Knuth | first=Donald E. | authorlink=Donald Knuth | title=Introduction to combinatorial algorithms and Boolean functions | series=The Art of Computer Programming | volume=4 | date=2008 | isbn=978-0-321-53496-5 | pages=64–74 | publisher=Addison-Wesley | location=Upper Saddle River, NJ }}

External links

[http://www.cs.unm.edu/~veroff/MEDIAN_ALGEBRA/ Median Algebra Proof]

Category:Boolean algebra

Category:Ternary operations