Relation de couverture

En mathématiques , et plus particulièrement en théorie de l'ordre , la relation de recouvrement d'un ensemble partiellement ordonné est la relation binaire qui existe entre des éléments comparables qui sont immédiatement voisins. La relation de recouvrement est couramment utilisée pour exprimer graphiquement l'ordre partiel au moyen du diagramme de Hasse .

Soit un ensemble d'ordre partiel . Comme d'habitude, soit la relation sur telle que si et seulement si et .

Soit et soient des éléments de .

Alors couvre , écrit , si et il n'existe aucun élément tel que . De manière équivalente, couvre si l' intervalle est l'ensemble à deux éléments .

Lorsque , on dit que est une couverture de . Certains auteurs utilisent également le terme couverture pour désigner une telle paire dans la relation de couverture.

• Dans un ensemble fini linéairement ordonné {1, 2, ..., n }, i + 1 couvre i pour tout i compris entre 1 et n − 1 (et il n'y a pas d'autres relations de recouvrement).
• Dans l' algèbre booléenne de l' ensemble des puissances d'un ensemble S , un sous-ensemble B de S recouvre un sous-ensemble A de S si et seulement si B est obtenu à partir de A en ajoutant un élément non présent dans A .
• Dans le réseau de Young , formé par les partitions de tous les entiers non négatifs, une partition λ recouvre une partition μ si et seulement si le diagramme de Young de λ est obtenu à partir du diagramme de Young de μ en ajoutant une cellule supplémentaire.
• Le diagramme de Hasse représentant la relation de recouvrement d'un réseau de Tamari est le squelette d'un associaèdre .
• La relation de recouvrement de tout réseau distributif fini forme un graphe médian .
• Sur les nombres réels d'ordre total usuel ≤, l'ensemble de couverture est vide : aucun nombre ne recouvre un autre.

• Si un ensemble partiellement ordonné est fini, sa relation de recouvrement est la réduction transitive de la relation d'ordre partiel. De tels ensembles partiellement ordonnés sont donc complètement décrits par leurs diagrammes de Hasse. En revanche, dans un ordre dense , comme les nombres rationnels d'ordre standard, aucun élément ne recouvre un autre.

• Knuth, Donald E. (2006), L'art de la programmation informatique , volume 4, fascicule 4 , Addison-Wesley, ISBN 0-321-33570-8.
• Stanley, Richard P. (1997), Enumerative Combinatorics, vol. 1 (2e éd.), Cambridge University Press , ISBN 0-521-55309-1.
• Brian A. Davey et Hilary Ann Priestley (2002), Introduction aux réseaux et à l'ordre (2e éd.), Cambridge University Press, ISBN 0-521-78451-4, LCCN 2001043910.