Abstract

For a family $\mathcal{ℱ}\subset \left(\genfrac{}{}{0.0pt}{}{[n]}{k}\right)$ and two elements $x,y\in [n]$ define $\mathcal{ℱ}(\overline{x},\overline{y})=\{F\in \mathcal{ℱ}:x\notin F,y\notin F\}$. The double-diversity ${\gamma }_2(\mathcal{ℱ})$ is defined as the minimum of $|\mathcal{ℱ}(\overline{x},\overline{y})|$ over all pairs $x,y$. Let $\mathcal{ℒ}\subset \left(\genfrac{}{}{0.0pt}{}{[7]}{3}\right)$ consist of the seven lines of the Fano plane. For $n\ge 7$, $k\ge 3$ one defines the Fano $k$-graph ${\mathcal{ℱ}}_{\mathcal{ℒ}}$ as the collection of all $k$-subsets of $[n]$ that contain at least one line. It is proven that for $n\ge 13k^2$ the Fano $k$-graph is the essentially unique family maximizing the double diversity over all $k$-graphs without a pair of disjoint edges. Some similar, although less exact results are proven for triple and higher diversity as well.

Keywords

Mathematical Subject Classification

Milestones

Authors