Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4655337 | Journal of Combinatorial Theory, Series A | 2014 | 30 Pages |
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].
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
David Ellis,