Counting (3+1) - Avoiding permutations

2011/02/28 by M. D. Atkinson, Atkinson, M. D., Bruce E. Sagan +3
Computer Science · Mathematics · #05A05 #05A15 #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1102.5568

openalex publication_date 2011/02/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A poset is \it (\3+\1)-free if it contains no induced subposet isomorphic to the disjoint union of a 3-element chain and a 1-element chain. These posets are of interest because of their connection with interval orders and their appearance in the (\3+\1)-free Conjecture of Stanley and Stembridge. The dimension 2 posets P are exactly the ones which have an associated permutation π where i\prec j in P if and only if i

Citations

• Simple permutations and pattern restricted permutations
• A Chromatic Symmetric Function in Noncommuting Variables

Related

• Enumerating (2+2)-free posets by the number of minimal elements and other statistics
• On a conjecture about enumerating (2+2)-free posets
• Enumerating (2+2)-free posets by indistinguishable elements
• A Proof of the Alternate Thomassé Conjecture for Countable NE-Free Posets
• Exact forbidden subposet results using Chain decompositions of the Cycle