A cross‐intersection theorem for subsets of a set

DOI10.1112/BLMS/BDU110MaRDI QIDQ5245489zbMATH OpenOpenAlexFDO

Authors Peter Borg

Publication date 8 April 2015

Published in Bulletin of the London Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

cross-intersectingErdős-Ko-Rado theoremextremal familiesfamilies of subsets

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Extremal set theory (05D05)

Abstract: Two families $mathcalA$ and $mathcalB$ of sets are said to be cross-intersecting if each member of $mathcalA$ intersects each member of $mathcalB$. For any two integers $n$ and $k$ with $0leqkleqn$, let $[n]chooseleqk$ denote the family of all subsets of $1,dots,n$ of size at most $k$. We show that if $mathcalAsubseteq[m]chooseleqr$, $mathcalBsubseteq[n]chooseleqs$, and $mathcalA$ and $mathcalB$ are cross-intersecting, then [|mathcal{A}||mathcal{B}| leq sum_{i=0}^r {m-1 choose i-1} sum_{j=0}^s {n-1 choose j-1},] and equality holds if $mathcalA=Ain[m]chooseleqrcolon1inA$ and $mathcalB=Bin[n]chooseleqscolon1inB$. Also, we generalise this to any number of such cross-intersecting families.

Recommendations

• Cross-intersecting sub-families of hereditary families
• The maximum sum of sizes of cross-intersecting families of subsets of a set
• EKR sets for large \(n\) and \(r\)
• Extremal t -intersecting sub-families of hereditary families
• A simple proof of the Hilton-Milner theorem
• A new short proof of a theorem of Ahlswede and Khachatrian
• On cross-intersecting uniform sub-families of hereditary families
• A short proof of a cross-intersection theorem of Hilton
• A size-sensitive inequality for cross-intersecting families
• A Katona-type proof of an Erdős-Ko-Rado-type theorem

Cites work

• A cross-intersection theorem for vector spaces based on semidefinite programming
• A generalization of the Katona theorem for cross t-intersecting families
• A new generalization of the Erdős-Ko-Rado theorem
• A short proof of a cross-intersection theorem of Hilton
• A simple proof of the Erdős-Chao Ko-Rado theorem
• An analogue of the Erdoes-Ko-Rado theorem for the Hamming schemes H(n,q)
• An Erdős-Ko-Rado theorem for cross t-intersecting families
• An Intersection Theorem for a Collection of Families of Subsets of a Finite Set
• Compression and Erdős-Ko-Rado graphs
• Cross t-intersecting integer sequences from weighted Erdős-Ko-Rado
• Cross-intersecting families and primitivity of symmetric systems
• Cross-intersecting families of labeled sets
• Cross-intersecting sub-families of hereditary families
• Erdös–Ko–Rado Theorem—22 Years Later
• Erdős-Ko-Rado from Kruskal-Katona
• Extremal t -intersecting sub-families of hereditary families
• Graphs with the Erdős-Ko-Rado property
• scientific article; zbMATH DE number 4029608 (Why is no real title available?)
• scientific article; zbMATH DE number 3621717 (Why is no real title available?)
• scientific article; zbMATH DE number 3189757 (Why is no real title available?)
• Intersecting and cross-intersecting families of labeled sets
• INTERSECTING FAMILIES OF SEPARATED SETS
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Intersection theorems for systems of finite sets
• On cross-intersecting families of sets
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• The complete intersection theorem for systems of finite sets
• The exact bound in the Erdős-Ko-Rado theorem
• The exact bound in the Erdős-Ko-Rado theorem for cross-intersecting families
• The maximum sum and the maximum product of sizes of cross-intersecting families

Cited in

(15)

• A short proof of a cross-intersection theorem of Hilton
• Beyond the Erdős-Ko-Rado theorem
• Intersecting families, cross-intersecting families, and a proof of a conjecture of Feghali, Johnson and Thomas
• The maximum sum of sizes of cross-intersecting families of subsets of a set
• The maximum product of sizes of cross-intersecting families
• Set Systems with L-Intersections and k-Wise L-Intersecting Families
• The maximum product of weights of cross-intersecting families
• A sharp bound for the product of weights of cross-intersecting families
• Intersection properties of subsets of integers
• An intersection theorem for weighted sets
• A refined result on cross-intersecting families
• r$r$‐Cross t$t$‐intersecting families via necessary intersection points
• A proof of Frankl's conjecture on cross-union families
• A note on the maximum product-size of non-trivial cross t-intersecting families
• A note on non-empty cross-intersecting families

This page was built for publication: A cross‐intersection theorem for subsets of a set

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