کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4655337 1632946 2014 30 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Forbidding just one intersection, for permutations
ترجمه فارسی عنوان
ممنوع دادن فقط یک تقاطع، برای جایگزینی
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
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].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series A - Volume 126, August 2014, Pages 136-165
نویسندگان
,