Colin Ramsay and Ian T. Roberts, School of Mathematics,
Northern Territory University, and
Frank Ruskey, Dept. of Computer Science, Univertity of Victoria
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(2^{m},2^{m-1}) < 2m and demonstrate various recursive relationships that are used to determine the exact values of R(n,k) for k < 5.