Résumé de séminaire

Résumé :

M'intéressant à l'étude morphologique des ensembles ordonnés finis au travers des sous-structures orthogonales que sont les chaînes et les antichaînes, je vais être amené à introduire la classe des ordres chaîne dominés. Ces ordres sont des ordres admettant une famille partitive de ses éléments en deux ensembles. L'un de ces ensembles induit un chemin dans son digraphe de couverture et l'autre induit un sous-digraphe sans aucun arc.

Après avoir rappelé les définitions de base nécessaires à l'exposé, je montrerai que cette classe d'ordre est l'intersection des deux classes connues que sont les ordres d'intervalles et les treillis tronqués. Puis, en utilisant la notion de couplage maximum dans les graphes, je montrerai que le calcul du nombre de sauts des ordres chaîne dominés est alors polynomial.

Enfin, je montrerai que tout ordre d'intervalles peut se plonger dans un ordre de cette classe et que leurs dimensions ne diffèrent pas de plus deux.

Références :

Email : Jimmy.Leblet@univ-nantes.fr