Completely Separating Systems of k-Sets

Colin Ramsay and Ian T. Roberts

School of Mathematics, Northern Territory University, Darwin, Northern Territory, Australia

     (Email: cram@it.ntu.edu.au and robertsi@darwin.ntu.edu.au)

Frank Ruskey ^{∗}

Dept. of Computer Science, University of Victoria, Victoria, B.C., V8W 3P6, Canada

                    (Email: fruskey@csr.uvic.ca)

May 27, 1996

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 ∈ S and j ∉ S. A collection of k-sets C is called a (n, k)-separator if, for each ordered pair (i, j) ∈ T × T with i ≠ j, there is a set S ∈ 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) = ⌈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.

Keywords: Extremal set theory, Separating system, Completely separating system. AMS Classification: 04A20, 05D05.

∗Research supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant A3379.

1 Introduction

In 1961 Rényi [6] raised the problem of finding minimum separating systems in the context of solving certain problems in information theory. Subsequently, several variants have been treated in the literature. It is the purpose of this paper to introduce and partially solve another natural variant of the problem. We begin by introducing some notation and terminology.

Let [n] denote the set {1, 2, …, n}. A set S ⊆ [n] separates i from j if i ∈ S and j ∉ S. A collection C of subsets of [n] is a separator if, for each i, j ∈ [n] with i ≠ j, there is a set S in C that separates i from j. If, for each (i, j) ∈ [n] × [n] with i ≠ j, there is a set S in C that separates i from j and a set T that separates j from i, then we call C a complete separator. If in addition, the sets S and T that completely separate i, j are required to be disjoint, then C is a total separator. Observe that any complete separator is a separator, but not vice-versa. E.g., {{1, 2}, {1, 3}} is a separator but is not a complete separator since, even though 1 is separated from 2 by {1, 3}, element 2 is not separated from 1.

The generic problem is to find separators of smallest size; i.e., containing the least number of sets. Let S(n) denote the size of a smallest separator of [n]. Rényi [6]showed that S(n) = ⌈lgn⌉.^{1} Let S(n,_{≤}k) and S(n,_{=}k) denote the size of a smallest separator where each set is constrained to have at most k elements and exactly k elements, respectively. Katona [4] showed that these two quantities are identical and established upper and lower bounds on S(n, k) (hereafter we use S(n, k) to denote S(n,_{=}k)). Wegener [8] simplified the proof of Katona and slightly improved the upper bound. Their results are combined in the following theorem.

Theorem 1 (Katona-Wegener) If k ≥ ⌊n/2⌋, then S(n,_{≤}k) = ⌈lgn⌉. If k < ⌊n/2⌋, then

\frac{n}{k} \frac{logn}{logen/k} ≤ S(n,_{≤}k) ≤ ⌈\frac{logn}{log⌈n/k⌉} ⌉ (⌈n/k⌉ − 1).

Completely separating systems were introduced by Dickson [3]. Let R(n) denote the size of a smallest completely separating system on [n]. He showed that R(n) ∼ lgn. Spencer’s [7] obtained the sharper result that

R(n) = min\{t : \binom{t}{⌊t/2⌋} ≥ n\}.

Let R(n,_{≤}k) and R(n,_{=}k) denote the size of a smallest complete separator, where each set is constrained to have at most k elements and exactly k elements, respectively. Cai [1] shows that

R(n,_{≤}k) = ⌈2n/k⌉, if n > k^{2}/2 ≥ 2.

1By lgn we mean log_{2} n.

Cai [2] also generalized completely separating systems in a graph theoretic setting.

Our focus here is on complete separators, with the restriction that all the sets in the collection C are k-subsets of [n]. We call such a set system an (n, k)-separator. The size of a smallest (n, k)-separator is R(n,_{=}k) (which hereafter is denoted R(n, k)). For example, R(6, 3) ≤ 4, since C = {{1, 2, 3}, {1, 5, 6}, {2, 4, 6}, {3, 4, 5}} is a (6, 3)-separator. In fact R(6, 3) = 4 and for k ≠ 3, R(6, k) = 6. Note that any collection C of k-subsets of [n] that is a superset of a (n, k)-separator is also a (n, k)-separator.

Where no confusion arises we denote collections of sets in an abbreviated form, omitting the braces and the commas of the contained sets. Thus the example given earlier will be written C = {123, 156, 246, 345}. Elements greater than 9 are represented using the letters A, B, etc. Given a set system Q and an integer p, we use Q + p to denote the set system obtained by adding p to each element of each S ∈ Q.

It is tempting to suppose that, as in the separating case, R(n,_{≤} k) equals R(n, k), which would allow us to use the results of Cai. This supposition is incorrect. Consider, for example, R(9,_{≤}4) = 5. (A set system meeting this equality is {1234, 4567, 7891, 258, 369}.) However, it turns out that R(9,_{=}4) = 6.

Observe that the following inequalities hold.

S(n) ≤ S(n,_{≤}k) = S(n, k) ≤ R(n,_{≤}k) ≤ R(n, k)

Let T(n) denote the size of a smallest total separator on [n]. Yao [9] showed that T(3^{m}) = 3m.

2 Results

In this section we present our results, starting with a simple symmetry observation.

Lemma 2 The symmetry R(n, k) = R(n, n − k) holds for all 1 ≤ k < n.

Proof: By taking complements, a (n, k)-separator becomes a (n, n − k)-separator. □

The next lemma reflects the fact that every element must occur at least twice in a (n, k)-separator, when k ≠ 1. This is the “trivial lower bound”.

Lemma 3 For all 2 ≤ k < n,

R(n, k) ≥ ⌈\frac{2n}{k} ⌉ . (1)

Proof: For k ≥ 2 every element of [n] must appear in at least two k-sets of any (n, k)-separator. Thus k · R(n, k) ≥ 2n from which (1) follows. □

A trivial upper bound is

R(n, k) ≤ n, (2)

which follows from consideration of the set system

{{1, …, k}, {2, …, k + 1}, …, {n, 1, …, k − 1}}.

The following lemma gives a slight improvement on Lemma 3 for some cases.

Lemma 4 For all 2 ≤ k < n,

R(n, k) ≥ ⌈\frac{n}{k} ⌈\frac{n − 1}{n − k} ⌉⌉ . (3)

Proof: For k ≥ 2, every element a of [n], in a (n, k)-separator, must occur without each of the other n − 1 elements of [n]. Each time a occurs in a k-subset, it is separated from n − k elements of [n]. Therefore a must occur in at least ⌈\frac{n−1}{n−k} ⌉ sets. This value replaces the constant 2 in Lemma 3. □

Note that (3) is also trivially valid for k = 1 (see Lemma 5). To use Lemma 4 for k′ < n/2, we use Lemma 2 and then Lemma 4 for k = n − k′. This provides a better bound than Lemma 3 only for those k near n/2. For example, if n = 16, k′ = 7 then R(n, k′) ≥ ⌈2n/k⌉ = 5, by Lemma 3. For n = 16, k = 9, Lemma 4 gives R(n, k) ≥ 6, so R(16, 7) ≥ 6, by Lemma 2.

Interestingly, this lemma provides an improved bound only in the case where the bound in Lemma 3 is 5. Lemma 4 improves this to 6 in most, but not all, of these cases.

Lemma 5 For n ≥ 2, R(n, 1) = n. For n ≥ 3, R(n, 2) = n.

Proof: That R(n, 1) ≤ n follows from (2). That R(n, 1) ≥ n follows from the observation that each element of [n] must appear in at least one set.

Now consider the case where k = 2. That R(n, 2) ≤ n follows from (2). For the lower bound use Lemma 3. □

Note that Lemma 2 immediately gives us R(n, n − 1) = n, for n ≥ 2 and R(n, n − 2) = n, for n ≥ 3.

Use C[x] to denote {S ∈ C : x ∈ S}. Observe that a set system C of k-subsets of [n] is a (n, k)-separator if and only if ⋂{S ∈ C[x]} = {x}, for all x ∈ [n]. In particular if, for all x ∈ [n], there are two sets S, T ∈ C such that S ∩ T = {x}, then C is a (n, k)-separator. We will use this criterion in the proof of the next theorem.

Our main result is the following theorem, which tells us that the bound in Lemma 3 is attained for sufficiently large n compared to k.

