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

Sang June Lee, Mark Siggers, Norihide Tokushige

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)627-645
Number of pages19
JournalDiscrete Applied Mathematics
Volume216
DOIs
StatePublished - 10 Jan 2017

Keywords

  • Ahlswede–Khachatrian theorem
  • Cross intersecting families
  • Erdős–Ko–Rado theorem
  • Random walks
  • Shifting

Fingerprint

Dive into the research topics of 'Towards extending the Ahlswede–Khachatrian theorem to cross t-intersecting families'. Together they form a unique fingerprint.

Cite this