A relation on 132-avoiding permutation patterns
A permutation $σ$ contains the permutation $τ$ if there is a subsequence of $σ$ order isomorphic to $τ$. A permutation $σ$ is $τ$-<i>avoiding</i> if it does not contain the permutation $τ$. For any $n$, the <i>popularity...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2015-12-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/2141/pdf |
| _version_ | 1827323791761473536 |
|---|---|
| author | Natalie Aisbett |
| author_facet | Natalie Aisbett |
| author_sort | Natalie Aisbett |
| collection | DOAJ |
| description | A permutation $σ$ contains the permutation $τ$ if there is a subsequence of $σ$ order isomorphic to $τ$. A permutation $σ$ is $τ$-<i>avoiding</i> if it does not contain the permutation $τ$. For any $n$, the <i>popularity</i> of a permutation $τ$, denoted $A$<sub>$n$</sub>($τ$), is the number of copies of $τ$ contained in the set of all 132-avoiding permutations of length $n$. Rudolph conjectures that for permutations $τ$ and $μ$ of the same length, $A$<sub>$n$</sub>($τ$) ≤ $A$<sub>$n$</sub>($μ$) for all $n$ if and only if the spine structure of $τ$ is less than or equal to the spine structure of $μ$ in refinement order. We prove one direction of this conjecture, by showing that if the spine structure of $τ$ is less than or equal to the spine structure of $μ$, then $A$<sub>$n$</sub>($τ$) ≤ $A$<sub>$n$</sub>($μ$) for all $n$. We disprove the opposite direction by giving a counterexample, and hence disprove the conjecture. |
| first_indexed | 2024-04-25T01:58:13Z |
| format | Article |
| id | doaj.art-1dc1b67b410f4622bc2127e08ac0b8d2 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:13Z |
| publishDate | 2015-12-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-1dc1b67b410f4622bc2127e08ac0b8d22024-03-07T15:28:21ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502015-12-01Vol. 17 no.2Combinatorics10.46298/dmtcs.21412141A relation on 132-avoiding permutation patternsNatalie Aisbett0School of Mathematics and statistics [Sydney]A permutation $σ$ contains the permutation $τ$ if there is a subsequence of $σ$ order isomorphic to $τ$. A permutation $σ$ is $τ$-<i>avoiding</i> if it does not contain the permutation $τ$. For any $n$, the <i>popularity</i> of a permutation $τ$, denoted $A$<sub>$n$</sub>($τ$), is the number of copies of $τ$ contained in the set of all 132-avoiding permutations of length $n$. Rudolph conjectures that for permutations $τ$ and $μ$ of the same length, $A$<sub>$n$</sub>($τ$) ≤ $A$<sub>$n$</sub>($μ$) for all $n$ if and only if the spine structure of $τ$ is less than or equal to the spine structure of $μ$ in refinement order. We prove one direction of this conjecture, by showing that if the spine structure of $τ$ is less than or equal to the spine structure of $μ$, then $A$<sub>$n$</sub>($τ$) ≤ $A$<sub>$n$</sub>($μ$) for all $n$. We disprove the opposite direction by giving a counterexample, and hence disprove the conjecture.https://dmtcs.episciences.org/2141/pdfpermutationspermutation patternpopularity[info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | Natalie Aisbett A relation on 132-avoiding permutation patterns Discrete Mathematics & Theoretical Computer Science permutations permutation pattern popularity [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | A relation on 132-avoiding permutation patterns |
| title_full | A relation on 132-avoiding permutation patterns |
| title_fullStr | A relation on 132-avoiding permutation patterns |
| title_full_unstemmed | A relation on 132-avoiding permutation patterns |
| title_short | A relation on 132-avoiding permutation patterns |
| title_sort | relation on 132 avoiding permutation patterns |
| topic | permutations permutation pattern popularity [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/2141/pdf |
| work_keys_str_mv | AT natalieaisbett arelationon132avoidingpermutationpatterns AT natalieaisbett relationon132avoidingpermutationpatterns |