##
**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 A_{1},A_{2}, ... ,A_{m(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) > 2^{n-1} for all n and that for n > n_{0}(\epsilon), m(n) > (1-\epsilon)2^{n} log 2. *W. M. Schmidt* [Acta. Math. Acad. Sci. Hung. 15, 373-374 (1964; Zbl 143.02501)] proved m(n) > 2^{n}/(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 > m_{0}, m(n) < (\sqrt 7+\epsilon)^{n} and that **lim**_{n ––> oo} m(n)^{1/n} exists. In the present paper the author uses a non-constructive method to show that m(n) < n^{2}2^{n+1} (and hence **lim**_{n ––> oo} m(n)^{1/n} = 2), and suggests that m(n) = 0(n2^{n}) is a reasonable guess.

**Reviewer: ** W.Moser

**Classif.: ** * 05D05 Extremal set theory

04A20 Combinatorial set theory

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag