510.84 I46r ILLINOIS— UNIVERSITY no.629-630 AT URBANA-CHAMPAIGN— cop. 2 DEPT. OF COMPUTER SCIENCE REPORT CENTRAL CIRCULATION BOOKSTACKS The person charging this material is re- sponsible for its renewal or its return to the library from which it was borrowed on or before the Latest Date stamped below. You may be charged a minimum fee of $75.00 for each lost book. Theft, mutilation, and underlining of book* are reasons for disciplinary action and may result in dismissal from the University. TO RENEW CALL TELEPHONE CENTER, 333*8400 UNIVERSITY OF ILLINOIS LIBRARY AT URBANA-CHAMPAIGN SEP 2 7 1996 DHL 3 200? When renewing by phone, write new due date below previous due date. L162 Q/VYT mc ON A PROBLEM OF KATONA ON MINIMAL SEPARATING SYSTEMS by Andrew Chi- Chin Yao March I97U ON A PROBLEM OF KATONA ON MINIMAL SEPARATING SYSTEMS by Andrew Chi -Chin Yao March I97U Department of Computer Science University of Illinois at Urbana-Champaign Urbana, Illinois This work was supported in part by the National Science Foundation under Grant No. US NSF GJ^1538. --33 ^ « X ii ABSTRACT Let S be an n- element set. In this paper, we determine the smallest number f(n) for which there exists a family of subsets of S {A,, A , ..., A / \) with the following property: Given any two elements x, y e S (x^y), there exist k, £ such that A^ H A„ = ft, and x g A^_, y e A.. In particular it is shown that f(n) = 3% o n when n is a power of 3. LIBRARY UNIVERSITY OF ILLINOIS W UH (ANA CHAMPAIGN Digitized by the Internet Archive in 2013 http://archive.org/details/onproblemofkaton629yaoa 1. Introduction Let S be a finite set. We shall say "(A, B) separates (x, y)" where x, y € S and A, B c= S, ifxeA,yeB, and A n B = j/S. A family of subsets F is called a total separating system for S if, for any two elements x, y e S, x f y, there exist A, B e F such that (A, B) separates (x,y). Recently Katona [1] raised the following question: For a set S of n elements, what is the smallest integer f(n) such that there exists a total separating system for S with f(n) members? A similar question was settled some time ago by J. Spencer [2] for completely separating systems. (A completely separating system is slightly different from a total separating system). In this note we solve Katona' s problem. Our main result is the following theorem: Main Theorem Let S = fx_, x_, .... x _}. If f(n) is the smallest l 1 ' n-l J integer such that there exists a total separating system F = {A,, A^, ..._, A f(n)} f ° r S ' then f ( 1 ) = °' f ^ = 2 ' and r 3£ if 3 > n > 2-3^ "- f(n) = i 3^+1 if k.^' 1 > n < ?> & (l) ^ 3i+2 if 2-3^ > n > k'3^' 1 where £ > 1. The above values of f(l) and f (2 ) are obviously correct, therefore we shall only be interested in determining f(n) for n > 3. In Section 2 we shall derive a recursive inequality for f(n) which forms the basis for proving lower bounds. In Section 3 it is shown that f(n) = 3% - n when n is a power of 3. The general formula for f(n) is proved in Section k by explicit construction of separating systems and by solving the recursive inequality derived in Section 2. 2. The Basic Inequality Let F = {A , A , . .., A / \) be a minimal total separating system where n > 2. We may assume, without loss of generality, that for any j (l 2 such that (i) B. n A = fi i = 1, 2, ..., k-1 (2) (ii) A U B 1 U B 2 U ... U B k _ x = S (3) Proof. Let {B n , B c , ..., B n . } = {C| C e F, C n A = 2. We shall prove (ii) is true. Suppose (ii) were not true, we would have S - (A U B 1 U B 2 U ... U B k _ 1 ) ^ 0. Let R = S - (A U B U B U ... U B ). We claim that F', which is obtained by replacing the member A by A U R in the family F, is still a total separating system. This, of course, will be a contradiction. To prove our claim, we first note that for any two elements x., x. e S, there exist C,, C in F such that (C-,,C p ) separates (x., x.). There are two cases: Case(l) C f A, C^ £ A Obviously both C and C are still in F', and they will separate (x., x. ) for F'. Case (2) C= A (The case C p = A can "be treated similarly.) Since C n C = fi, I.e., C^A- fi, we have C 2 = B. for some i (l < i < k-l) by definition of the B.'s. Therefore, tJ R fl C n = R H B. = 0. Hence (A U'R, CL) separates (x., x.) for F'. 2 1 r 2 l j Thus we have shown that F' is also a separating system. This completes the proof of Lemma 2.1. Lemma 2.2 f(n) > f(n') if n > n'. Proof. Let S - [x Q , x ± , ..., x^}, and S f = {x Q , x^ . .., x^J If F = {A,, Ap, ..., kr., \} is a total separating system for S, then F' s {A. D S|l < i < f(n)} is a total separating system for S'. Q.E.D. Theorem 2.3 For n > 2, we have f(n) > k + f{\-r\ ) for some integer k > 2. Proof. Let F = {A., k , ..., k , x} be a minimal separating system that satisfies the assumption made at the beginning of this section. Let k g be such that |aJ = max |A. | . Applying Lemma 2.1 Xj Xj i / • ^-.o / „ \ -^ l r|i w Since B. H A- = for all i, we can easily show that the family F - fA„, B... B , .... B n .,}, when restricted to the set A„, must form 1 I 1 2 k-l J £ a total separating system for k Q . This proves Xj f(n) > k + f(|A^|) (5) From (k), (5) and Lemma 2.2, we obtain f(n) > k + f(r#l) for some k > 2 (6) Q.E.D. (k) is the basic inequality to be used for deriving lower bounds, Before proving the general result we will drive a simple formula for f(3 ) which serves to illustrate the general technique. 3. A Special Case: f(3 k ) = 3k, k > We shall prove a theorem from which the inequality f (3 ) > 3k follows immediately. Then we shall show f (3 ) < 3k to complete the proof. Theorem 3.1 f(n) > 3%^ n for a11 n > 1. Proof. We shall prove by induction. First we note f(l) = 0, f(2) = 2 satisfy this inequality. Suppose the theorem is true for all n such that n < n~. From Theorem 2.3 we have f(n ) > k + f(r-^i) V > k + 3% 3 r-£-i > (k - 3%o k ) + 3H? n for some k > 2 It is easy to prove k - 3%o k > f° r a ^- positive integer k. Therefore, f(n ) > 3%on and the induction is complete. Corollary 3.2 f(3 k ) > 3k for k > To prove f(3 )< 3k it is sufficient to construct a total separating system F of 3k members for the set S = {x , x , ..., x } with n = 3 - 1. To do this we consider the ternary number representations for p, < p < n - 1. Let * pO pi p£ P^k-1 where a. , a, ..., a e {0, 1, 2}. We assert that the following pO pi Pj -K""l definition gives the family we want: f & {Ar^|0 < i < k - 1, 3 = 0, 1, 2} J where A* 1 ^ = fx la . = j) for < i < k - 1, j =0, 1, 2. j p 1 pi -- Clearly, (i) F has 3k members. (ii) A^ i} n a^ } =jz5if j j> j\ (iii) For any two elements x , x , with p f p*, there exists i such that a . ^ a f . since the ternary representations of two different numbers are never the same. Let j = a . , j ' s a ,., then x e A. , x . e A. , . pi' ° p'l' p j ' p f j ' This proves F to be a total separating system with 3k members as asserted. We have thus proved f(3 ) = 3k. k. Proof of Main Theorem Since f(n) is a non-decreasing function of n (Lemma 2.2), we need only to establish the following inequalities in order to prove (l): Upper bounds: f(3^) < 3i f(^3 i_1 ) < 3i + 1 (7) f(2-3 i ) < 3£ + 2 far i > 1 Lower bounds: f(3 +l) > 3i + 1 f(2.3^" 1 +l) > 3£ (8) f(lf.3^' 1 +l) > 3J + 2 f or £ > 1 (A) Proof of Upper Bounds Lemma k.l f(3^) < 3i Proof. This was proved in Section 2. Lemma U.2 f (2. 3 ) < 3^ + 2 Proof. Write S = [y Q , y , ..., y^, z Q , z ± , ..., zj where o m = 3 - 1. As in Section 3, represent each p, < p < m, as a ternary- number £-1 P = Z a . 3 1 i=0 P 1 Now define a family F "by F = {{y , y ± , .... y m ),Cv z i' "" z m^ u £ A j 1° - i - £ ' lf d = °' 1 ' 23 where A. = [y la . = j] U {z la . = j}. By arguments similar to those L p 1 pi J L p 1 pi J used in Section 3 it is easy to see that F is a total separating system i i £ for S. Since F has 3£ + 2 members and |S| = 2. 3 , we obtain f(2-3 i ) < 3£ + 2. Lemma k.3 f(^3 i-1 ) < 3£ + 1 >1 A total separating system for S with 3^+1 can be constructed as follows Proof. Let S = fx 1 1 < q < k, < p < 3 - 1} . qp' - - - - F = {B |q = 1, 2, 3, k) tW^O < i < £ - 2, j = 0, 1, 2} where B - {x . |o < i < 3 £ ~ 1 - 1} for q = 1, 2, 3, h, and A: 1 ' = {x |l < q < k, a . = j} for < i < £ - 2, j =0/1, 2. This implies f(U.3^ _1 ) < 31 + 1 since |s| = ^-3 . Lemma ^.1, h.2, k.3 complete the proof for upper bounds as given by (7). (b) Proof of Lower Bounds Before proving (8) we need an auxiliary result. Lemma h.k For k > k, k + 3%o(4) > - 1 (9) For k > 5, k + 3% 3 (^) > - 2 (10) Proof. These inequalities can be established by observing that (9) and (10 ) are true for k = k and k = 5 respectively and the fact that the function k + 3%^(r) is non-decreasing for k > k. We are now ready to prove (8). The proof will be broken down into the next three lemmas. Lemma h.3 f (3^+1) > 31 + 1 for £ > 1 (11) Proof. From Theorem 3.1 f(3^+l) > 3% 3 (3^+l) > 3£ It follows that f(3 +1) > 3£ + 1, since f(n) is an integer. Lemma k.6 f(2.3^ _1 +l) > 3£ for £ > 1 (12) Proof. We shall prove (12) by induction. From Theorem 3.1, it follows f(3) > 3. Therefore (12) is true for £ = 1. Now suppose (12) is true for £, we shall show (12) is also true for £ + 1. From Theorem 2.3, f(2- 3^+1) > k + f(r 2 *^ +L | ) for some k > 2 8 There are three cases: Case (i) k = 2 f (2- 3^+1) > 2 + f(3^+l) > 2 + (3i+l) = 3U+1) where Lemma U.5 was used. Case (ii)k = 3 f(2«3 i +l) > 3 + f(2.3 f_1 +l) > 3 + 3i = 3U+1) Case (iii)k > 1+ f (2'3^+l) > k + ?(\ 2 'l +± ] ) > k + 3% 2 (^-) where Theorem 3.1 was used in the last step. New, using inequality (9), we obtain: f(2.3 i +l) > k + 3% 3 J^ + 3(i+l) > - 1 + 3U+1) It follows, f (2. 3^+1) > 3(i+l) Therefore, in all cases we have shown that (12) is true for £ + 1. This completes the induction. Lemma k.7 t(k'3 +l) > 3i + 2 for i > 1 (13) Proof. We shall prove (13) by induction. According to Theorem 2.3, f(n) > k + f(r#l) for some k > 2 (lk) First w use (lU) to prove that (13) is true for £ = 1. Case (i) k = 2 f(5) > 2 + f(r|l) = 2 + f(3) > 5 Case (ii) k = 3 f(5) > 3 + f (rfl) = 3 + f(2) > 5 Case (iii) k = 4 f(5) > U + f(rfl) = ** + f(2) > 5 Case (iv) k = 5 f(5) > 5 + f(l) = 5 9 In all cases (1*0 leads to f(5) > 5. Therefore (13) is true for I = 1. Now suppose (13) is true for H, we shall prove that it is also true for £ + 1. Again, we use (1*0 : Case (i) k = 2 f(U-3 i +l) > 2 + f(2-3^+l) > 2 + 3(i+l) where Lemma k.6 was used in the last step. Case (ii) k = 3 f(U-3^+l) > 3 + f(U.3 i_1 +l) > 3 + (3i+2) = 3(i+l) + 2 Case (iii) k = k f(k-3 £ +l) > h + f(3^+l) > ^ + 3£ + 1 = 3(i+l) + 2 where Lemma *+. 5 was used. Case (iv) k > 5 f(^3^+l) > k + f(T^ r ti l) > k + 3 ^ 3 (^_) where Theorem 3.1 was used in the last step. Now applying (10) we obtain f(U-3^+l) > k + 3% 3 (^) + 3(i+2) > - 2 + 3(i+2) This leads to f^^+l) > - 1 + 3U+2) = 3U+1) + 2 Therefore, in all cases, (1*0 leads to f (U. 3^+1) > 3(i+l) + 2 Thus (13) is true for £ + 1 and the induction is complete. The above three lemmas {k.5, h.6, k.7) complete the proof of (8). Prom the results in (A), (B), we have shown that both the upper bound (7) and the lower bound (8) are true. This then implies the Main Theorem which we have mentioned at the beginning of this section. 10 After this work was completed, it was subsequently discovered by D. E. Muller that the problem considered here can be shown to be equivalent to the problem of finding a graph with m nodes with the largest number of maximal cliques. That latter problem was solved earlier by different methods. [3]>[^] 11 REFERENCES [1] G. 0. H. Katona, "Combinatorial Search Problem, " A Survey of Combinatorial Theory edited by J. N. Srivastava, et al., North Holland, 1973. [2] J. Spencer, "Minimal Completely Separating Systems," J. Combin. Theory , 8, 1970, pp. hkG-hWj . [3] R. E. Miller and D. E. Mailer, "A Problem of Maximum Consistent Subsets, " IBM Research Report RC-2^-0, J. T. Watson Research Center, Yorktown Heights, New York, i960. [h] J. W. Moon and L. Moser, "On Cliques in Graphs," Israel J. of Math, 3, 1965, PP. 23-28. BIBLIOGRAPHIC DATA SHEET 1. Report No UIUCDCS-R-7^-629 3. Recipient's Accession No. 5. Report Date March 197 1 ! 4. Title and Subtitle On a Problem of Katona on Minimal Separating Systems 7. Author(s) Andrew Chi _ Chih Yao 8- Performing Organization Rept. No. 9. Performing Organization Name and Address Department of Computer Science University of Illinois Urbana, Illinois 10. Project/Task/Work Unit No. 11. Contract /Grant No. GJ U1538 12. Sponsoring Organization Name and Address National Science Foundation Washington, D.C. 13. Type of Report & Period Covered 14. 15. Supplementary Notes 16. Abstracts Let S he an n-element set. In this paper, we determine the smallest number f(n) which there exists a family of subsets of S {A,, Ag. , .., A f / x} with the following property: Given any two elements x, y e S (xfo), there exist k, £ such that A k D A^ / 0, and x e A,, y e A . In particular it is shown that f(n) = 3%o n when n is a power of 3. 17. Key Words and Document Analysis. 17a. Descriptors 17b. Identif iers/ODen-Ended Terms 17c. COSATI Field/Group 18. Availability Statement FORM NTIS-35 ( 10-70) 19. Security Class (This Report) UNCLASSIFIED 20. Security Class (This Page UNCLASSIFIED 21. No. of Pages 22. Price USCOMM-DC 40329-P7 1 S3 'V n >. s UNIVERSITY OF ILLINOIS-URBAN* 3 0112 002541370