Aisbett, Natalie - A relation on 132-avoiding permutation patterns

dmtcs:2141 - Discrete Mathematics & Theoretical Computer Science, December 15, 2015, Vol. 17 no.2
A relation on 132-avoiding permutation patterns

Authors: Aisbett, Natalie

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.


Source : oai:HAL:hal-01349056v1
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]


Share

Browsing statistics

This page has been seen 26 times.
This article's PDF has been downloaded 61 times.