Structure and enumeration of (3+1)-free posets
From MaRDI portal
Publication:2256977
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.
Recommendations
- Structure and enumeration of (3+1)-free posets (extended abstract).
- A characterization of (3+1)-free posets
- Asymptotic enumeration of N-free partial orders
- On a conjecture about enumerating \((2+2)\)-free posets
- Enumerating \((\mathbf 2+\mathbf 2)\)-free posets by the number of minimal elements and other statistics
Cites work
- (2+2)-free posets, ascent sequences and pattern avoiding permutations
- A characterization of (3+1)-free posets
- A symmetric function generalization of the chromatic polynomial of a graph
- An Asymptotic Expansion for the Coefficients of Some Formal Power Series
- Asymptotic Enumeration of Partial Orders on a Finite Set
- Counting \(\mathbf {(3+1)}\)-avoiding permutations
- Counting unlabeled structures
- Enumerating \((\mathbf 2+\mathbf 2)\)-free posets by the number of minimal elements and other statistics
- Enumeration of graded (3+1)-avoiding posets
- Graph colorings and related symmetric functions: ideas and applications: A description of results, interesting applications, and notable open problems.
- scientific article; zbMATH DE number 1268810 (Why is no real title available?)
- scientific article; zbMATH DE number 1033382 (Why is no real title available?)
- scientific article; zbMATH DE number 1111371 (Why is no real title available?)
- Incomparability graphs of \((3+1)\)-free posets are \(s\)-positive
- Inhomogeneous sorting
- On immanants of Jacobi-Trudi matrices and permutations with restricted position
- Structure and enumeration of (3+1)-free posets (extended abstract).
- Total nonnegativity and (3+1)-free posets
Cited in
(18)- A class of labeled posets and the Shi arrangement of hyperplanes
- Total nonnegativity and (3+1)-free posets
- Finding balance: split graphs and related classes
- Hereditary semiorders and enumeration of semiorders by dimension
- Four variations on graded posets
- Enumeration of graded (3+1)-avoiding posets
- scientific article; zbMATH DE number 6806834 (Why is no real title available?)
- Catalan pairs and Fishburn triples
- Enumeration of graded \((3+1)\)-avoiding posets
- Structure and enumeration of (3+1)-free posets (extended abstract).
- A characterization of (3+1)-free posets
- On a conjecture about enumerating \((2+2)\)-free posets
- Homogeneous sets in graphs and a chromatic multisymmetric function
- Some progress on the Aharoni-Korman conjecture
- Bijective proof of a conjecture on unit interval posets
- Differential transcendence of Bell numbers and relatives: a Galois theoretic approach
- -chromatic symmetric functions
- Finding large 3-free sets. I. The small \(n\) case
This page was built for publication: Structure and enumeration of \((3+1)\)-free posets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2256977)
