A Deza-Frankl type theorem for set partitions

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

来源：Electronic Journal of Combinatorics, 2015, 22(1): P1.84.

DOI：10.37236/4987

• t-intersecting family
• Erdos-Ko-Rado
• set partitions

A set partition of [n] is a collection of pairwise disjoint nonempty subsets (called blocks) of [n] whose union is [n]. Let B(n) denote the family of all set partitions of [n]. A family A subset of B(n) is said to be rn-intersecting if any two of its members have at least rn blocks in common. For any set partition P is an element of B(n), let tau (P) - {x : {x} is an element of P} denote the union of its singletons. Also, let mu(P) = [n] - tau(P) denote the set of elements that do not appear as a singleton in P. Let
F-2t = {P is an element of B(n) : vertical bar mu(P)vertical bar <= t};
F2t+1(i0) = {P is an element of B(n) : vertical bar mu(P) boolean AND ([n] \ {i0}vertical bar <= t}.
In this paper, we show that for r >= 3, there exists a constant n(0) = n(0) (r) depending on r such that for all n >= n(0), if A subset of B(n) is (n - r)-intersecting, then
vertical bar A vertical bar <= { vertical bar F-2t vertical bar , if r = 2t; vertical bar F2t+1 (1)vertical bar if r = 2t + 1.
Moreover, equality holds if and only if
A = {F-2t if r = 2t;
F2t+1(i(0)), if r = 2t + 1,
for some i(0) is an element of [n].

• 出版日期2015-3-30