Structure and enumeration of (3+1)-free posets
Authors:
- Mathieu Guay-PaquetMGMathieu Guay-Paquet
- Alejandro H. MoralesAMAlejandro H. Morales
- Eric RowlandEREric Rowland
Preprint
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 play a central role in the (3+1)-free conjecture of Stanley and Stembridge. Lewis and Zhang have enumerated (3+1)-free posets in the graded case by decomposing them into bipartite graphs, but until now the general enumeration problem has remained open. We give a finer decomposition into bipartite graphs which applies to all (3+1)-free posets and obtain generating functions which count (3+1)-free posets with labelled or unlabelled vertices. Using this decomposition, we obtain a decomposition of the automorphism group and asymptotics for the number of (3+1)-free posets.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Enumeration of Graded (3 + 1)-Avoiding PosetsDiscrete Mathematics & Theoretical Computer Science, 2012
- Enumerating -free posets by the number of minimal elements and other statisticsDiscrete Applied Mathematics, 2011
- -free posets, ascent sequences and pattern avoiding permutationsJournal of Combinatorial Theory, Series A, 2010
- Total nonnegativity and (3+1)-free posetsJournal of Combinatorial Theory, Series A, 2003
- Graph colorings and related symmetric functions: ideas and applications A description of results, interesting applications, & notable open problemsDiscrete Mathematics, 1998
- Combinatorial Species and Tree-like Structures1997
- A Symmetric Function Generalization of the Chromatic Polynomial of a GraphAdvances in Mathematics, 1995
- The Book of Traces1995
- On immanants of Jacobi-Trudi matrices and permutations with restricted positionJournal of Combinatorial Theory, Series A, 1993