University of Cambridge > Talks.cam > Combinatorics Seminar > Families of permutations with a forbidden intersection

Families of permutations with a forbidden intersection

Add to your list(s) Download to your calendar using vCal

  • UserDavid Ellis (Queen Mary UL)
  • ClockThursday 22 November 2018, 14:30-15:30
  • HouseMR12.

If you have a question about this talk, please contact Andrew Thomason.

A family of permutations is said to be ‘t-intersecting’ if any two permutations in the family agree on at least t points. It is said to be (t-1)-intersection-free if no two permutations in the family agree on exactly t-1 points. Deza and Frankl conjectured in 1977 that a t-intersecting family of permutations in S_n can be no larger than a coset of the stabiliser of t points, provided n is large enough depending on t; this was proved by the speaker and independently by Friedgut and Pilpel in 2008. We give a new proof of a stronger statement: namely, that a (t-1)-intersection-free family of permutations in S_n can be no larger than a coset of the stabiliser of t points, provided n is large enough. This can be seen as an analogue for permutations of seminal results of Frankl and Furedi on families of k-element sets. Our proof is partly algebraic and partly combinatorial; it is more ‘robust’ than the original proofs of the Deza-Frankl conjecture, using a combinatorial ‘quasirandomness’ argument to avoid many of the algebraic difficulties of the original proofs. Based on joint work with Noam Lifshitz (Bar Ilan University).

This talk is part of the Combinatorics Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2019 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity