On a problem of Katona on minimal separating systems

Andrew Chi Chih Yao

doi:10.1016/0012-365X(76)90085-6

On a problem of Katona on minimal separating systems

Andrew Chi Chih Yao

Faculty of Electronic and Information Engineering

Research output: Contribution to journal › Article › peer-review

8 Scopus citations

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_f(n)} with the following property: Given any two elements x, y ∈ S (x ≠ y), there exist k, l such that A_k ∩ A_l= ∅, and x ∈ A_k, y ∈ A_l. In particular it is shown that f(n)= 3 log₃n when n is a power of 3.

Original language	English
Pages (from-to)	193-199
Number of pages	7
Journal	Discrete Mathematics
Volume	15
Issue number	2
DOIs	https://doi.org/10.1016/0012-365X(76)90085-6
State	Published - 1976

Access to Document

10.1016/0012-365X(76)90085-6

Cite this

@article{4fca5d82a25a42c386f041e48882b90c,

title = "On a problem of Katona on minimal separating systems",

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.",

author = "Yao, \{Andrew Chi Chih\}",

year = "1976",

doi = "10.1016/0012-365X(76)90085-6",

language = "英语",

volume = "15",

pages = "193--199",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - On a problem of Katona on minimal separating systems

AU - Yao, Andrew Chi Chih

PY - 1976

Y1 - 1976

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0042117865

U2 - 10.1016/0012-365X(76)90085-6

DO - 10.1016/0012-365X(76)90085-6

M3 - 文章

AN - SCOPUS:0042117865

SN - 0012-365X

VL - 15

SP - 193

EP - 199

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 2

ER -

On a problem of Katona on minimal separating systems

Abstract

Access to Document

Other files and links

Fingerprint

Cite this