Natalie Aisbett - A relation on 132-avoiding permutation patterns

dmtcs:2141 - Discrete Mathematics & Theoretical Computer Science, December 15, 2015, Vol. 17 no.2 - https://doi.org/10.46298/dmtcs.2141
A relation on 132-avoiding permutation patternsArticle

Authors: Natalie Aisbett 1

  • 1 School of Mathematics and statistics [Sydney]

A permutation $&sigma;$ contains the permutation $&tau;$ if there is a subsequence of $&sigma;$ order isomorphic to $&tau;$. A permutation $&sigma;$ is $&tau;$-<i>avoiding</i> if it does not contain the permutation $&tau;$. For any $n$, the <i>popularity</i> of a permutation $&tau;$, denoted $A$<sub>$n$</sub>($&tau;$), is the number of copies of $&tau;$ contained in the set of all 132-avoiding permutations of length $n$. Rudolph conjectures that for permutations $&tau;$ and $&mu;$ of the same length, $A$<sub>$n$</sub>($&tau;$) ≤ $A$<sub>$n$</sub>($&mu;$) for all $n$ if and only if the spine structure of $&tau;$ is less than or equal to the spine structure of $&mu;$ in refinement order. We prove one direction of this conjecture, by showing that if the spine structure of $&tau;$ is less than or equal to the spine structure of $&mu;$, then $A$<sub>$n$</sub>($&tau;$) ≤ $A$<sub>$n$</sub>($&mu;$) for all $n$. We disprove the opposite direction by giving a counterexample, and hence disprove the conjecture.


Volume: Vol. 17 no.2
Section: Combinatorics
Published on: December 15, 2015
Submitted on: June 9, 2013
Keywords: permutations,permutation pattern,popularity,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 439 times.
This article's PDF has been downloaded 638 times.