Theorem 6 If n ≥ k(k − 1) and 1 < k < n, then

R(n, k) = ⌈\frac{2n}{k} ⌉ .

Proof: Let n = kp + r where 0 ≤ r < k. Our strategy is to create a (n, k)-separator so that kp elements appear in exactly two sets, and the remaining elements appear at least twice. The cases p ≥ k and p = k−1 require slightly different constructions, and each of these cases is broken into subcases depending on whether r = 0, 0 < r ≤ k/2, or r > k/2.

(A) If p ≥ k, then imagine a p by k matrix M whose jth column consists of the integers 1 + (j − 1)p, 2 + (j − 1)p, …, jp, in that order. We form one set system R = {R_{1}, R_{2}, …, R_{p}} by taking the rows of M, and another C = {C_{0}, C_{1}, …, C_{p−1}} by successively stripping k elements from the columns of M from top-to-bottom and left-to-right. To be more precise, define

C_{j} = {1 + jk, 2 + jk, …, k + jk} for 0 ≤ j ≤ p − 1 and
R_{i} = {i, i + p, …, i + (k − 1)p} for 1 ≤ i ≤ p.

Note that C is a partition of [kp], as is R. Furthermore |R_{i} ∩ C_{j}| ≤ 1 for all i and j. Hence C ∪ R is a (kp, k)-separator. Thus if r = 0 we are done.

Now assume that r > 0. To get a (n, k)-separator we have to account for the remaining elements, call them E, where E = [n] \ [kp]. There are two subcases, r ≤ k/2 and r > k/2. Take D to be the diagonal elements of M. That is,

D = {1, 2 + p, …, k + (k − 1)p} = {i + (i − 1)p : 1 ≤ i ≤ k}.

We now modify the sets in R by removing an element of D (if possible) from each set R_{i} and replacing it with an element of E so that each element of E gets used, as close as possible, the same number of times. To be unambiguous, let R′ = {R′_{1}, R′_{2}, …, R′_{p}} where

R′_{i} = / \begin{matrix}R_{i} \ \{i + (i − 1)p\} ∪ \{kp + 1 + ((i − 1) mod r)\} & if 1 ≤ i ≤ k, \\ R_{i} & if k < i ≤ p. \end{matrix}

(i) If r ≤ k/2 then S = R′ ∪ C ∪ {D} is a (n, k)-separator of size 2p + 1. To show that S is a separator, we observe that, for each element x ∈ [n], there are two sets containing x whose intersection is {x}. If x ∈ D then the two sets are D and the set C_{j} that contains x (recall that C is a partition of [kp]). If x ∈ [kp] \ D, then use the two sets C_{j} and R_{i} that contain x, as in the r = 0 case. If x ∈ [n] \ [kp], then the two sets are R_{x−kp} and R_{x−kp+r} .

(ii) If r > k/2, then there are some elements of E that have occurred only once in S; we need to form another set containing these singletons. The elements 1 + kp, 2 + kp, …, k−r+kp have all appeared twice, the elements 1+k−r+kp, 2+k−r+kp, …, n have appeared only once. Define X to be the singletons together with the first 2(k−r) elements of D. That is,

X = {1 + k − r + kp, 2 + k − r + kp, …, n}
∪ {1, 2 + p, …, r + (2(k − r) − 1)p}.  (4)

Now S ∪{X} is a (n, k)-separator of size 2p+2. This follows from the same arguments given in the r ≤ k/2 case, except for those elements x ∈ X \ D (i.e., the singletons); those elements are dealt with by noting that X ∩ R_{x−kp} = {x}.

(B) If p = k − 1, then imagine a k by k matrix N constructed from M by adding an extra bottom row identical to the first row of M but rotated left one position. We now form a set system R = {R_{2}, R_{3}, …, R_{k−1}} by taking all rows of N except the first and last, and another set system C = {C_{0}, C_{1}, …, C_{k−1}} consisting of the columns of N. To be more precise, define

C_{j} = {1 + j(k − 1), 2 + j(k − 1), …, k + j(k − 1)} for 0 ≤ j ≤ k − 1 and

R_{i} = {i, i + k − 1, …, i + (k − 1)(k − 1)} for 1 ≤ i ≤ k − 1.

The element k + (k − 1)^{2} of C_{k−1} is taken to be 1. The set R_{1} will be used only when r > 0.

Note that C_{j} ∩ C_{j+1} (index addition taken mod k) is {k + j(k − 1)} and that otherwise the intersection of two sets in C is empty. The union of all sets C_{j} is [n]. The elements k + j(k − 1) do not occur in R. In fact, R forms a partition of [n] \ {k + j(k − 1) : 0 ≤ j ≤ k − 1}. Since |R_{i} ∩ C_{j}| ≤ 1 for all i and j, the union C ∪ R is a (pk, k)-separator. Thus if r = 0 we are done.

Now assume now that r > 0. To obtain a (n, k)-separator we have to account for the remaining elements, call them E, where E = [n] \ [kp]. Again, we have two subcases, r ≤ k/2 and r > k/2.

(i) If r ≤ k/2 then set, for 0 ≤ j ≤ k − 1,

C′_{j} = C_{j} \ {k + j(k − 1)} ∪ {1 + kp + (j mod r)}.

Now the intersection of two sets in C′ = {C′_{0}, C′_{1}, …, C′_{k−1}} is either empty or is an element of E. It is easy to verify that the set system S = C′ ∪ R ∪ R_{1} is a (n, k)- separator of size 2k − 1, as required.

(ii) If r > k/2 then define X as in (4). The set system S ∪ {X} is a (n, k)-separator of size 2k, as required. Again, we leave verification to the reader. □

Lemma 7 For k = 3, R(4, 3) = 4, R(5, 3) = 5, and R(n, 3) = ⌈2n/3⌉ if n ≥ 6.

Proof: Note that R(4, 3) = R(4, 1) = 4 and R(5, 3) = R(5, 2) = 5, using Lemmas 2 and 5. For n ≥ 6, the result follows from Theorem 6. □

Lemma 8 For k = 4, R(5, 4) = 5, R(6, 4) = 6, R(7, 4) = 5, R(8, 4) = 5, R(9, 4) = 6, R(10, 4) = 5, R(11, 4) = 6 and R(n, 4) = ⌈n/2⌉ if n ≥ 12.

Proof: The values for R(5, 4), R(6, 4), and R(7, 4) follow from Lemma 2 and our earlier results for k = 1, 2, 3.

That R(8, 4) ≤ 5 follows from considering the set system C = {1234, 1678, 2578, 3568, 4567}. By Lemma 3, R(8, 4) ≥ 4. Assume R(8, 4) = 4. Then each element occurs in exactly 2 sets. We can assume S = {1, 2, 3, 4} occurs. To separate the elements of S, with only one occurrence of each element, at least 4 more sets are required. Hence R(8, 4) ≠ 4 and so R(8, 4) = 5.

By Lemma 3, R(9, 4) ≥ 5. We show that R(9, 4) ≠ 5 as follows. We may assume that the set A = {1, 2, 3, 4} occurs in a (9, 4)-separator containing 5 sets. To separate 1234, not all others sets contain only one element of A, as we need to separate 56789 and R(5, 3) = 5. Thus our separator contains a set other than A with more than one element of A. Noting the comment before Lemma 3, no more than 2 elements of A can occur together in another set, else these elements cannot be separated within the given constraints. Thus we may assume the set 1256 occurs. Then, to separate 1 and 2, 1 must occur in one set and 2 in another. Similarly, to separate 5 and 6, 5 must occur in one set and 6 in another. Hence, one of the pairs 15, 16, 25, 26 occurs again. Assume it is 15. To separate these, 5 must occur in another set without 1. This means that each of 1,2,5 occur in at least 3 sets; contradicting the fact that only 2 such elements can exist. Hence, R(9, 4) cannot be 5. To see that R(9, 4) = 6, consider the set system {1234, 1235, 1467, 2568, 3789, 4569}.

That R(10, 4) = 5 follows from the trivial lower bound and the set system {1234, 1567, 2589, 368A, 479A}.

That R(11, 4) = 6 follows from the trivial lower bound and the set system {1234, 4567, 789A, B368, B259, 156A}.

For k ≥ 12, the result follows from Theorem 6. □

