AN ANALOGUE OF THE HILTON-MILNER THEOREM FOR WEAK COMPOSITIONS

作者：Ku Cheng Yeaw^*; Wong Kok Bin

来源：Bulletin of the Korean Mathematical Society, 2015, 52(3): 1007-1025.

DOI：10.4134/BKMS.2015.52.3.1007

• cross-intersecting family
• Hilton-Milner
• Erdos-Ko-Rado
• weak compositions

Let N-0 be the set of non-negative integers, and let P(n,l) denote the set of all weak compositions of n with 1 parts, i.e., P(n,l) = {(x(1),x(2), ... ,x(l)) is an element of N-o(l) : x(1) + x(2) + ... + x(l) = n}. For any element u = (u(1), u(2), ... , u(l)) is an element of P(n,l), denote its ith-coordinate by u(i), i.e., u(i) = u(i). A family A subset of P(n,l) is said to be t-intersecting if Ili : u(i) = v(i)vertical bar 1 >= t for all u, v is an element of A. A family A subset of P(n,l) is said to be trivially t-intersecting if there is a t-set T of [l] = {1, 2, ..., l} and elements y(s) E N-0 (s is an element of T) such that A = {u is an element of P(n,l) : u(j) = y(j) for all j is an element of T}. We prove that given any positive integers l, t with 1 >= 2t + 3, there exists a constant n(0)(l, t) depending only on l and t, such that for all n >= n(0)(l, t), if A subset of P(n,l) is non-trivially t-intersecting, then
vertical bar A vertical bar <= ((n + l - t - 1)(l - t - 1)) - ((n - 1)(l - t - 1)) + t.
Moreover, equality holds if and only if there is a t-set T of [l] such that
A = boolean OR(s is an element of[l]\T) As boolean OR {q(i) : i is an element of T},
where As = {u is an element of P(n,l) : u(j) = 0 for all j is an element of T and u(s) = 0} and q(i) is an element of P(n,l) with qi(j) = 0 for all j is an element of [l] \ {i} and q(i)(i) = n.

• 出版日期2015-5