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.


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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s