How small can n get and still have the conclusion of Theorem 6 still hold?

Lemma 9 If n < \binom{k+1}{2}, 1 < k < n, and k|2n, then R(n, k) > 2n/k.

Proof: We prove the contrapositive. If R(n, k) ≤ 2n/k then, by Lemma 3, we must have R(n, k) = 2n/k. Thus each element of [n] occurs exactly twice in a separator. Without loss of generality we may assume that {1, …, k} is a member of a (n, k)- separator. To separate these elements, using each only once more, each of 1 …k must appear in a set by themselves and so there are at least k + 1 sets in the (n, k)- separator. As each element of [n] occurs twice, 2n ≥ k(k + 1), as required. □

The following lemmas show how we can use a (n, k)-separator to construct separators for larger values of n or k.

Lemma 10 If R(n, k) ≤ k + 1, 1 < k < n, then R(n + k + 1, k + 1) ≤ k + 2.

Proof: Let A = {A_{1}, A_{2}, …, A_{k+1}} be a (n, k)-separator. Consider the set system B = {B_{0}, B_{1}, …, B_{k+1}} where B_{0} = {n + 1, n + 2, …, n + k + 1} and B_{i} = A_{i} ∪ {n + i} for i = 1, 2, …, k + 1. It is easy to verify that B is an (n + k + 1, k + 1)-separator. □

Lemma 11 If R(n, k) ≥ k + 1 then R(n + k + 1, k + 1) ≤ 1 + R(n, k).

Proof: The proof is similar to that used to prove Lemma 10, but we need to be more careful about which elements are being added to the sets of the (n, k)-separator A to ensure that the old elements [n] are separated from the new elements B_{0}. Let p = R(n, k) and assume p ≥ k + 1. Our goal is to construct a (n + k + 1, k + 1)- separator C of cardinality p + 1. Let A = {A_{1}, A_{2}, …, A_{p}} be an (n, k)-separator. Consider the set system B = {B_{0}, B_{1}, …, B_{p}} with B_{0} = {n + 1, n + 2, …, n + k + 1} and B_{i} = S_{i} ∪ {b_{i}} for i = 1, 2, …, p, where the exact values of b_{i} are yet to be specified. Let B_{i} be the set subsystem {B_{1}, B_{2}, …, B_{i}}. We select successive values of b_{i} so that for all a ∈ [n], the condition

|B_{i}[a] ∩ B_{0}| ≤ 1, (5)

holds for i = 1, 2, …, p. Taking i = p, this suffices to prove B[a] = {a} for a ∈ [n]. To get B[a] = a for a ∈ B_{0}, we set b_{i} = n + i for i = 1, 2, …, k + 1 (this is where the condition R(n, k) ≥ k + 1 is used). Succeeding values of b_{i} are selected as follows. Noting that b_{1}, b_{2}, …, b_{k+1} satisfy (5), assume that b_{1}, b_{2}, …, b_{m} have been selected to that (5) holds. Let

Q = ⋃_{a∈A_{m+1}} B_{m}[a] ∩ B_{0},

and pick b_{m+1} ∈ B_{0} \ Q. The set B_{0} \ Q is non-empty since |Q| ≤ k. The invariant (5) still holds since B_{m+1}[a] ∩ B_{0} is either empty or is {b_{m+1}} depending on whether B_{m}[a] is non-empty or not. □

Lemma 12 Let p + q = n. Then R(n, k) ≤ R(p, k) + R(q, k).

Proof: A (p, k)-separator P and a (q, k)-separator Q may be used to create a (n, k)- separator C by taking C = P ∪ (Q + p). □

Table 1: Known values of R(n, k) for 2 ≤ n ≤ 48 and 1 ≤ k ≤ min(20, n − 1).

9 Lemma 13 For n ≥ 1, R(4n, 2n) ≤ 2 + R(2n, n).

Proof: Assume that C = {S_{1}, S_{2}, …, S_{m}} is a (2n, n)-separator, where m = R(2n, n). Construct A = {A_{1}, A_{2}, …, A_{m}, A_{m+1}, A_{m+2}} as follows. If i ∈ [m], then A_{i} = S_{i} ∪ (S_{i}+2n). The other two sets are formed by taking A_{m+1} = [2n] and A_{m+2} = [2n]+2n.

