# A relation on 132-avoiding permutation patterns

Abstract : A permutation $σ$ contains the permutation $τ$ if there is a subsequence of $σ$ order isomorphic to $τ$. A permutation $σ$ is $τ$-avoiding if it does not contain the permutation $τ$. For any $n$, the popularity of a permutation $τ$, denoted $A$n(τ), 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$n$($τ$) ≤ $A$n(μ) 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$n$($τ$) ≤ $A$$n$($μ$) for all $n$. We disprove the opposite direction by giving a counterexample, and hence disprove the conjecture.
Keywords :
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no.2 (2), pp.285-302

Littérature citée [6 références]

https://hal.inria.fr/hal-01349056
Contributeur : Coordination Episciences Iam <>
Soumis le : mardi 26 juillet 2016 - 17:57:33
Dernière modification le : jeudi 7 septembre 2017 - 01:03:44

### Fichier

2375-9839-1-PB.pdf
Accord explicite pour ce dépôt

### Identifiants

• HAL Id : hal-01349056, version 1

### Citation

Natalie Aisbett. A relation on 132-avoiding permutation patterns. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no.2 (2), pp.285-302. 〈hal-01349056〉

### Métriques

Consultations de la notice

## 42

Téléchargements de fichiers