Covering relation

<h2 id="definition">Definition</h2>
Let 
 
 
 
 X
 
 
 {\displaystyle X}
 
 be a set with a partial order 
 
 
 
 ≤
 
 
 {\displaystyle \leq }
 
.
As usual, let 
 
 
 
 <
 
 
 {\displaystyle <}
 
 be the relation on 
 
 
 
 X
 
 
 {\displaystyle X}
 
 such that 
 
 
 
 x
 <
 y
 
 
 {\displaystyle x<y}
 
 if and only if 
 
 
 
 x
 ≤
 y
 
 
 {\displaystyle x\leq y}
 
 and 
 
 
 
 x
 ≠
 y
 
 
 {\displaystyle x\neq y}
 
.
Let 
 
 
 
 x
 
 
 {\displaystyle x}
 
 and 
 
 
 
 y
 
 
 {\displaystyle y}
 
 be elements of 
 
 
 
 X
 
 
 {\displaystyle X}
 
.
Then 
 
 
 
 y
 
 
 {\displaystyle y}
 
 covers 
 
 
 
 x
 
 
 {\displaystyle x}
 
, written 
 
 
 
 x
 ⋖
 y
 
 
 {\displaystyle x\lessdot y}
 
,
if 
 
 
 
 x
 <
 y
 
 
 {\displaystyle x<y}
 
 and there is no element 
 
 
 
 z
 
 
 {\displaystyle z}
 
 such that 
 
 
 
 x
 <
 z
 <
 y
 
 
 {\displaystyle x<z<y}
 
. Equivalently, 
 
 
 
 y
 
 
 {\displaystyle y}
 
 covers 
 
 
 
 x
 
 
 {\displaystyle x}
 
 if the <a href="/facts/Partially_ordered_set/qb4a3FAX">interval</a> 
 
 
 
 [
 x
 ,
 y
 ]
 
 
 {\displaystyle [x,y]}
 
 is the two-element set 
 
 
 
 {
 x
 ,
 y
 }
 
 
 {\displaystyle \{x,y\}}
 
.
When 
 
 
 
 x
 ⋖
 y
 
 
 {\displaystyle x\lessdot y}
 
, it is said that 
 
 
 
 y
 
 
 {\displaystyle y}
 
 is a cover of 
 
 
 
 x
 
 
 {\displaystyle x}
 
. Some authors also use the term cover to denote any such pair 
 
 
 
 (
 x
 ,
 y
 )
 
 
 {\displaystyle (x,y)}
 
 in the covering relation.

<h2 id="examples">Examples</h2>
<ul><li>In a finite <a href="/facts/Linearly_ordered/xnTtmuYJ">linearly ordered</a> set {1, 2, ..., n}, i + 1 covers i for all i between 1 and n − 1 (and there are no other covering relations).</li>
<li>In the <a href="/facts/Boolean_algebra_(structure)/cHbo65jm">Boolean algebra</a> of the <a href="/facts/Power_set/FVuf8PDD">power set</a> of a set S, a subset B of S covers a subset A of S if and only if B is obtained from A by adding one element not in A.</li>
<li>In <a href="/facts/Young%27s_lattice/X90jpt0r">Young's lattice</a>, formed by the <a href="/facts/Partition_(number_theory)/LtyXWqwH">partitions</a> of all nonnegative integers, a partition λ covers a partition μ if and only if the <a href="/facts/Young_diagram/e5lI4bck">Young diagram</a> of λ is obtained from the Young diagram of μ by adding an extra cell.</li>
<li>The Hasse diagram depicting the covering relation of a <a href="/facts/Tamari_lattice/UtSr0cMH">Tamari lattice</a> is the <a href="/facts/N-skeleton/EAt2F7tC">skeleton</a> of an <a href="/facts/Associahedron/2ajjs785">associahedron</a>.</li>
<li>The covering relation of any finite <a href="/facts/Distributive_lattice/97DFz1cu">distributive lattice</a> forms a <a href="/facts/Median_graph/xl4m0C9I">median graph</a>.</li>
<li>On the <a href="/facts/Real_number/R02gw5Pb">real numbers</a> with the usual total order ≤, the cover set is empty: no number covers another.</li></ul>
<h2 id="properties">Properties</h2>
<ul><li>If a partially ordered set is finite, its covering relation is the <a href="/facts/Transitive_reduction/UemedaAE">transitive reduction</a> of the partial order relation. Such partially ordered sets are therefore completely described by their Hasse diagrams. On the other hand, in a <a href="/facts/Dense_order/EVVQI3V6">dense order</a>, such as the <a href="/facts/Rational_number/VJQmyY05">rational numbers</a> with the standard order, no element covers another.</li></ul>

<ul><li><a href="/facts/Donald_Knuth/GozNzDM6">Knuth, Donald E.</a> (2006), <a href="/facts/The_Art_of_Computer_Programming/MR1bMD9e">The Art of Computer Programming</a>, Volume 4, Fascicle 4, Addison-Wesley, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-321-33570-8.</li>
<li><a href="/facts/Richard_P._Stanley/8bQ4QrLM">Stanley, Richard P.</a> (1997), <a href="http://www-math.mit.edu/~rstan/ec/">Enumerative Combinatorics</a>, vol. 1 (2nd ed.), <a href="/facts/Cambridge_University_Press/fgEBSSRq">Cambridge University Press</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-521-55309-1.</li>
<li>Brian A. Davey; <a href="/facts/Hilary_Priestley/d8r8I53C">Hilary Ann Priestley</a> (2002), <a href="/facts/Introduction_to_Lattices_and_Order/YrpGPbUq">Introduction to Lattices and Order</a> (2nd ed.), Cambridge University Press, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-521-78451-4, <a href="/facts/LCCN_(identifier)/5hb5Cw2V">LCCN</a> <a href="https://lccn.loc.gov/2001043910">2001043910</a>.</li></ul>

Covering relation open-in-new

Covering relation