Extremal Combinatorics on Permutations


We talked about extremal problems for set systems: collections of subsets of an n element sets, – Sperner’s theorem, the Erdos-Ko-Rado theorem, and quite a few more. (See here, here and here.) What happens when we consider collections of permutations rather than collection of sets? Not so much is known on extremal problems for families of permutations.

David Ellis, Ehud Friedgut, and Haran Pilpel have recently proved an old conjecture of Deza and Frankl regarding an analog for permutations of the Erdos-Ko-Rado Theorem. They showed that for every k if n is sufficiently large, any family of permutations on an n-element set such that every two permutations in the family agree in at least k places, contains at most (n-k)! permutations.

The proof uses spectral methods and representations of the symmetric group.

9 thoughts on “Extremal Combinatorics on Permutations

  1. Gil Kalai

    I wonder what other theorems of extremal combinatorics extend nicely to collections of permutations. Also, can we think of interesting extensions to other combinatorial structures.

  2. Janos Korner

    Dear Gil,

    Sperner’s problem (which in fact, was Schreier’s who asked Sperner this question) is a question about the asymptotic growth of the largest symmetric
    clique in the power graphs of a directed one-edge graph. In this optic we have generalized this problem to permutations in arXiv:0809.1522. This is the last in a series of papers on the “permutation capacity” of graphs and digraphs.
    Needless to say that the problems are generalizations of Shannon capaicity
    from finite graphs to infinite graphs and digraphs, so most of them are unsolved and we only have bounds some of which are non-trivial.


  3. Gil

    Thanks a lot, Janos. This is very interesting.

    Here is the link to the paper by Gerard Cohen, Emanuela Fachini, Janos Korner, and here are its opening lines.

    How many permutations of the first n natural numbers can we find such that any two of them place two consecutive natural numbers somewhere in the same position? This problem was introduced in [10] where the authors conjectured that the maximum number of such permutations is exactly the middle binomial coefficient {{n} \choose {n/2}}.

    I suppose what I had in mind are questions about collections of permutations which form an anti chain with respect to the strong (Bruhat) orderings or with respect to the weak order, or perhaps some other order. I am not sure if these questions are the same or if they were studied but probably there are various ways to extend Sperner’s theorem to permutations.

    1. Nathan Lindzey

      Hi Gil,
      It has been a few years since you’ve posed this (nice) question. Do you know of any progress that has been made in this direction (my searches came up dry)? Also, I’m assuming that you were thinking of S = {(i,i+1) | \forall i < n} for the generating set?

  4. Nathan Lindzey

    Hi Janos,
    I was referring to “collections of permutations which form an anti chain with respect to the strong (Bruhat) orderings”. In other words, given the Bruhat poset B_n of the symmetric group w.r.t the generating set of adjacent transpositions, what is the longest antichain of B_n? I’ve only read the abstract of your joint paper, but I believe this is different than the question you answer.


Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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