科研之友
微信
新浪微博
Facebook
分享链接
摘要
A family of permutations A subset of S-n is said to be intersecting if any two permutations in A agree at some point, that is, for any sigma, pi is an element of A, there is some i such that sigma(i) = pi(i). Deza and Frankl showed that if A subset of S-n is intersecting, then vertical bar A vertical bar <= (n -1)!. Cameron and Ku showed that if equality holds, then A = {sigma is an element of S-n : sigma(i) = j} for some i and j. They conjectured a 'stability' version of this result, namely that there exists a constant c < 1 such that if A subset of S-n is an intersecting family of size at least c(n -1)!, then there exist i and j such that every permutation in A maps i to j (we call such a family 'centred'). They also made a stronger 'Hilton-Milner' type conjecture, namely, that, for n >= 6, if A subset of S-n is a non-centred intersecting family, then A cannot be larger than the family C = {sigma is an element of S-n : sigma(1) = 1, sigma(i) = i for some i > 2} boolean OR {(12)}, which has size (1 - 1/e + o(1))(n -1)!. We prove the stability conjecture, and also the Hilton-Milner type conjecture for n sufficiently large. Our proof makes use of the classical representation theory of S-n. One of our key tools will be an extremal result on cross-intersecting families of permutations, namely that, for n >= 4, if A, B subset of S-n are cross-intersecting, then vertical bar A vertical bar vertical bar B vertical bar <= ((n -1)!)(2). This was a conjecture of Leader [Lecture at the 20th British Combinatorial Conference, 2005]; it was proved for n sufficiently large by Friedgut, Pilpel and the author.
- 出版日期2012-2
