Article ID Journal Published Year Pages File Type
4655420 Journal of Combinatorial Theory, Series A 2013 13 Pages PDF
Abstract
Let B(n) denote the collection of all set partitions of [n]. Suppose A⊆B(n) is a non-trivial t-intersecting family of set partitions i.e. any two members of A have at least t blocks in common, but there is no fixed set of t blocks of size one which belong to all of them. It is proved that for sufficiently large n depending on t,|A|⩽Bn−t−B˜n−t−B˜n−t−1+t where Bn is the n-th Bell number and B˜n is the number of set partitions of [n] without blocks of size one. Moreover, equality holds if and only if A is equivalent to{P∈B(n):{1},{2},…,{t},{i}∈Pfor somei∉{1,2,…,t,n}}∪{Q(i,n):1⩽i⩽t} where Q(i,n)={{i,n}}∪{{j}:j∈[n]∖{i,n}}. This is an analogue of the Hilton-Milner theorem for set partitions.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,