Elements represented as intersections of sets

Abstract

For a natural number $n$ let $[n]=\{1,\dots ,n\}$. We say that a family $\mathcal{S}\subseteq 2^{[n]}$ is \emph{representing} if every singleton set of $[n]$ is an intersection of some sets from $\mathcal{S}$. We show that the smallest possible cardinality of a representing set for $[n]$ is the discrete inverse $s(n)$ of the Sperner's function $n\mapsto \left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$, which by Sperner's Theorem is the maximum number of elements in an antichain in $2^{[n]}$ when viewed as subset (or boolean) lattice. Specifically, $s(n)$ is then the smallest positive integer such that $2^{[n]}$ contains an $n$-element antichain. Some generalization, further applications and asymptotics in terms of the second real branch of the Lambert $W$ function are presented.

16 pages, 6 figures