Median algebra




In mathematics, a median algebra is a set with a ternary operation ⟨x,y,z⟩{displaystyle langle x,y,zrangle }langle x,y,zrangle satisfying a set of axioms which generalise the notion of median or majority function, as a Boolean function.


The axioms are



  1. ⟨x,y,y⟩=y{displaystyle langle x,y,yrangle =y}langle x,y,yrangle =y

  2. ⟨x,y,z⟩=⟨z,x,y⟩{displaystyle langle x,y,zrangle =langle z,x,yrangle }langle x,y,zrangle =langle z,x,yrangle

  3. ⟨x,y,z⟩=⟨x,z,y⟩{displaystyle langle x,y,zrangle =langle x,z,yrangle }langle x,y,zrangle =langle x,z,yrangle

  4. ⟨⟨x,w,y⟩,w,z⟩=⟨x,w,⟨y,w,z⟩⟩{displaystyle langle langle x,w,yrangle ,w,zrangle =langle x,w,langle y,w,zrangle rangle }langle langle x,w,yrangle ,w,zrangle =langle x,w,langle y,w,zrangle 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,yrangle =y}langle x,y,yrangle =y

  • ⟨u,v,⟨u,w,x⟩⟩=⟨u,x,⟨w,u,v⟩⟩{displaystyle langle u,v,langle u,w,xrangle rangle =langle u,x,langle w,u,vrangle rangle }langle u,v,langle u,w,xrangle rangle =langle u,x,langle w,u,vrangle 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,zrangle =(xvee y)wedge (yvee z)wedge (zvee x)}langle x,y,zrangle =(xvee y)wedge (yvee z)wedge (zvee 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{displaystyle 0}{displaystyle 0} and 1{displaystyle 1}1 satisfying ⟨0,x,1⟩=x{displaystyle langle 0,x,1rangle =x}{displaystyle langle 0,x,1rangle =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}x, y{displaystyle y}y, and z{displaystyle z}z there is a unique vertex ⟨x,y,z⟩{displaystyle langle x,y,zrangle }langle x,y,zrangle that belongs to shortest paths between any two of x{displaystyle x}x, y{displaystyle y}y, and z{displaystyle z}z. If this is the case, then the operation ⟨x,y,z⟩{displaystyle langle x,y,zrangle }langle x,y,zrangle 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]}{displaystyle [x,z]} to be the set of elements y{displaystyle y}y such that ⟨x,y,z⟩=y{displaystyle langle x,y,zrangle =y}{displaystyle langle x,y,zrangle =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)}(x,z) such that the interval [x,z]{displaystyle [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..mw-parser-output cite.citation{font-style:inherit}.mw-parser-output q{quotes:"""""""'""'"}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-limited a,.mw-parser-output .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}


  • 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: Addison-Wesley. pp. 64–74. ISBN 0-321-53496-4.



External links


  • Median Algebra Proof



-

Popular posts from this blog

Westermarck effect

Image
This article includes a list of references, but its sources remain unclear because it has insufficient inline citations . Please help to improve this article by introducing more precise citations. (November 2014) (Learn how and when to remove this template message) The Westermarck effect , or reverse sexual imprinting, is a hypothetical psychological effect through which people who live in close domestic proximity during the first few years of their lives become desensitized to sexual attraction. This phenomenon was first hypothesized by Finnish anthropologist Edvard Westermarck in his book The History of Human Marriage (1891) as one explanation for the incest taboo. Observations interpreted as evidence for the Westermarck effect have since been made in many places and cultures, including in the Israeli kibbutz system, and the Chinese Shim-pua marriage customs, as well as in biologically-related families. In the case of the Israeli kibbutzim (collective farms), children...
Read more

Orthodox Church in America

Image
For other uses, see Orthodox Church in America (disambiguation). Orthodox Church in America Recognition Autocephaly recognized by the Russian (since 1970), Bulgarian, Georgian, Polish, and Czech and Slovak Churches [1] Primate Metropolitan Tikhon (Mollard) [2] Headquarters Oyster Bay Cove, New York, United States Territory United States, Canada Possessions Mexico, formerly Australia and South America Language English, Church Slavonic, Spanish, Russian, Arabic, Koine Greek, Romanian, Bulgarian, Albanian Members 1 million adherents, [3] 90,000 (U.S. only) [a] [5] Bishops 14 [5] Parishes 700 [5] Monasteries 20 [5] Website oca.org Part of a series on the Eastern Orthodox Church Mosaic of Christ Pantocrator, Hagia Sophia Overview Structure Theology (History of theology) Liturgy Church history Holy Mysteries View of salvation View of Mary View of icons Background Crucifixion / Resurrection / Asc...
Read more

Italian cuisine

Image
"Italian restaurant" redirects here. For the television series, see Italian Restaurant. Some typical Italian gastronomic products in a window display in Imola Pizza is one of the world's most popular foods and a common fast food item Part of a series on the Culture of Italy History People Languages Traditions Mythology and folklore Mythology folklore Cuisine Festivals Religion Art Literature Music and performing arts Music Media Television Cinema Sport Monuments World Heritage Sites Symbols Flag Coat of arms Italy portal v t e Italian cuisine History Ancient Roman cuisine Medieval cuisine Early modern cuisine Contemporary cuisine Regional cuisines Apulian cuisine Lombard cuisine Neapolitan cuisine Roman cuisine Sicilian cuisine Venetian cuisine Cuisine of Abruzzo Cuisine of Sardinia Lists Chefs Dishes Pas...
Read more