Structure and enumeration of $(3+1)$-free posets (extended abstract)
Résumé
A poset is $(3+1)$-free if it does not contain the disjoint union of chains of length 3 and 1 as an induced subposet. These posets are the subject of the $(3+1)$-free conjecture of Stanley and Stembridge. Recently, Lewis and Zhang have enumerated $\textit{graded}$ $(3+1)$-free posets, but until now the general enumeration problem has remained open. We enumerate all $(3+1)$-free posets by giving a decomposition into bipartite graphs, and obtain generating functions for $(3+1)$-free posets with labelled or unlabelled vertices.
Un poset sans $(3 + 1)$ est un poset qui n’a pas de sous-poset induit formé de deux chaînes disjointes de longueur 3 et 1. Ces posets sont l’objet de la conjecture $(3+1)$ de Stanley et Stembridge. Récemment, Lewis et Zhang ont énuméré les posets $\textit{étagés}$ sans $(3 + 1)$, mais en général la question d’énumération est restée ouverte jusqu'à maintenant. Nous énumérons tous les posets sans $(3 + 1)$ en donnant une décomposition de ces posets en graphes bipartis, et obtenons des fonctions génératrices qui les énumèrent, qu’ils soient étiquetés ou non.
Origine : Fichiers éditeurs autorisés sur une archive ouverte