Towards extending the Ahlswede-Khachatrian theorem to cross -intersecting families

详细信息    查看全文

• 作者：Sang June Lee^a ; ^{sanglee242@duksung.ac.kr} ; Mark Siggers^b ; ^{mhsiggers@knu.ac.kr} ; Norihide Tokushige^c ; ^{hide@edu.u-ryukyu.ac.jp}
• 关键词：Cross intersecting families ; Erdős&ndash ; Ko&ndash ; Rado theorem ; Ahlswede&ndash ; Khachatrian theorem ; Shifting ; Random walks
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：10 January 2017
• 年：2017
• 卷：216
• 期：part_P3
• 页码：627-645
• 全文大小：514 K
• 卷排序：216

文摘

Ahlswede and Khachatrian’s diametric theorem is a weighted version of their complete intersection theorem, which is itself a well known extension of the tt-intersecting Erdős–Ko–Rado theorem. The complete intersection theorem says that the maximum size of a family of subsets of [n]={1,…,n}[n]={1,…,n}, every pair of which intersects in at least tt elements, is the size of certain trivially intersecting families proposed by Frankl. We address a cross intersecting version of their diametric theorem.Two families AA and BB of subsets of [n][n] are cross  tt-intersecting   if for every A∈AA∈A and B∈BB∈B, AA and BB intersect in at least tt elements. The pp-weight of a kk element subset AA of [n][n] is pk(1−p)n−kpk(1−p)n−k, and the weight of a family AA 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 pp-weight of a tt-intersecting family depends on the value of pp. Ahlswede and Khachatrian showed that for pp in the range [rt+2r−1,r+1t+2r+1], the maximum pp-weight of a tt-intersecting family is that of the family Frt consisting of all subsets of [n][n] containing at least t+rt+r elements of the set [t+2r][t+2r].In a previous paper we showed a cross tt-intersecting version of this for large tt in the case that r=0r=0. In this paper, we do the same in the case that r=1r=1. We show that for pp in the range [1t+1,2t+3] the maximum pp-weight of a cross tt-intersecting pair of families, for t≥200t≥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 tt-intersecting families achieving this weight.