Permutations fixing a k-set

Abstract

Let $i(n,k)$ be the proportion of permutations $\pi \in {\mathcal{S}}_n$ having an invariant set of size $k$. In this note we adapt arguments of the second author to prove that $i(n,k)\asymp k^{-\delta }(1+\log k{)}^{-3/2}$ uniformly for $1\le k\le n/2$, where $\delta =1-\frac{1+\log \log 2}{\log 2}$. As an application we show that the proportion of $\pi \in {\mathcal{S}}_n$ contained in a transitive subgroup not containing ${\mathcal{A}}_n$ is at least $n^{-\delta +o(1)}$ if $n$ is even.

17 pages. This is the final version accepted for publication incorporating the referees' suggestions. This version will differ from the published version

References in corpus (2)

• Four Random Permutations Conjugated by an Adversary Generate $S_n$ with High Probability
• Computing derangement probabilities of the symmetric group acting on k-sets

Cited by in corpus (9)

• Irreducible polynomials of bounded height
• Irreducibility of random polynomials: general measures
• Invariable generation of the symmetric group
• Permutations contained in transitive subgroups
• A model problem for multiplicative chaos in number theory
• Conjugacy classes of derangements in finite groups of Lie type
• Magic squares, the symmetric group and Möbius randomness
• Cycle type of random permutations: A toolkit
• Multiplicative arithmetic functions and the generalized Ewens measure