Families of permutations with a forbidden intersection

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

• David Ellis (Queen Mary UL)
• Thursday 22 November 2018, 14:30-15:30
• MR12.

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.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Combinatorics Seminar
• DPMMS Lists
• DPMMS Pure Maths Seminar
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR12
• School of Physical Sciences
• bld31

Note that ex-directory lists are not shown.