Pattern Avoidance in Task-Precedence Posets
We have extended classical pattern avoidance to a new structure: multiple task-precedence posets whose Hasse diagrams have three levels, which we will call diamonds. The vertices of each diamond are assigned labels which are compatible with the poset. A corresponding permutation is formed by reading...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2016-06-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/1324/pdf |
| _version_ | 1827323786234429440 |
|---|---|
| author | Mitchell Paukner Lucy Pepin Manda Riehl Jarred Wieser |
| author_facet | Mitchell Paukner Lucy Pepin Manda Riehl Jarred Wieser |
| author_sort | Mitchell Paukner |
| collection | DOAJ |
| description | We have extended classical pattern avoidance to a new structure: multiple
task-precedence posets whose Hasse diagrams have three levels, which we will
call diamonds. The vertices of each diamond are assigned labels which are
compatible with the poset. A corresponding permutation is formed by reading
these labels by increasing levels, and then from left to right. We used Sage to
form enumerative conjectures for the associated permutations avoiding
collections of patterns of length three, which we then proved. We have
discovered a bijection between diamonds avoiding 132 and certain generalized
Dyck paths. We have also found the generating function for descents, and
therefore the number of avoiders, in these permutations for the majority of
collections of patterns of length three. An interesting application of this
work (and the motivating example) can be found when task-precedence posets
represent warehouse package fulfillment by robots, in which case avoidance of
both 231 and 321 ensures we never stack two heavier packages on top of a
lighter package. |
| first_indexed | 2024-04-25T01:58:07Z |
| format | Article |
| id | doaj.art-0aac83d88e55456ca05c8a042ae11b94 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:07Z |
| publishDate | 2016-06-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-0aac83d88e55456ca05c8a042ae11b942024-03-07T15:30:37ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502016-06-01Vol. 18 no. 2, Permutation...Permutation Patterns10.46298/dmtcs.13241324Pattern Avoidance in Task-Precedence PosetsMitchell PauknerLucy PepinManda RiehlJarred WieserWe have extended classical pattern avoidance to a new structure: multiple task-precedence posets whose Hasse diagrams have three levels, which we will call diamonds. The vertices of each diamond are assigned labels which are compatible with the poset. A corresponding permutation is formed by reading these labels by increasing levels, and then from left to right. We used Sage to form enumerative conjectures for the associated permutations avoiding collections of patterns of length three, which we then proved. We have discovered a bijection between diamonds avoiding 132 and certain generalized Dyck paths. We have also found the generating function for descents, and therefore the number of avoiders, in these permutations for the majority of collections of patterns of length three. An interesting application of this work (and the motivating example) can be found when task-precedence posets represent warehouse package fulfillment by robots, in which case avoidance of both 231 and 321 ensures we never stack two heavier packages on top of a lighter package.https://dmtcs.episciences.org/1324/pdfmathematics - combinatorics |
| spellingShingle | Mitchell Paukner Lucy Pepin Manda Riehl Jarred Wieser Pattern Avoidance in Task-Precedence Posets Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics |
| title | Pattern Avoidance in Task-Precedence Posets |
| title_full | Pattern Avoidance in Task-Precedence Posets |
| title_fullStr | Pattern Avoidance in Task-Precedence Posets |
| title_full_unstemmed | Pattern Avoidance in Task-Precedence Posets |
| title_short | Pattern Avoidance in Task-Precedence Posets |
| title_sort | pattern avoidance in task precedence posets |
| topic | mathematics - combinatorics |
| url | https://dmtcs.episciences.org/1324/pdf |
| work_keys_str_mv | AT mitchellpaukner patternavoidanceintaskprecedenceposets AT lucypepin patternavoidanceintaskprecedenceposets AT mandariehl patternavoidanceintaskprecedenceposets AT jarredwieser patternavoidanceintaskprecedenceposets |