کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4655663 1343397 2012 25 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Setwise intersecting families of permutations
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Setwise intersecting families of permutations
چکیده انگلیسی

A family of permutations A⊂Sn is said to be t-set-intersecting if for any two permutations σ,π∈A, there exists a t-set x whose image is the same under both permutations, i.e. σ(x)=π(x). We prove that if n is sufficiently large depending on t, the maximum-sized t-set-intersecting families of permutations in Sn are cosets of stabilizers of t-sets. The t=2 case of this was conjectured by János Körner. It can be seen as a variant of the Deza–Frankl conjecture, proved in Ellis, Friedgut and Pilpel (2011) [3], . Our proof uses similar techniques to those of Ellis, Friedgut and Pilpel (2011) [3], namely, eigenvalue methods, together with the representation theory of the symmetric group, but the combinatorial part of the proof is harder.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series A - Volume 119, Issue 4, May 2012, Pages 825-849