We now argue that A has the desired properties. If p, q ∈ [2n], then if S_{i} separates p from q then A_{i} also separates p from q. If p, q ∈ [2n] + 2n, then if S_{i} separates p − 2n from q − 2n then A_{i} separates p from q. If p ∈ [2n] and q ∈ [2n] + 2n, then A_{m+1} separates p from q. If p ∈ [2n] + 2n and q ∈ [2n], then A_{m+2} separates p from q. Thus, in all cases p is separated from q, and so A is a (4n, 2n)-separator of size 2 + R(2n, n). □

As a consequence we have, for example, that R(12, 6) ≤ 6, R(16, 8) ≤ 7, R(20, 10) ≤ 8, R(24, 12) ≤ 8 and R(28, 14) ≤ 10.

Corollary 14 R(2^{m}, 2^{m−1}) ≤ 2m.

Proof: The proof is by induction, the base case R(2, 1) = 2 following from earlier results, and the inductive step following from Lemma 13. □

Note that the bound of the previous lemma is not tight since, for example, R(8, 4) = 5 < 2 · 3. However, it does suggest logarithmic growth along the k = n/2 diagonal. Our final lemma provides us with bounds on the rate of growth of R(n, k) with n, for a fixed k.

Lemma 15 (i) If n ≥ 2k − 2, 1 < k < n, then R(n + 1, k) ≤ 2 + R(n, k), (ii) If n ≥ 2k − 3, 1 < k < n, then R(n + 2, k) ≤ 3 + R(n, k), (iii) If n ≥ 3k − 6, 1 < k < n, then R(n + 3, k) ≤ 3 + R(n, k).

Proof: We start with a minimal (n, k)-separator S. (i) Append to S the sets {1, …, k − 1, n + 1} and {k, …, 2k − 2, n + 1}. (ii) Append to S the sets {1, …, k − 1, n+1}, {1, …, k−1, n+2} and {k, …, 2k−3, n+1, n+2}. (iii) Append to S the sets {1, …, k−2, n+1, n+2}, {k−1, …, 2k−4, n+2, n+3} and {2k−3, …, 3k−6, n+3, n+1}. □

Table 1 contains a summary of the known results for values of R(n, k). The values for k = n/2 have been bracketed to highlight the symmetry. Where exact values are not known the bounds on the value are given. Lower bounds come from Lemmas 3 and 4 and Theorem 9. Upper bounds come from repeated applications of the lemmas from Lemma 10 onwards. Some of the specific cases for k = 5 have been proved by arguments similar to those employed in Lemma 8, while some of the upper bounds come from known example (n, k)-separators.

3 Final Remarks

There are many variations on problems involving separation schemes. To mention one of these, there is the question of minimising the size of a separating system where each set A in the system has 1 < k ≤ |A| ≤ m < n. For more open problems, see Ramsay et al [5].

The authors would like to thank Paulette Lieby for valuable help whilst preparing this paper.

References

[1] M-C. Cai, On a problem of Katona on minimal completely separating systems with restrictions, Discrete Math., 48 (1984), 121–123.

[2] M-C. Cai, On separating systems of graphs, Discrete Math., 49 (1984), 15–20.

[3] T. J. Dickson, On a problem concerning separating systems of a finite set, Journal of Combinatorial Theory, 7 (1969), 191–196.

[4] G. Katona, On separating systems of a finite set, Journal of Combinatorial Theory, 1 (1966), 174–194.

[5] C. Ramsay, I. Roberts and F. Ruskey, Separation of elements in finite sets, Proceedings of AWOCA 6, NTU Press, Darwin, 1994, 37–47.

[6] A. Rényi, On random generating elements of a finite Boolean algebra, Acta. Sci. Math. (Szeged), 22 (1961), 75–81.

[7] J. Spencer, Minimal completely separating systems, Journal of Combinatorial Theory, 8 (1970), 446–447.

[8] I. Wegener, On separating systems whose elements are sets of at most k elements, Discrete Math., 28 (1979), 219–222.

[9] A. C-C. Yao, On a problem of Katona on minimal separating systems, Discrete Math., 15 (1976), 193–199.