Minimal completely separating systems of \(k\)-sets (Q5929844): Difference between revisions

Let \(n\) and \(k\) be fixed positive integers. A collection \(C\) of \(k\)-subsets of \([n]=\{1,2, \ldots, n\}\) is a completely separating system if, for all distinct \(i,j \in [n]\), there is an \(S \in C\) for which \(i \in S\) and \(j \notin S\). Let \(R(n,k)\) denote the minimum size of such a \(C\). It is proved in this paper that, if \(n_k\) is a sequence with \(k \ll n_k \ll k^{1+\varepsilon}\) for every \(\varepsilon > 0\), then \(R(n_k,k) \sim \min \{t \mid n_k \leq {t \choose {\lceil kt/n_{_k} \rceil}}\}\).