7
$\begingroup$

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.

| cite | improve this question | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.