Author/Authors :
Ellis، نويسنده , , David، نويسنده ,
Abstract :
We prove that for n sufficiently large, if A is a family of permutations of { 1 , 2 , … , n } with no two permutations in A agreeing exactly once, then | A | ≤ ( n − 2 ) ! , with equality holding only if A is a coset of the stabilizer of 2 points. We also obtain a Hilton–Milner type result, namely that if A is such a family which is not contained within a coset of the stabilizer of 2 points, then it is no larger than the family B = { σ ∈ S n : σ ( 1 ) = 1 , σ ( 2 ) = 2 , B = # { fixed points of σ ≥ 5 } ≠ 1 } B = ∪ { ( 1 3 ) ( 2 4 ) , ( 1 4 ) ( 2 3 ) , ( 1 3 2 4 ) , ( 1 4 2 3 ) } We conjecture that for t ∈ N , and for n sufficiently large depending on t, if A is family of permutations of { 1 , 2 , … , n } with no two permutations in A agreeing exactly t − 1 times, then | A | ≤ ( n − t ) ! , with equality holding only if A is a coset of the stabilizer of t points. This can be seen as a permutation analogue of a conjecture of Erdős on families of k-element sets with a forbidden intersection, proved by Frankl and Füredi in [9].