A size-sensitive inequality for cross-intersecting families

DOI10.1016/J.EJC.2017.01.004MaRDI QIDQ518199zbMATH OpenOpenAlexFDO

Authors Peter Frankl, Andrey B. Kupavskii

Publication date 28 March 2017

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

Erdős-Ko-Rado theoremPyber's inequality

Mathematics Subject Classification ID

Combinatorial inequalities (05A20) Extremal set theory (05D05)

Abstract: Two families $mathcalA$ and $mathcalB$ of $k$-subsets of an $n$-set are called cross-intersecting if $AcapBeemptyset$ for all $AinmathcalA,BinmathcalB$. Strengthening the classical ErdH os-Ko-Rado theorem, Pyber proved that $|mathcalA||mathcalB|le{n-1choosek-1}^2$ holds for $nge2k$. In the present paper we sharpen this inequality. We prove that assuming $|mathcalB|gen-1choosek-1+n-ichoosek-i+1$ for some $3leilek+1$ the stronger inequality ${\displaystyle }$|mathcal A||mathcal B|le Bigl({n-1choose k-1}+{n-ichoose k-i+1}Bigr)Bigl({n-1choose k-1}-{n-ichoose k-1}Bigr)${\displaystyle }$ holds. These inequalities are best possible.

Recommendations

• A Short Proof for an Extension of the Erdős–Ko–Rado Theorem
• The exact bound in the Erdős-Ko-Rado theorem for cross-intersecting families
• Some best possible inequalities concerning cross-intersecting families
• Some Inequalities Concerning Cross-Intersecting Families
• A generalization of the Katona theorem for cross t-intersecting families

Cites work

• A generalization of a theorem of Kruskal
• A new generalization of the Erdős-Ko-Rado theorem
• Families of finite sets with minimum shadows
• scientific article; zbMATH DE number 5145337 (Why is no real title available?)
• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 3489128 (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
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Some best possible inequalities concerning cross-intersecting families
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• THE ERDÖS–KO–RADO THEOREM WITH VALENCY CONDITIONS
• The exact bound in the Erdős-Ko-Rado theorem for cross-intersecting families

Cited in

(21)

• A short proof of a cross-intersection theorem of Hilton
• Regular bipartite graphs and intersecting families
• Sharp results concerning disjoint cross-intersecting families
• On the arithmetic mean of the size of cross-union families
• A generalization of Kneser graphs
• Refinement of lower bounds of the chromatic number of a space with forbidden one-color triangles
• New inequalities for cross-intersecting families
• The maximum sum and the maximum product of sizes of cross-intersecting families
• On the maximum number of edges in hypergraphs with fixed matching and clique number
• Family sizes for complete multipartite graphs
• A cross‐intersection theorem for subsets of a set
• Uniform s-Cross-Intersecting Families
• A refined result on cross-intersecting families
• r$r$‐Cross t$t$‐intersecting families via necessary intersection points
• A product version of the Hilton-Milner theorem
• A note on the maximum product-size of non-trivial cross t-intersecting families
• Stabilities for non-uniform t-intersecting families
• On nontrivial cross-t-intersecting families
• Maximal intersecting families revisited
• A result for hemi-bundled cross-intersecting families
• Proof of Frankl's conjecture on cross-intersecting families

This page was built for publication: A size-sensitive inequality for cross-intersecting families

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