Proofs of conjectures about pattern-avoiding linear extensions

MaRDI QIDQ5207852zbMATH OpenFDO

Authors Colin Defant

Publication date 13 January 2020

Full work available at URL https://arxiv.org/abs/1905.02309, https://dmtcs.episciences.org/5796/pdf

zbMATH Keywords

heaplinear extensionpermutation patternrectangular poset

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16) Combinatorics of partially ordered sets (06A07)

Abstract: After fixing a canonical ordering (or labeling) of the elements of a finite poset, one can associate each linear extension of the poset with a permutation. Some recent papers consider specific families of posets and ask how many linear extensions give rise to permutations that avoid certain patterns. We build off of two of these papers. We first consider pattern avoidance in $k$-ary heaps, where we obtain a general result that proves a conjecture of Levin, Pudwell, Riehl, and Sandberg in a special case. We then prove some conjectures that Anderson, Egge, Riehl, Ryan, Steinke, and Vaughan made about pattern-avoiding linear extensions of rectangular posets.

Recommendations

• Pattern avoidance in extensions of comb-like posets
• Pattern avoiding linear extensions of rectangular posets
• Poset pattern-avoidance problems posed by Yakoubov
• Pattern avoidance in poset permutations
• Pattern avoidance in k-ary heaps

Cited in

(5)

• Pattern avoiding linear extensions of rectangular posets
• Pattern avoidance in extensions of comb-like posets
• Pattern avoidance in k-ary heaps
• scientific article; zbMATH DE number 1192333 (Why is no real title available?)
• Poset pattern-avoidance problems posed by Yakoubov

This page was built for publication: Proofs of conjectures about pattern-avoiding linear extensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207852)