Treillis de réorientations acycliques et leurs treillis quotients

Étant donné un graphe orienté acyclique D, on considère l’ensemble de ses réorientations acycliques, ordonnées par inclusion des ensembles d’arcs retournés. On obtient par exemple un treillis booléen lorsque D est une forêt, et l’ordre faible lorsque D est un tournoi. Nous caractériserons les graphes orientés acycliques D pour lesquels cet ordre est un treillis, et même un treillis semidistributif. Dans ce dernier cas, nous présenterons un modèle combinatoire pour les sup irréductibles de ce treillis, et montrerons comment lire les représentations canoniques par sup et l’ordre de forçage sur les sup irréductibles pour manipuler les congruences et les quotients de ces treillis. Ceci amène naturellement à des généralisations graphiques des associaèdres, des permutarbrèdres, et plus généralement des quotientopes, construits à partir de polytopes de tessons graphiques. Cet exposé est basé sur http://arxiv.org/abs/2111.12387.