Katona, Gyula (1966) On separating systems of a finite set. JOURNAL OF COMBINATORIAL THEORY, 1 (2). pp. 174194. ISSN 00219800

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.
Item Type:  Article 

Subjects:  Q Science / természettudomány > QA Mathematics / matematika 
SWORD Depositor:  MTMT SWORD 
Depositing User:  MTMT SWORD 
Date Deposited:  30 Jan 2015 09:14 
Last Modified:  30 Jan 2015 09:14 
URI:  http://real.mtak.hu/id/eprint/21125 
Actions (login required)
Edit Item 