Median algebra
Encyclopedia
In mathematics
, a median algebra is a set with a ternary operation
< x,y,z > satisfying a set of axioms which generalise the notion of median or majority function
, as a Boolean function.
The axioms are
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
also suffice.
In a Boolean algebra, or more generally a distributive lattice
, the median function
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
.
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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a median algebra is a set with a ternary operation
Ternary operation
In mathematics, a ternary operation is an n-ary operation with n = 3. A ternary operation on a set A takes any given three elements of A and combines them to form a single element of A. An example of a ternary operation is the product in a heap....
< x,y,z > satisfying a set of axioms which generalise the notion of median or majority function
Majority function
In Boolean logic, the majority function is a function from n inputs to one output. The value of the operation is false when n/2 or more arguments are false, and true otherwise....
, as a Boolean function.
The axioms are
- < x,y,y > = y
- < x,y,z > = < z,x,y >
- < x,y,z > = < x,z,y >
- < < x,w,y > ,w,z > = < x,w, < y,w,z > >
The second and third axioms imply commutativity
Commutativity
In mathematics an operation is commutative if changing the order of the operands does not change the end result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it...
: 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
Distributive lattice
In mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection...
, the median function
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
Distributive lattice
In mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection...
.
Relation to median graphs
A median graphMedian graph
In mathematics, and more specifically graph theory, a median graph is an undirected graph in which any three vertices a, b, and c have a unique median: a vertex m that belongs to shortest paths between any two of a, b, and c.The concept of median graphs has long been studied, for instance by or ...
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.