covering relation

The covering relation

Warning: Tentative.


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 satsfies 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, there are exactly two elements zz such that xzyx \leq z \leq y: z=xz = x and z=yz = y. 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.


Revised on February 13, 2011 20:35:37 by Toby Bartels (