Discrete Mathematics & Theoretical Computer Science |

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.

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]

This page has been seen 145 times.

This article's PDF has been downloaded 311 times.