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)Article

Authors: Mathieu Guay-Paquet 1; Alejandro H. Morales 1; Eric Rowland 1

  • 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 $\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.


Volume: DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)
Section: Proceedings
Published on: January 1, 2013
Imported on: November 21, 2016
Keywords: (3+1)-free posets,trace monoid,generating functions,chromatic symmetric function,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada

Consultation statistics

This page has been seen 97 times.
This article's PDF has been downloaded 93 times.