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

preprint2015arXivOpen access

Abstract

Ahlswede and Khachatrian's diametric theorem is a weighted version of their complete intersection theorem, itself an extension of the tt-intersecting Erdős-Ko-Rado theorem. Their intersection theorem says that the maximum size of a family of subsets of [n]={1,…,n}[n] = \{1, \dots, 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 A\mathcal{A} and B\mathcal{B} of subsets of [n][n] are {\em cross tt-intersecting} if for every A∈AA \in \mathcal{A} and B∈BB \in \mathcal{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−kp^{k}(1-p)^{n-k}, and the weight of a family A\mathcal{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 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][\frac{r}{t + 2r - 1}, \frac{r+1}{t + 2r + 1}], the maximum pp-weight of a tt-intersecting family is that of the family Frt\mathcal{F}^t_r 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][\frac{1}{t + 1}, \frac{2}{t + 3}] the maximum pp-weight of a cross tt-intersecting pair of families, for t≥200t \geq 200, is achieved when both families are F1t\mathcal{F}^t_1. 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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.