Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 201.33704
Autor: Erdös, Paul
Title: On a combinatorial problem. II (In English)
Source: Acta Math. Acad. Sci. Hung. 15, 445-447 (1964).
Review: A family F of subsets of a set M is said to have property B if there exists a subset K of M so that no set of the family F is contained either in K or \bar K (the complement of K in M). P. Erdös and A. Hajnal [ibid. 12, 87-123 (1961; Zbl 201.32801)] investigated property B and its generalizations, and posed the problem: What is the smallest integer m(n) for which there exists a family F, of sets A1,A2, ... ,Am(n) each having n elements, which does not possess property B? They observed that m(n) \leq \binom{2n-1}{n}, m(1) = 1, m(2) = 3, m(3) = 7. The author[Nordisk mat. Tidskr. 11, 5-10 (1963; Zbl 116.01104)] showed that m(n) > 2n-1 for all n and that for n > n0(\epsilon), m(n) > (1-\epsilon)2n log 2. W. M. Schmidt [Acta. Math. Acad. Sci. Hung. 15, 373-374 (1964; Zbl 143.02501)] proved m(n) > 2n/(1+4/n). H. L. Abbott and L. Moser [Can. Math. Bull. 7, 177-181 (1964; Zbl 131.01302)], using a constructive method, proved m(ab \leq m(a)(m(b))a and from this deduced that for n > m0, m(n) < (\sqrt 7+\epsilon)n and that limn ––> oo m(n)1/n exists. In the present paper the author uses a non-constructive method to show that m(n) < n22n+1 (and hence limn ––> oo m(n)1/n = 2), and suggests that m(n) = 0(n2n) is a reasonable guess.
Reviewer: W.Moser
Classif.: * 05D05 Extremal set theory
04A20 Combinatorial set theory
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag