Mathieu Guay-Paquet ; Alejandro H. Morales ; Eric Rowland
-
Structure and enumeration of (3+1)-free posets (extended abstract)
dmtcs:12809 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2013,
DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)
-
https://doi.org/10.46298/dmtcs.12809
Structure and enumeration of (3+1)-free posets (extended abstract)Conference paper
Authors: Mathieu Guay-Paquet 1; Alejandro H. Morales 1; Eric Rowland 1
NULL##NULL##NULL
Mathieu Guay-Paquet;Alejandro H. Morales;Eric Rowland
1 Laboratoire de combinatoire et d'informatique mathématique [Montréal]
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 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.