Completely Separating Systems of k-Sets

Colin Ramsay and Ian T. Roberts, School of Mathematics, Northern Territory University, and
Frank Ruskey, Dept. of Computer Science, Univertity of Victoria

Abstract

Dickson [On a problem concerning separating systems of a finite set, Journal of Combinatorial Theory, 7 (1969), 191-196.] introduced the notion of a completely separating set system. We study such systems with the additional constraint that each set in the system has the same size.

Let T denote an n-set. We say that a subset S of T separates i from j if i \in S and j \not\in S. A collection of k-sets C is called a (n,k)-separator if, for each ordered pair (i,j) \in T \times T with i \neq j, there is a set S \in C which separates i from j. Let R(n,k) denote the size of a smallest (n,k)-separator. For n > k(k-1) we show that R(n,k) = ceiling( 2n/k ). We also show that R(2m,2m-1) < 2m and demonstrate various recursive relationships that are used to determine the exact values of R(n,k) for k < 5.