Improved bounds on the maximum diversity of intersecting families

DOI10.1016/J.EJC.2023.103885MaRDI QIDQ6201878zbMATH OpenFDO

Authors Peter Frankl, Jian Wang

Publication date 26 March 2024

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

inequalitiesmaximum degreediversityfinite setsfamilies of subsets

Mathematics Subject Classification ID

Extremal set theory (05D05)

Abstract: A family $$ is called an intersecting family if $Fcap{F}^{\prime }eqemptyset$ for all $F,F^{\prime }inmathcalF$. If $capmathcalFeqemptyset$ then $mathcalF$ is called a star. The diversity of an intersecting family $mathcalF$ is defined as the minimum number of $k$-sets in $mathcalF$, whose deletion results in a star. In the present paper, we prove that for $n>36k$ any intersecting family $$ has diversity at most $$, which improves the previous best bound $n>72k$ due to the first author. This result is derived from some strong bounds concerning the maximum degree of large intersecting families. Some related results are established as well.

Recommendations

• On diversity of certain \(t\)-intersecting families
• Diversity of uniform intersecting families
• Diversity
• A generalization of diversity for intersecting families
• Maximum degree and diversity in intersecting hypergraphs

Cites work

• scientific article; zbMATH DE number 4029608 (Why is no real title available?)
• scientific article; zbMATH DE number 3489128 (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?)
• A generalization of a theorem of Kruskal
• A product version of the Hilton-Milner theorem
• A simple proof of the Hilton-Milner theorem
• Antichains of fixed diameter
• Diversity
• Diversity of uniform intersecting families
• Erdős-Ko-Rado theorem with conditions on the maximal degree
• Exact solution of some Turán-type problems
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Intersecting and cross-intersecting families of labeled sets
• Intersecting families with sunflower shadows
• Intersection theorems for systems of finite sets
• Intersections and distinct intersections in cross-intersecting families
• Maximum degree and diversity in intersecting hypergraphs
• New injective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems
• Non-trivial intersecting families
• On finite set-systems whose every intersection is a kernel of a star
• On intersecting families of finite sets
• Regular bipartite graphs and intersecting families
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Some best possible inequalities concerning cross-intersecting families
• THE ERDÖS–KO–RADO THEOREM WITH VALENCY CONDITIONS
• The complete nontrivial-intersection theorem for systems of finite sets
• The exact bound in the Erdős-Ko-Rado theorem
• The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton-Milner family
• The unbalance of set systems
• Two extremal problems on intersecting families

Cited in

(3)

• A generalization of diversity for intersecting families
• Stabilities for non-uniform \(t\)-intersecting families
• Diversity and intersecting theorems for weak compositions

This page was built for publication: Improved bounds on the maximum diversity of intersecting families

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