Article ID Journal Published Year Pages File Type
4647105 Discrete Mathematics 2014 4 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,