On a problem of Katona on minimal separating systems |
| |
Authors: | Andrew Chi-Chih Yao |
| |
Affiliation: | Department of Computer Science, University of Illinois, Urbana, IL 61801, U.S.A. |
| |
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{A1,A2,…,Af(n)} with the following property: Given any two elements x, y ∈ S (x ≠ y), there exist k, l such that Ak ∩ Al= ?, and x ∈ Ak, y ∈ Al. In particular it is shown that f(n)= 3 log3n when n is a power of 3. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|