Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 199.31801
Autor: Erdös, Pál
Title: On a combinatorial problem. III (In English)
Source: Can. Math. Bull. 12, 413-416 (1969).
Review: [Part I in Nordisk. Mat. Tidskr. 11, 5-10 (1963; Zbl 116.01104)]
E.W.Miller, in C. R. Soc. Sci. Varsovie 30, 31-38 (1937; Zbl 017.30003), defines a family of sets {A} th have property B if there exists a set S which meets all the sets Ak and contains none of them. The author and A.Hajnal [Acta Math. Acad. Sci. Hungar. 12, 87-123 (1961; Zbl 201.32801)] define m(n) as the smallest integer for which there is a family of m(n) sets, each with cardinality n, which do not have property B. In Part II [ibid. 15, 445-447 (1964)], the author had found bounds for m(n). In this paper he considers the function mN(n) which is the smallest integer for which there are mN(n) sets Ak each with cardinality n which are all subsets of a set S, |S| = N, and which do not have property B. It is shown that if N = (c+o(1))n then limn ––> oo mN (n)1/n = 2(c-2)(c-2)/2(c-1)(1-c)cc/2, if c > 2 and = 4 if c = 2. To prove this, upper and lower bounds for mN(n) are found, differing byonly 2N. The author suggests that for large values of N the more appropriate function to consider would be mN(n) being the smallest integer for which there is a family of sets not having property B, satisfying Ak \subset S, |S| = N with the restriction that the set of Ak's contained in any proper subset of S has the property B. A symptotic formulae for mN(n) and mN'(n) are not known.
Reviewer: D.I.A.Cohen
Classif.: * 05D05 Extremal set theory
04A99 Miscellaneous topics in set theory
Index Words: combinatorics
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag