On separating systems whose elements are sets of at most k elements

✍ Scribed by Ingo Wegener

• Book ID: 103055688
• Publisher: Elsevier Science
• Year: 1979
• Tongue: English
• Weight: 423 KB
• Volume: 28
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(79)90101-8

✦ Synopsis

A system A,, . . . , A,,, of subsets of X := (1,. . . , n} is called a separating system if for any two distinct elements of X there is a set Ai (1 G i em) that contains exactly one of the two elements. We investigate separating systems where each set Ai has at most k elements and we are looking for minimal separating systems, that means separating systems with the least number of subsets. We call this least number m(n, k). Katona has proved good bounds on m(n, k) but his proof is very complicated. We give a shorter and easier proof. In doing so we slightly improve the upper bound of Katona.