Covering relation
Appearance
![](https://upload.wikimedia.org/wikipedia/commons/thumb/e/ea/Hasse_diagram_of_powerset_of_3.svg/300px-Hasse_diagram_of_powerset_of_3.svg.png)
Inmathematics,especiallyorder theory,thecovering relationof apartially ordered setis thebinary relationwhich holds betweencomparableelements that are immediate neighbours. The covering relation is commonly used to graphically express the partial order by means of theHasse diagram.
Definition[edit]
Letbe a set with a partial order. As usual, letbe the relation onsuch thatif and only ifand.
Letandbe elements of.
Thencovers,written, ifand there is no elementsuch that.Equivalently,coversif theintervalis the two-element set.
When,it is said thatis a cover of.Some authors also use the term cover to denote any such pairin the covering relation.
Examples[edit]
- In a finitelinearly orderedset {1, 2,...,n},i+ 1 coversifor allibetween 1 andn− 1 (and there are no other covering relations).
- In theBoolean algebraof thepower setof a setS,a subsetBofScovers a subsetAofSif and only ifBis obtained fromAby adding one element not inA.
- InYoung's lattice,formed by thepartitionsof all nonnegative integers, a partitionλcovers a partitionμif and only if theYoung diagramofλis obtained from the Young diagram ofμby adding an extra cell.
- The Hasse diagram depicting the covering relation of aTamari latticeis theskeletonof anassociahedron.
- The covering relation of any finitedistributive latticeforms amedian graph.
- On thereal numberswith the usual total order ≤, the cover set is empty: no number covers another.
Properties[edit]
- If a partially ordered set is finite, its covering relation is thetransitive reductionof the partial order relation. Such partially ordered sets are therefore completely described by their Hasse diagrams. On the other hand, in adense order,such as therational numberswith the standard order, no element covers another.
References[edit]
- Knuth, Donald E.(2006),The Art of Computer Programming,Volume 4, Fascicle 4,Addison-Wesley,ISBN0-321-33570-8.
- Stanley, Richard P.(1997),Enumerative Combinatorics,vol. 1 (2nd ed.),Cambridge University Press,ISBN0-521-55309-1.
- Brian A. Davey;Hilary Ann Priestley(2002),Introduction to Lattices and Order(2nd ed.), Cambridge University Press,ISBN0-521-78451-4,LCCN2001043910.