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 language | English |
|---|---|
| Pages (from-to) | 627-645 |
| Number of pages | 19 |
| Journal | Discrete Applied Mathematics |
| Volume | 216 |
| DOIs | |
| State | Published - 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
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver