Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4655793 | Journal of Combinatorial Theory, Series A | 2011 | 20 Pages |
A family of permutations A⊂SnA⊂Sn is said to be t-intersecting if any two permutations in AA agree on at least t points, i.e. for any σ,π∈Aσ,π∈A, |{i∈[n]:σ(i)=π(i)}|⩾t|{i∈[n]:σ(i)=π(i)}|⩾t. It was proved by Friedgut, Pilpel and the author in [6] that for n sufficiently large depending on t, a t -intersecting family A⊂SnA⊂Sn has size at most (n−t)!(n−t)!, with equality only if AA is a coset of the stabilizer of t points (or ‘t-coset’ for short), proving a conjecture of Deza and Frankl. Here, we first obtain a rough stability result for t -intersecting families of permutations, namely that for any t∈Nt∈N and any positive constant c , if A⊂SnA⊂Sn is a t -intersecting family of permutations of size at least c(n−t)!c(n−t)!, then there exists a t -coset containing all but at most an O(1/n)O(1/n)-fraction of AA. We use this to prove an exact stability result: for n sufficiently large depending on t , if A⊂SnA⊂Sn is a t-intersecting family which is not contained within a t -coset, then AA is at most as large as the familyD={σ∈Sn:σ(i)=i∀i⩽t,σ(j)=jfor somej>t+1}∪{(1t+1),(2t+1),…,(tt+1)}, which has size (1−1/e+o(1))(n−t)!(1−1/e+o(1))(n−t)!. Moreover, if AA is the same size as DD then it must be a ‘double translate’ of DD, meaning that there exist π,τ∈Snπ,τ∈Sn such that A=πDτA=πDτ. The t=1t=1 case of this was a conjecture of Cameron and Ku and was proved by the author in [5]. We build on our methods in [5], but the representation theory of SnSn and the combinatorial arguments are more involved. We also obtain an analogous result for t -intersecting families in the alternating group AnAn.