An analogue of the Erdos-Ko-Rado theorem for weak compositions

Abstract

Let n0 be the set of non-negative integers, and let P(n,l) denote the set of all weak compositions of n with l parts, i.e., P(n,l)={(x 1,x2,⋯,x1)∈ℕ0 l:x1+x2+,⋯+x1=n}. For any element u=(u1,u2⋯,ul)∈P(n,l), denote its ith-coordinate by u(i), i.e., u(i)=ui. A family ⊆P(n,l) is said to be t-intersecting if |{i:u(i)=v(i)}|≥t for all u,v∈A. We prove that given any positive integers l,t with l≥t+2, there exists a constant n0(l,t) depending only on l and t, such that for all n≥n0(l,t), if ⊆P(n,l) is t-intersecting then |A|≤(n+l-t-1 l-t-1). Moreover, the equality holds if and only if A={u∈P(n,l):u(j)=0for allj∈T} for some t-set T of {1,2,⋯,l}. © 2013 Elsevier Ltd. All rights reserved.