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

DOI10.1016/J.DISC.2021.112327zbMATH Open1460.05186arXiv2006.12602OpenAlexW3128131754WikidataQ113877050 ScholiaQ113877050MaRDI QIDQ2659239FDOQ2659239

Authors: H. W. Willie Wong, Peter Frankl 

Publication date: 25 March 2021

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

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.

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

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

zbMATH Keywords

inequalitiesunioncontainmentintersectionfinite sets

Mathematics Subject Classification ID

Extremal set theory (05D05)

Cites Work

• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Title not available (Why is that?)
• The maximum sum and the maximum product of sizes of cross-intersecting families
• On cross-intersecting families of sets
• THE ERDÖS–KO–RADO THEOREM WITH VALENCY CONDITIONS
• A Combinatorial Theorem on Systems of Sets
• Generalizations of theorems of Katona and Milner

Cited In (6)

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

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)