Article ID Journal Published Year Pages File Type
4655337 Journal of Combinatorial Theory, Series A 2014 30 Pages PDF
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 familyB={σ∈Sn:σ(1)=1,σ(2)=2,B=#{fixed points of σ≥5}≠1}B=∪{(13)(24),(14)(23),(1324),(1423)} 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].
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,