https://hal.inria.fr/hal-01349056Aisbett, NatalieNatalieAisbettSchool of Mathematics and statistics [Sydney] - The University of Sydney A relation on 132-avoiding permutation patternsHAL CCSD2015permutationspermutation patternpopularity[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]Episciences Iam, Coordination2016-07-26 17:57:332020-02-19 13:10:042016-07-26 17:58:34enJournal articleshttps://hal.inria.fr/hal-01349056/document10.46298/dmtcs.2141application/pdf1A 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.