کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647105 | 1632409 | 2014 | 4 صفحه PDF | دانلود رایگان |
If a1,…,aka1,…,ak and nn are positive integers such that n=a1+⋯+akn=a1+⋯+ak, then the tuple (a1,…,ak)(a1,…,ak) is a composition of nn of length kk. We say that (a1,…,ak)(a1,…,ak)strongly tt-intersects (b1,…,bk)(b1,…,bk) if there are at least tt distinct indices ii such that ai=biai=bi. A set AA of compositions is strongly tt-intersecting if every two members of AA strongly tt-intersect. Let Cn,kCn,k be the set of all compositions of nn of length kk. Ku and Wong (2013) showed that for every two positive integers kk and tt with k≥t+2k≥t+2, there exists an integer n0(k,t)n0(k,t) such that for n≥n0(k,t)n≥n0(k,t), the size of any strongly tt-intersecting subset AA of Cn,kCn,k is at most n−t−1n−k, and the bound is attained if and only if A={(a1,…,ak)∈Cn,k:ai1=⋯=ait=1}A={(a1,…,ak)∈Cn,k:ai1=⋯=ait=1} for some distinct i1,…,iti1,…,it in {1,…,k}{1,…,k}. We provide a short proof of this analogue of the Erdős–Ko–Rado Theorem. It yields an improved value of n0(k,t)n0(k,t). We also show that the condition n≥n0(k,t)n≥n0(k,t) cannot be replaced by k≥k0(t)k≥k0(t) or n≥n0(t)n≥n0(t) (that is, the dependence of nn on kk is inevitable), and we suggest a Frankl-type conjecture about the extremal structures for any nn, kk, and tt.
Journal: Discrete Mathematics - Volume 333, 28 October 2014, Pages 62–65