A short proof of an Erdős–Ko–Rado theorem for compositions

Abstract

If a1, . . . , ak and n are positive integers such that n = a1 + • • • + ak, then the tuple (a1, . . . , ak) is a composition of n of length k. We say that (a1, . . . , ak) strongly t-intersects (b1, . . . , bk)if there are at least t distinct indices i such that ai = bi. A set A of compositions is strongly t-intersecting if every two members of A strongly t-intersect. Let Cn,k be the set of all compositions of n of length k. Ku and Wong (2013) showed that for every two positive integers k and t with k ≥ t + 2, there exists an integer n0(k, t) such that for n ≥ n0(k, t), the size of any strongly t-intersecting subset A of Cn,k is at most n−t−1 n−k , and the bound is attained if and only if A = {(a1, . . . , ak) ∈ Cn,k : ai1 = • • • = ait = 1} for some distinct i1, . . . , it in {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). We also show that the condition n ≥ n0(k, t) cannot be replaced by k ≥ k0(t) or n ≥ n0(t) (that is, the dependence of n on k is inevitable), and we suggest a Frankl-type conjecture about the extremal structures for any n, k, and t.