Skip to Main content Skip to Navigation
Conference papers

Structure and enumeration of $(3+1)$-free posets (extended abstract)

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-01229713
Contributor : Alain Monteil <>
Submitted on : Tuesday, November 17, 2015 - 10:20:26 AM
Last modification on : Wednesday, October 14, 2020 - 4:16:41 AM
Long-term archiving on: : Thursday, February 18, 2016 - 11:42:56 AM

File

dmAS0122.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01229713, version 1

Collections

Citation

Mathieu Guay-Paquet, Alejandro H. Morales, Eric Rowland. Structure and enumeration of $(3+1)$-free posets (extended abstract). 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. pp.253-264. ⟨hal-01229713⟩

Share

Metrics

Record views

52

Files downloads

88