Misplaced Pages

Median algebra

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

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

  1. ⟨ x , y , y ⟩ = y {\displaystyle \langle x,y,y\rangle =y}
  2. ⟨ x , y , z ⟩ = ⟨ z , x , y ⟩ {\displaystyle \langle x,y,z\rangle =\langle z,x,y\rangle }
  3. ⟨ x , y , z ⟩ = ⟨ x , z , y ⟩ {\displaystyle \langle x,y,z\rangle =\langle x,z,y\rangle }
  4. ⟨ ⟨ 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 } 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 } 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

External links

Categories: