2013/10/30 by David Ellis, Ellis, David · 2 citations
Mathematics · Engineering · #Limits and Structures in Graph Theory #graph theory and CDMA systems #Finite Group Theory Research
paper · pdf · doi:10.48550/arxiv.1310.8108
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 \σ∈ Sn: σ(1)=1,σ(2)=2, #\\textrmfixed points ofσ≥ 5\ ≠ 1\ ∪ \(1 3)(2 4),(1 4)(2 3),(1 3 2 4),(1 4 2 3)\. We conjecture that for t ∈ ℕ, 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 [P. Frankl and Z. Füredi, Forbidding Just One Intersection, Journal of Combinatorial Theory, Series A, Volume 39 (1985), pp. 160-176].