Geodesic
Pattern Avoidance in Task-Precedence Posets
Discrete mathematics & theoretical computer science, Permutation Patterns 2015, Tome 18 (2015-2016) no. 2.

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2016_18_2_a5,
     author = {Paukner, Mitchell and Pepin, Lucy and Riehl, Manda and Wieser, Jarred},
     title = {Pattern {Avoidance} in {Task-Precedence} {Posets}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {18},
     number = {2},
     year = {2015-2016},
     doi = {10.46298/dmtcs.1324},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.1324/}
}
TY  - JOUR
AU  - Paukner, Mitchell
AU  - Pepin, Lucy
AU  - Riehl, Manda
AU  - Wieser, Jarred
TI  - Pattern Avoidance in Task-Precedence Posets
JO  - Discrete mathematics & theoretical computer science
PY  - 2015-2016
VL  - 18
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.1324/
DO  - 10.46298/dmtcs.1324
LA  - en
ID  - DMTCS_2016_18_2_a5
ER  - 
%0 Journal Article
%A Paukner, Mitchell
%A Pepin, Lucy
%A Riehl, Manda
%A Wieser, Jarred
%T Pattern Avoidance in Task-Precedence Posets
%J Discrete mathematics & theoretical computer science
%D 2015-2016
%V 18
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.1324/
%R 10.46298/dmtcs.1324
%G en
%F DMTCS_2016_18_2_a5
Paukner, Mitchell; Pepin, Lucy; Riehl, Manda; Wieser, Jarred. Pattern Avoidance in Task-Precedence Posets. Discrete mathematics & theoretical computer science, Permutation Patterns 2015, Tome 18 (2015-2016) no. 2. doi : 10.46298/dmtcs.1324. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.1324/

Cité par Sources :