 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 notion of median or majority function, 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: 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 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/S000299041947088649.
 Isbell, John R. (August 1980). "Median algebra". Trans. Amer. Math. Soc. (American Mathematical Society) 260 (2): 319–362. doi:10.2307/1998007. JSTOR 1998007.
 Knuth, Donald E. (2008). Introduction to combinatorial algorithms and Boolean functions. The Art of Computer Programming. 4.0. Upper Saddle River, NJ: AddisonWesley. pp. 64–74. ISBN 0321534964.
External links
Categories:
Wikimedia Foundation. 2010.
Look at other dictionaries:
Median graph — The median of three vertices in a median 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(a,b,c) that belongs to shortest… … Wikipedia
Álgebra mediana — En matemática, un álgebra mediana es un conjunto con un operador ternario < x,y,z > que satisface los siguientes axiomas, los cuales generalizan la noción de mediana o función mayorante, como una función booleana: Absorción por la derecha:… … Wikipedia Español
Formelsammlung elementare Algebra — Dieser Artikel ist eine Formelsammlung zum Thema Elementare Algebra. Es werden mathematische Symbole verwendet, die im Artikel Mathematische Symbole erläutert werden. Inhaltsverzeichnis … Deutsch Wikipedia
List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… … Wikipedia
Majority function — In Boolean logic, the majority function (also called the median operator) 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. Alternatively, representing true… … Wikipedia
Clique (graph theory) — A graph with 23 1 vertex cliques (its vertices), 42 2 vertex cliques (its edges), 19 3 vertex cliques (the light blue triangles), and 2 4 vertex cliques (dark blue). Six of the edges and 11 of the triangles form maximal cliques. The two dark blue … Wikipedia
Boolean algebras canonically defined — Boolean algebras have been formally defined variously as a kind of lattice and as a kind of ring. This article presents them more neutrally but equally formally as simply the models of the equational theory of two values, and observes the… … Wikipedia
Principles and Standards for School Mathematics — are guidelines produced by the National Council of Teachers of Mathematics (NCTM) in 2000, setting forth recommendations for mathematics educators.[1] They form a national vision for preschool through twelfth grade mathematics education in the US … Wikipedia
2satisfiability — In computer science, 2 satisfiability (abbreviated as 2 SAT or just 2SAT) is the problem of determining whether a collection of two valued (Boolean or binary) variables with constraints on pairs of variables can be assigned values satisfying all… … Wikipedia
Experiment — Experimental redirects here. For the musical classification, see Experimental music. For other uses, see Experiment (disambiguation). Even very young children perform rudimentary experiments in order to learn about the world. An experiment is a… … Wikipedia