Diversity of uniform intersecting families

DOI10.1016/J.EJC.2018.07.005MaRDI QIDQ1671747zbMATH OpenOpenAlexWikidataFDO

Authors Andrey B. Kupavskii

Publication date 7 September 2018

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

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

zbMATH Keywords

Frankl's conjecture

Mathematics Subject Classification ID

Extremal set theory (05D05)

Abstract: A family $mathcalFsubset{2}^{[n]}$ is called intersecting if any two of its sets intersect. Given an intersecting family, its diversity is the number of sets not passing through the most popular element of the ground set. Peter Frankl made the following conjecture: for $n>3k>0$ any intersecting family $mathcalFsubset[n]choosek$ has diversity at most $n-3choosek-2$. This is tight for the following "two out of three" family: $Fin[n]choosek:|Fcap[3]|ge2$. In this note, we prove this conjecture for $ngeck$, where $c$ is a constant independent of $n$ and $k$. In the last section, we discuss the case $2k<n<3k$ and show that one natural generalization of Frankl's conjecture does not hold.

Recommendations

• On diversity of certain \(t\)-intersecting families
• Uniformly cross intersecting families
• Uniform s-Cross-Intersecting Families
• Uniform Intersecting Families with Covering Number Restrictions
• Uniform intersecting families with large covering number
• On the measure of intersecting families, uniqueness and stability
• On the union of intersecting families
• Intersecting k-uniform families containing a given family
• scientific article; zbMATH DE number 4198044
• Non-trivial intersecting families

Cites work

• Analysis of Boolean Functions
• Antichains of fixed diameter
• Counting intersecting and pairs of cross-intersecting families
• Erdős-Ko-Rado theorem for \(\{0,\pm 1\}\)-vectors
• Erdős-Ko-Rado theorem with conditions on the maximal degree
• scientific article; zbMATH DE number 3189757 (Why is no real title available?)
• Intersecting Families are Essentially Contained in Juntas
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• On the hardness of approximating minimum vertex cover
• Regular bipartite graphs and intersecting families
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• The complete intersection theorem for systems of finite sets
• The junta method in extremal hypergraph theory and Chvátal's conjecture
• The unbalance of set systems
• Two extremal problems on intersecting families

Cited in

(30)

• Diverse homogeneous sets
• Two extremal problems on intersecting families
• Minimum degree and diversity in intersecting antichains
• Best possible bounds on the number of distinct differences in intersecting families
• Size and structure of large \((s,t)\)-union intersecting families
• Sharp bounds for the chromatic number of random Kneser graphs
• The Erdős matching conjecture and concentration inequalities
• A generalization of Kneser graphs
• On the independence numbers of some distance graphs with vertices in \(\{-1, 0, 1\}^n\)
• Degree versions of theorems on intersecting families via stability
• scientific article; zbMATH DE number 5122069 (Why is no real title available?)
• Optimizing diversity
• Maximum size intersecting families of bounded minimum positive co-degree
• On diversity of certain \(t\)-intersecting families
• Diversity
• Sharp threshold for the Erdős–Ko–Rado theorem
• Fixed-Parameter Algorithms for the Kneser and Schrijver Problems
• Uniform intersecting families with large covering number
• Improved bounds on the maximum diversity of intersecting families
• A generalization of diversity for intersecting families
• Diversity and intersecting theorems for weak compositions
• Size, diversity, minimum degree, sturdiness, dömdödöm
• Two results on set families: sturdiness and intersection
• Intersecting families with covering number 3
• On the C-diversity of intersecting k-graphs
• A result for hemi-bundled cross-intersecting families
• Best possible bounds on the double-diversity of intersecting hypergraphs
• On the maximum diversity of hypergraphs with fixed matching number
• A note on the maximum diversity of intersecting families in the symmetric group
• Maximum degree and diversity in intersecting hypergraphs

Describes a project that uses

Uses Software

• MathOverflow

This page was built for publication: Diversity of uniform intersecting families

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