Median algebra explained

\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

\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

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

• Birkhoff . Garrett . Garrett Birkhoff . Kiss . A ternary operation in distributive lattices . . 53 . 1947 . 8 . 749–752 . 10.1090/S0002-9904-1947-08864-9 . S.A. . free .
• Isbell . John R. . John R. Isbell . Median algebra . . 260 . 2 . August 1980 . 319–362 . 10.2307/1998007 . 1998007 . American Mathematical Society . free .
• Book: Knuth, Donald E. . Donald Knuth

. Donald Knuth . Introduction to combinatorial algorithms and Boolean functions . . 4 . 2008 . 978-0-321-53496-5 . 64–74 . Addison-Wesley . Upper Saddle River, NJ .

External links

• Median Algebra Proof