Extremal Combinatorics on Permutations

Posted on March 13, 2009 by Gil Kalai

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.

This entry was posted in Combinatorics and tagged , , , , , . Bookmark the permalink.

9 Responses to Extremal Combinatorics on Permutations

  1. James Lee says:
    March 13, 2009 at 6:07 am

    This is a very cool paper, with the possible exception of the line “we finally proceed to eat the pudding.” Is that British or Hebrew?

    Reply
  2. Gil Kalai says:
    March 13, 2009 at 9:15 am

    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.

    Reply
  3. Gil says:
    March 13, 2009 at 5:22 pm

    For example, is there an analog for Sperner’s theorem for permutation?

    Reply
  4. Shreevatsa says:
    March 13, 2009 at 6:20 pm

    @James Lee: That line is about “the proof of the pudding is in the eating”—a very English proverb, not Hebrew (AFAIK).

    Reply
  5. Janos Korner says:
    March 14, 2009 at 9:24 am

    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.

    janos

    Reply
  6. Gil says:
    March 14, 2009 at 12:59 pm

    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.

    Reply
  7. Nathan Lindzey says:
    May 28, 2013 at 9:38 pm

    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.

    Reply

Leave a comment