Uniform s-Cross-Intersecting Families

DOI10.1017/S0963548317000062MaRDI QIDQ5366959zbMATH OpenOpenAlexFDO

Authors Peter Frankl, Andrey B. Kupavskii

Publication date 10 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Extremal set theory (05D05)

Abstract: In this paper we study a question related to the classical ErdH{o}s-Ko-Rado theorem, which states that any family of $k$-element subsets of the set $[n]=1,ldots,n$ in which any two sets intersect, has cardinality at most $n-1choosek-1$. We say that two non-empty families are $mathcalA,mathcalBsubset[n]choosek$ are {it $s$-cross-intersecting}, if for any $AinmathcalA,BinmathcalB$ we have $|AcapB|ges$. In this paper we determine the maximum of $|mathcalA|+|mathcalB|$ for all $n$. This generalizes a result of Hilton and Milner, who determined the maximum of $|mathcalA|+|mathcalB|$ for nonempty $1$-cross-intersecting families.

Recommendations

• Uniformly cross intersecting families
• Intersecting k-uniform families containing a given family
• scientific article; zbMATH DE number 4198044
• Uniform Intersecting Families with Covering Number Restrictions
• On cross-intersecting families of sets
• Cross-intersecting families of finite sets
• On cross t-intersecting families of sets
• On cross-intersecting uniform sub-families of hereditary families
• Uniform intersecting families with large covering number
• Cross L-intersecting families on set systems

Cites work

• A size-sensitive inequality for cross-intersecting families
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Iterative methods in combinatorial optimization.
• Some best possible inequalities concerning cross-intersecting families
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS

Cited in

(13)

• A short proof of a cross-intersection theorem of Hilton
• Diversity of uniform intersecting families
• Coloring cross-intersecting families
• On the arithmetic mean of the size of cross-union families
• A generalization of Kneser graphs
• Cross-intersecting non-empty uniform subfamilies of hereditary families
• Non-trivial 3-wise intersecting uniform families
• Unifying the representation of symmetric crossing families and weakly partitive families
• On cross-intersecting families of independent sets in graphs
• r$r$‐Cross t$t$‐intersecting families via necessary intersection points
• A result for hemi-bundled cross-intersecting families
• On non-empty cross-intersecting families
• Non-uniform pairwise cross t-intersecting families

This page was built for publication: Uniform s-Cross-Intersecting Families

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