On separating systems of a finite set

Katona, Gyula (1966) On separating systems of a finite set. JOURNAL OF COMBINATORIAL THEORY, 1 (2). pp. 174-194. ISSN 0021-9800

Preview

Text paper_4.pdf Download (5MB) | Preview

Abstract

Let H be a finite set, and A1, A2, ..., Am subsets of H. We call a system A separating system, if for any two distinct elements x and y of H there exists an Ai (1≤i≤m) such that either. x ∈ Ai and y ∉ Ai. or. x ∉ Ai and y ∈ Ai. This paper deals with the problem of finding the minimum of m, if additionally {curly logical or}Ai{curly logical or}≤k (1≤i≤m), where 1≤k≤n, and {curly logical or}Ai{curly logical or} is the cardinal number of Ai. We reduce this combinatorial problem to an analytical one, and give a lower and an upper estimation:. frac(log n, log en / k) frac(n, k) ≤ min m ≤ {frac(log 2 n, log n / k)} frac(n, k). © 1966 Academic Press Inc.

Actions (login required)

Edit Item