Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4655663 | Journal of Combinatorial Theory, Series A | 2012 | 25 Pages |
Abstract
A family of permutations A⊂Sn is said to be t-set-intersecting if for any two permutations σ,π∈A, there exists a t-set x whose image is the same under both permutations, i.e. σ(x)=π(x). We prove that if n is sufficiently large depending on t, the maximum-sized t-set-intersecting families of permutations in Sn are cosets of stabilizers of t-sets. The t=2 case of this was conjectured by János Körner. It can be seen as a variant of the Deza–Frankl conjecture, proved in Ellis, Friedgut and Pilpel (2011) [3], . Our proof uses similar techniques to those of Ellis, Friedgut and Pilpel (2011) [3], namely, eigenvalue methods, together with the representation theory of the symmetric group, but the combinatorial part of the proof is harder.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics