On naturally labelled posets and permutations avoiding 12-34
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912160891797504 |
|---|---|
| author | Bevan, David Cheon, Gi-Sang Kitaev, Sergey |
| author_facet | Bevan, David Cheon, Gi-Sang Kitaev, Sergey |
| contents | A partial order $\prec$ on $[n]$ is naturally labelled (NL) if $x\prec y$ implies $x<y$. We establish a bijection between {3, 2+2}-free NL posets and 12-34-avoiding permutations, determine functional equations satisfied by their generating function, and use series analysis to investigate their asymptotic growth, presenting evidence of stretched exponential behaviour. We also exhibit bijections between 3-free NL posets and various other objects, and determine their generating function. The connection between our results and a hierarchy of combinatorial objects related to interval orders is described. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_08023 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On naturally labelled posets and permutations avoiding 12-34 Bevan, David Cheon, Gi-Sang Kitaev, Sergey Combinatorics 06A07, 05A05, 05A15, 05A16 A partial order $\prec$ on $[n]$ is naturally labelled (NL) if $x\prec y$ implies $x<y$. We establish a bijection between {3, 2+2}-free NL posets and 12-34-avoiding permutations, determine functional equations satisfied by their generating function, and use series analysis to investigate their asymptotic growth, presenting evidence of stretched exponential behaviour. We also exhibit bijections between 3-free NL posets and various other objects, and determine their generating function. The connection between our results and a hierarchy of combinatorial objects related to interval orders is described. |
| title | On naturally labelled posets and permutations avoiding 12-34 |
| topic | Combinatorics 06A07, 05A05, 05A15, 05A16 |
| url | https://arxiv.org/abs/2311.08023 |