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

چکیده انگلیسی
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
Journal: Discrete Mathematics - Volume 306, Issue 1, 28 January 2006, Pages 74–86
نویسندگان
C.Y. Ku, I. Leader,