Article ID Journal Published Year Pages File Type
6423411 Discrete Mathematics 2013 11 Pages PDF
Abstract

A family A of sets is said to be intersecting if any two sets in A intersect (i.e. have at least one common element). A is said to be centred if there is an element common to all the sets in A; otherwise, A is said to be non-centred. For any r∈[n]:={1,…,n} and any integer k≥2, let Sn,r,k be the family {{(x1,y1),…,(xr,yr)}:x1,…,xr  are distinct elements of  [n],  y1,…,yr∈[k]} of k-signedr-sets on[n]. Let m:=max{0,2r−n}. We establish the following Hilton-Milner-type theorems, the second of which is proved using the first:(i) If A1 and A2 are non-empty cross-intersecting (i.e. any set in A1 intersects any set in A2) sub-families of Sn,r,k, then |A1|+|A2|≤nrkr−∑i=mrri(k−1)in−rr−ikr−i+1. (ii) If A is a non-centred intersecting sub-family of Sn,r,k, 2≤r≤n, then |A|≤{n−1r−1kr−1−∑i=mr−1ri(k−1)in−1−rr−1−ikr−1−i+1if  r

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,