کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651266 1342529 2006 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An Erdős–Ko–Rado theorem for partial permutations
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
An Erdős–Ko–Rado theorem for partial permutations
چکیده انگلیسی

Let [n][n] denote the set of positive integers {1,2,…,n}{1,2,…,n}. An r-partial permutation   of [n][n] is a pair (A,f)(A,f) where A⊆[n]A⊆[n], |A|=r|A|=r and f:A→[n]f:A→[n] is an injective map. A set AA of r-partial permutations is intersecting   if for any (A,f)(A,f), (B,g)∈A(B,g)∈A, there exists x∈A∩Bx∈A∩B such that f(x)=g(x)f(x)=g(x). We prove that for any intersecting family AA of r  -partial permutations, we have |A|⩽n-1r-1((n-1)!/(n-r)!).It seems rather hard to characterize the case of equality. For 8⩽r⩽n-38⩽r⩽n-3, we show that equality holds if and only if there exist x0x0 and ε0ε0 such that AA consists of all (A,f)(A,f) for which x0∈Ax0∈A and f(x0)=ε0f(x0)=ε0.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 306, Issue 1, 28 January 2006, Pages 74–86
نویسندگان
, ,