Green on derangements

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.

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in events, exposition and tagged , , . Bookmark the permalink.

2 Responses to Green on derangements

1. Sean Eberhard says:

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.