Analogues of Katona's and Milner's theorems for two families

DOI10.1016/J.DISC.2021.112327MaRDI QIDQ2659239zbMATH OpenOpenAlexWikidataFDO

Authors H. W. Willie Wong, Peter Frankl

Publication date 25 March 2021

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

inequalitiesunioncontainmentintersectionfinite sets

Mathematics Subject Classification ID

Extremal set theory (05D05)

Abstract: Let $n>s>0$ be integers, $X$ an $n$-element set and $mathscrA,mathscrBsubset{2}^X$ two families. If $|AcupB|les$ for all $AinmathscrA,BinmathscrB$, then $mathscrA$ and $mathscrB$ are called cross $s$-union. Assuming that neither $mathscrA$ nor $mathscrB$ is empty, we prove several best possible bounds. In particular, we show that $|mathscrA|+|mathscrB|le1+sumlimit{s}_{0leiles}nchoosei$. Supposing $nge2s$ and $mathscrA,mathscrB$ are antichains, we show that $|mathscrA|+|mathscrB|lenchoose1+nchooses-1$ unless $mathscrA=emptyset$ or $mathscrB=emptyset$. An analogous result for three families is established as well.

Recommendations

• A generalization of the Katona theorem for cross t-intersecting families
• Analogues of Milner's theorem for families without long chains and of vector spaces
• Some best possible inequalities concerning cross-intersecting families
• New inequalities for cross-intersecting families
• The exact bound in the Erdős-Ko-Rado theorem for cross-intersecting families

Cites work

• scientific article; zbMATH DE number 4029608 (Why is no real title available?)
• A Combinatorial Theorem on Systems of Sets
• Generalizations of theorems of Katona and Milner
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• On cross-intersecting families of sets
• THE ERDÖS–KO–RADO THEOREM WITH VALENCY CONDITIONS
• The maximum sum and the maximum product of sizes of cross-intersecting families

Cited in

(6)

• Families of ICIS with constant total Milnor number
• A stability result for the Katona theorem
• Analogues of Milner's theorem for families without long chains and of vector spaces
• Kruskal-Katona function and variants of cross-intersecting antichains
• Improved bounds for cross-Sperner systems
• r$r$‐Cross t$t$‐intersecting families via necessary intersection points

This page was built for publication: Analogues of Katona's and Milner's theorems for two families

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