TY - JOUR
T1 - Towards extending the Ahlswede–Khachatrian theorem to cross t-intersecting families
AU - Lee, Sang June
AU - Siggers, Mark
AU - Tokushige, Norihide
N1 - Publisher Copyright:
© 2016 Elsevier B.V.
PY - 2017/1/10
Y1 - 2017/1/10
N2 - Ahlswede and Khachatrian's diametric theorem is a weighted version of their complete intersection theorem, which is itself a well known extension of the t-intersecting Erdős–Ko–Rado theorem. The complete intersection theorem says that the maximum size of a family of subsets of [n]={1,…,n}, every pair of which intersects in at least t elements, is the size of certain trivially intersecting families proposed by Frankl. We address a cross intersecting version of their diametric theorem. Two families A and B of subsets of [n] are cross t-intersecting if for every A∈A and B∈B, A and B intersect in at least t elements. The p-weight of a k element subset A of [n] is pk(1−p)n−k, and the weight of a family A is the sum of the weights of its sets. The weight of a pair of families is the product of the weights of the families. The maximum p-weight of a t-intersecting family depends on the value of p. Ahlswede and Khachatrian showed that for p in the range [rt+2r−1,r+1t+2r+1], the maximum p-weight of a t-intersecting family is that of the family Frt consisting of all subsets of [n] containing at least t+r elements of the set [t+2r]. In a previous paper we showed a cross t-intersecting version of this for large t in the case that r=0. In this paper, we do the same in the case that r=1. We show that for p in the range [1t+1,2t+3] the maximum p-weight of a cross t-intersecting pair of families, for t≥200, is achieved when both families are F1t. Further, we show that except at the endpoints of this range, this is, up to isomorphism, the only pair of t-intersecting families achieving this weight.
AB - Ahlswede and Khachatrian's diametric theorem is a weighted version of their complete intersection theorem, which is itself a well known extension of the t-intersecting Erdős–Ko–Rado theorem. The complete intersection theorem says that the maximum size of a family of subsets of [n]={1,…,n}, every pair of which intersects in at least t elements, is the size of certain trivially intersecting families proposed by Frankl. We address a cross intersecting version of their diametric theorem. Two families A and B of subsets of [n] are cross t-intersecting if for every A∈A and B∈B, A and B intersect in at least t elements. The p-weight of a k element subset A of [n] is pk(1−p)n−k, and the weight of a family A is the sum of the weights of its sets. The weight of a pair of families is the product of the weights of the families. The maximum p-weight of a t-intersecting family depends on the value of p. Ahlswede and Khachatrian showed that for p in the range [rt+2r−1,r+1t+2r+1], the maximum p-weight of a t-intersecting family is that of the family Frt consisting of all subsets of [n] containing at least t+r elements of the set [t+2r]. In a previous paper we showed a cross t-intersecting version of this for large t in the case that r=0. In this paper, we do the same in the case that r=1. We show that for p in the range [1t+1,2t+3] the maximum p-weight of a cross t-intersecting pair of families, for t≥200, is achieved when both families are F1t. Further, we show that except at the endpoints of this range, this is, up to isomorphism, the only pair of t-intersecting families achieving this weight.
KW - Ahlswede–Khachatrian theorem
KW - Cross intersecting families
KW - Erdős–Ko–Rado theorem
KW - Random walks
KW - Shifting
UR - http://www.scopus.com/inward/record.url?scp=84962159563&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2016.02.015
DO - 10.1016/j.dam.2016.02.015
M3 - Article
AN - SCOPUS:84962159563
SN - 0166-218X
VL - 216
SP - 627
EP - 645
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
ER -