For n≥6r, every 2r-union family has at most C(n-2,r-1) sets of size >r; for n≥3.5r+1 it has at most C(n,r) sets of size ≥r, and both bounds are tight.
Improved bounds on the maximum diversity of intersecting families
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
A family $\mathcal{F}\subset \binom{[n]}{k}$ is called an intersecting family if $F\cap F'\neq \emptyset$ for all $F,F'\in \mathcal{F}$. If $\cap \mathcal{F}\neq \emptyset$ then $\mathcal{F}$ is called a star. The diversity of an intersecting family $\mathcal{F}$ is defined as the minimum number of $k$-sets in $\mathcal{F}$, whose deletion results in a star. In the present paper, we prove that for $n>36k$ any intersecting family $\mathcal{F}\subset \binom{[n]}{k}$ has diversity at most $\binom{n-3}{k-2}$, 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.
citation-role summary
background 1
citation-polarity summary
fields
math.CO 1years
2025 1verdicts
CONDITIONAL 1roles
background 1polarities
background 1representative citing papers
citing papers explorer
-
The overflow in the Katona Theorem
For n≥6r, every 2r-union family has at most C(n-2,r-1) sets of size >r; for n≥3.5r+1 it has at most C(n,r) sets of size ≥r, and both bounds are tight.