Completely separating systems of \(k\)-sets (Q1382833): Difference between revisions

A set system separates the elements of the underlying set if for all elements \(i\) and \(j\) with \(i\neq j\) there exists an element of the system containing one of them and avoiding the other. In 1961 Rényi asked for the minimum size of a separating system on a finite underlying set. A separating system is complete if there exists a set containing \(i\) and avoiding \(j\) and another one containing \(j\) and avoiding \(i.\) The notion was introduced by \textit{T. J. Dickson} [J. Comb. Theory 7, 191-196 (1969; Zbl 0208.02403)]. This paper examines the case where all elements of the completely separating system have the same cardinality \(k.\) If the underlying set has \(n \geq k(k-1)\) elements then it is shown that the minimal completely separating system with \(k\)-element subsets has precisely \(\lceil 2n / k \rceil\) sets. Several recursive relationships for the minimal size of completely separating \(k\)-systems are introduced as well.