Minimum blocking sets for families of partitions

Abstract

A $3$-partition of an $n$-element set $V$ is a triple of pairwise disjoint nonempty subsets $X,Y,Z$ such that $V=X\cup Y\cup Z$. We determine the minimum size ${\phi }_3(n)$ of a set $\mathcal{E}$ of triples such that for every 3-partition $X,Y,Z$ of the set $\{1,\dots ,n\}$, there is some $\{x,y,z\}\in \mathcal{E}$ with $x\in X$, $y\in Y$, and $z\in Z$. In particular, $${\phi }_3(n)=\lceil \frac{n(n-2)}{3}\rceil .$$ For $d>3$, one may define an analogous number ${\phi }_d(n)$. We determine the order of magnitude of ${\phi }_d(n)$, and prove the following upper and lower bounds, for $d>3$: $$\frac{2n^{d-1}}{d!}-o(n^{d-1})\le {\phi }_d(n)\le \frac{0.86}{(d-1)!}{n}^{d-1}+o(n^{d-1}).$$