For simplicity let $k$ be given fixed, and $n$ grows large. We are interested in a small set $M_n={g_1,...,g_m}$ of permutations in $S_n$, s.t for all $a\in S_n$, there is $g_i \in M_n$ with $ag_i$ having at least $k$ fixed points. The question is how large must $M_n$ be asymptotically depending on $k,n$. Another interesting question after we solve this one, is what happens when we force $M_n$ to be a subgroup of $S_n$.

If ones assums $n \geq (k+1)!$ there is the following upper bound which will be proved below after the lower bound)

Upper bound: $m=O((k+1)!nlog(n))$. Note for $k=1$ we also have the clear upper bound of $n$ taking what's genereated by a large circle, in fact if we want to be exact,$n/2+1$ for even $n$ and $\lceil(n/2)\rceil$ for odd $n$ bound if we care about constants by (for even $n$ for instance) having the $g_i$ fix $1,...,n/2-1$, and do what's generated by a large circle over the rest.

A (sad) lower bound of $m=\theta ((k+1)!)$ also follows in similiar spirit to the upper bound.

Here is also a lower bound of $n/2+1$ for $k=1$ and even $n$ (and in particular for the rest of the $k$. Odd $n$ is similiar):

We start with the complete bipartite graph with both sides having $n$ elements, each perfect matching corresponds to a matching which says who the left guy goes to in the right. Each $g_i$ kills a set of edges (i.e if in our permutation that edge exists, then multiplying by $g_i$ would lead to a fixed point for the left guy).

Thus what I claim that if you remove a union of any $n/2$ perfect matchings off the complete bipartite graph with $n$ vertices on each side, there is still a perfect matching standing. Note that it is possible to use $n/2+1$ matchings to cover so that we won't be able to find a perfect matching, so this is tight.

Now if we could only use $n/2$, then let's see the set that kills Halls condition. Say it is the set $A$ of size $a$. Then it sees a set $B$ of size at most $a-1$. Clearly $a \leq n/2$, otherwise $A$ sees everyone after removing the matchings. So we managed to cover the complete bipartite graph $AxB^c$ with $n/2$ matchings exhausting $A$. But $B^c$ has size at least $n-(n/2-1)=n/2+1$, and so $A$ sees all of $B^c$ after removing our matchings,a contradiction.

Here is an upper bound as promised and the other lower bound:

We want a set of $m$ permutations $g_{1},..,g_{m}$, s.t for all permutations $a$, there is $g_{i}$ with $ag_{i}$ having at least $k$ fixed points. Given a fixed $a$, if we pick a random $g$, what is the probability $ag$ has at least $k$ fixed points? Well since choosing $g$ at random is like $a^{-1}g$ at random, we're asking what is the probability a random $g$ has at least $k$ fixed points. It turns out easier to count the other thing, how many permutations have at most $k-1$ fixed points? Well in paricular how many have exactly $s$ fixed points? That's like fixing the $s$ fixed points, and then picking a derangment (no fixed point) on the rest; number of derangments on $n$ elements is (this one by inclusion exclusion) $n!(\sum_{0}^{n}\frac{(-1)^{i}}{i!})$, for large $n$ this is $\sim\frac{n!}{e}$. Thus the number of those with exactly $s$ fixed points is like $\binom{n}{s}\frac{(n-s)!}{e}$. So the number with at most $k-1$ fixed points is: $\sum_{s=0}^{k-1}\binom{n}{s}\frac{(n-s)!}{e}$. Thus our desired probability is $1-\frac{\sum_{s=0}^{k-1}\binom{n}{s}\frac{(n-s)!}{e}}{n!}=1-\frac{1}{e}(\sum_{s=0}^{k-1}\frac{\binom{n}{s}}{n\cdot(n-1)..(n-s+1)})=1-\frac{1}{e}(\sum_{s=0}^{k-1}\frac{\frac{n(n-1)..(n-s+1)}{s!}}{n(n-1)..(n-s+1)})=1-\frac{1}{e}(\sum_{s=0}^{k-1}\frac{1}{s!})=\frac{\sum_{s=k}^{\infty}\frac{1}{s!}}{e}$, this by Taylor approximation is at least (and up to a constant exactly) $\frac{1}{e(k+1)!}$. At last we can get to our problem. We need to union bound over $n!$ guys, so we want $(1-\frac{1}{e(k+1)!})^{m}<\frac{1}{n!}$. If $m=e(k+1)!$ we get roughly $\frac{1}{e}$, so $e(k+1)!(nlogn)$ is what we want and tight (to get the union bound) up to a const. So our answer is that $m=(k+1)!(nlog(n))$ suffices. To get a lower bound we try to flip our heads as usual. Assume we have just $m$, and we take a random element, the probability m catches us is $\frac{1}{e(k+1)!}$, so the probability at least one of them catches us by union bound is at most $\frac{m}{e(k+1)!}$, so $m\geq(k+1)!$ is a bound.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.