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∨y)∧(y∨z)∧(z∨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

* 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

* Median Algebra Proof

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Median algebra. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Median_algebra&oldid=186243"