nLab
covering relation

The covering relation

Warning: Tentative.

Idea

The covering relation on a structure (generally already equipped with other relations) is a binary relation such that xx is related to yy if and only if yy is (in an appropriate sense) an immediate (and only immediate) successor of xx.

In a poset

A pair (x,y)(x,y) in a poset satisfies the covering relation if x<yx \lt y but there is no zz such that x<zx \lt z and z<yz \lt y. In other words, the interval [x,y]={zxzy}[x,y] = \{z \mid x \leq z \leq y\} contains exactly two elements xx and yy. In this case, you would say that “yy covers xx”.

In a directed graph

A pair (x,y)(x,y) of vertices in a directed graph or quiver satisfies the covering relation if there is an edge xyx \to y but there is no other path from xx to yy.

Common generalisation

Given any binary relation \sim on a set SS, a pair (x,y)(x,y) of elements of SS satisfies the covering relation if the only sequence x=z 0,,z n=yx = z_0, \ldots, z_n = y such that x ix i+1x_i \sim x_{i+1} satisfies n=1n = 1 (so xyx \sim y). Then the covering relation on a poset is the covering relation of \leq, and the covering relation in a directed graph is the covering relation of the adjacency relation of the graph.

References

Revised on November 21, 2016 09:15:06 by Noam Zeilberger (176.187.66.101)