I have to mention Ben Green again. Yesterday he gave a lovely colloquium talk on a problem I had cracked my head against some years ago without much success.
As usual with derangements, the story begins with a classical result: the probability that a random permutation of n points has no fixed points is very close to 1/e.
How many permutations fix no subset of size k of the domain? In other words, what is the proportion of derangements in the action of the symmetric group Sn on k-sets? For fixed k, this tends to a limit p(k). (This is an easy consequence of Goncharev’s theorem that the joint distribution of the number of cycles of lengths 1, 2, …, k tends to independent Poisson random variables with parameters 1, 1/2, …, 1/k.
But what is the function p(k)? This is the question that Ben and his collaborators Sean Eberhard and Kevin Ford have tackled. It is bounded above and below by constants times k−0.086…(log k)−3/2. The mysterious constant is 1−(1+log log 2)/log 2.
There is a context for this. Łuczak and Pyber showed that the only primitive actions of the symmetric groups for which the proportion of derangements does not tend to zero are those on k-sets for fixed k; their bounds were improved by Diaconis, Fulman and Guralnick, who proved much else besides, including the limiting distribution in the above case.
Ben went on to describe some fascinating connections with the number of divisors of an integer; but I have no time to talk about this now.
Hi Peter,
Dimitris Koukoulopoulos, Kevin Ford, and I also have some more recent work in this vein that you might be interested in. We count permutations fixing several disjoint sets of given sizes, and we deduce an estimate for the number of permutations contained in some transitive subgroup. See arxiv.org/abs/1605.01068.
Thanks — I will take a look!