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

DOI10.1016/J.DAM.2016.02.015zbMATH Open1358.05298OpenAlexW2963240870MaRDI QIDQ516792FDOQ516792

Authors: Sang June Lee, Norihide Tokushige, Mark Siggers 

Publication date: 15 March 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: Ahlswede and Khachatrian's diametric theorem is a weighted version of their complete intersection theorem, itself an extension of the $t$-intersecting ErdH{o}s-Ko-Rado theorem. Their intersection theorem says that the maximum size of a family of subsets of $[n]=1,dots,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 $mathcalA$ and $mathcalB$ of subsets of $[n]$ are {em cross $t$-intersecting} if for every $AinmathcalA$ and $BinmathcalB$, $A$ and $B$ intersect in at least $t$ elements. The $p$-weight of a $k$ element subset $A$ of $[n]$ is $p^k(1-p{)}^{n-k}$, and the weight of a family $mathcalA$ 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 $[fracrt+2r-1,fracr+1t+2r+1]$, the maximum $p$-weight of a $t$-intersecting family is that of the family $mathcal{F}_r^t$ 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 $[frac1t+1,frac2t+3]$ the maximum $p$-weight of a cross $t$-intersecting pair of families, for $tgeq200$, is achieved when both families are $mathcal{F}_1^t$. 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.

Full work available at URL: https://arxiv.org/abs/1509.02249

Recommendations

• A generalization of the Katona theorem for cross t-intersecting families
• An Erdős-Ko-Rado theorem for cross \(t\)-intersecting families
• On cross \(t\)-intersecting families of sets
• Intersecting families, cross-intersecting families, and a proof of a conjecture of Feghali, Johnson and Thomas
• A refined result on cross-intersecting families
• AK-type stability theorems on cross \(t\)-intersecting families
• On \(r\)-cross \(t\)-intersecting families for weak compositions
• The intersection structure of \(t\)-intersecting families
• On \(r\)-cross intersecting families of sets
• The exact bound in the Erdős-Ko-Rado theorem for cross-intersecting families

zbMATH Keywords

random walksshiftingAhlswede-Khachatrian theoremcross intersecting familiesErdős-Ko-Rado theorem

Mathematics Subject Classification ID

Extremal set theory (05D05)

Cites Work

• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• The complete intersection theorem for systems of finite sets
• The diametric theorem in Hamming spaces---optimal anticodes
• Title not available (Why is that?)
• The exact bound in the Erdős-Ko-Rado theorem
• Beyond the Erdős-Ko-Rado theorem
• An Erdős-Ko-Rado theorem for cross \(t\)-intersecting families
• Cross-intersecting families of vectors
• A pushing-pulling method: New proofs of intersection theorems

Cited In (7)

• More complete intersection theorems
• A note on large \(H\)-intersecting families
• AK-type stability theorems on cross \(t\)-intersecting families
• The weighted complete intersection theorem
• Cross \(t\)-intersecting integer sequences from weighted Erdős-Ko-Rado
• An Erdős-Ko-Rado theorem for cross \(t\)-intersecting families
• The maximum measure of non-trivial 3-wise intersecting families

This page was built for publication: Towards extending the Ahlswede-Khachatrian theorem to cross \(t\)-intersecting families

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q516792)