Proofs of Conjectures about Pattern-Avoiding Linear Extensions
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...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2019-10-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/5438/pdf |
| _version_ | 1797270019451650048 |
|---|---|
| author | Colin Defant |
| author_facet | Colin Defant |
| author_sort | Colin Defant |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:57:37Z |
| format | Article |
| id | doaj.art-9be41d3bcfea47e8804f79f20fb1e341 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:57:37Z |
| publishDate | 2019-10-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-9be41d3bcfea47e8804f79f20fb1e3412024-03-07T15:40:07ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502019-10-01vol. 21 no. 4Combinatorics10.23638/DMTCS-21-4-165438Proofs of Conjectures about Pattern-Avoiding Linear ExtensionsColin DefantAfter 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.https://dmtcs.episciences.org/5438/pdfmathematics - combinatorics05a05, 05a15, 05a16 |
| spellingShingle | Colin Defant Proofs of Conjectures about Pattern-Avoiding Linear Extensions Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics 05a05, 05a15, 05a16 |
| title | Proofs of Conjectures about Pattern-Avoiding Linear Extensions |
| title_full | Proofs of Conjectures about Pattern-Avoiding Linear Extensions |
| title_fullStr | Proofs of Conjectures about Pattern-Avoiding Linear Extensions |
| title_full_unstemmed | Proofs of Conjectures about Pattern-Avoiding Linear Extensions |
| title_short | Proofs of Conjectures about Pattern-Avoiding Linear Extensions |
| title_sort | proofs of conjectures about pattern avoiding linear extensions |
| topic | mathematics - combinatorics 05a05, 05a15, 05a16 |
| url | https://dmtcs.episciences.org/5438/pdf |
| work_keys_str_mv | AT colindefant proofsofconjecturesaboutpatternavoidinglinearextensions |