In mathematics, a median algebra is a set with a ternary operation ⟨ x , y , z ⟩ {\displaystyle \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
⟨ x , y , y ⟩ = y {\displaystyle \langle x,y,y\rangle =y}
⟨ x , y , z ⟩ = ⟨ z , x , y ⟩ {\displaystyle \langle x,y,z\rangle =\langle z,x,y\rangle }
⟨ x , y , z ⟩ = ⟨ x , z , y ⟩ {\displaystyle \langle x,y,z\rangle =\langle x,z,y\rangle }
⟨ ⟨ x , w , y ⟩ , w , z ⟩ = ⟨ x , w , ⟨ y , w , z ⟩ ⟩ {\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
⟨ x , y , y ⟩ = y {\displaystyle \langle x,y,y\rangle =y}
⟨ u , v , ⟨ u , w , x ⟩ ⟩ = ⟨ u , x , ⟨ w , u , v ⟩ ⟩ {\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 ⟨ x , y , z ⟩ = ( x ∨ y ) ∧ ( y ∨ z ) ∧ ( z ∨ x ) {\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 0 and 1 satisfying ⟨ 0 , x , 1 ⟩ = x {\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 x {\displaystyle x} , y {\displaystyle y} , and z {\displaystyle z} there is a unique vertex ⟨ x , y , z ⟩ {\displaystyle \langle x,y,z\rangle } that belongs to shortest paths between any two of x {\displaystyle x} , y {\displaystyle y} , and z {\displaystyle z} . If this is the case, then the operation ⟨ x , y , z ⟩ {\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 [ x , z ] {\displaystyle [x,z]} to be the set of elements y {\displaystyle y} such that ⟨ x , y , z ⟩ = y {\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 ( x , z ) {\displaystyle (x,z)} such that the interval [ x , z ] {\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. 260 (2). American Mathematical Society: 319–362. doi:10.2307/1998007. JSTOR 1998007. Knuth, Donald E. (2008). Introduction to combinatorial algorithms and Boolean functions. The Art of Computer Programming. Vol. 4. Upper Saddle River, NJ: Addison-Wesley. pp. 64–74. ISBN 978-0-321-53496-5.
External links Median Algebra Proof
