• Title of article

    Forbidding just one intersection, for permutations

  • Author/Authors

    Ellis، نويسنده , , David، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2014
  • Pages
    30
  • From page
    136
  • To page
    165
  • 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].
  • Keywords
    stability , Permutations , Intersections
  • Journal title
    Journal of Combinatorial Theory Series A
  • Serial Year
    2014
  • Journal title
    Journal of Combinatorial Theory Series A
  • Record number

    1532034