Title of article :
An analogue of the Hilton–Milner theorem for set partitions
Author/Authors :
Ku، نويسنده , , Cheng Yeaw and Wong، نويسنده , , Kok Bin، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2013
Pages :
13
From page :
1508
To page :
1520
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 | ⩽ B n − t − B ˜ n − t − B ˜ n − t − 1 + t where B n 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 } ∈ P for some i ∉ { 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.
Keywords :
Intersecting family , Hilton–Milner , Erd?s–Ko–Rado , set partitions
Journal title :
Journal of Combinatorial Theory Series A
Serial Year :
2013
Journal title :
Journal of Combinatorial Theory Series A
Record number :
1531926
Link To Document :
بازگشت