Publications of (and about) Paul Erdös
Autor: Erdös, Pál; Hajnal, András
Title: On a combinatorial problem (In Hungarian)
Source: Mat. Lapok 19, 345-348 (1968).
Review: Let S be a set of n elements. Let f(A) be a set function which makes correspond to every subset A of S an element of S-A. Put F(A) = \bigcupB \subset A f(B) where B runs through all subsets of A. Let H(n)be the smallest integer for which there is a function f so that for every S1 \subset S, |S1| \geq H(n) we have F(S) = S. We prove log n/ log 2 < H(n) < log n/ log 2+3 log log n/ log 2+o(log log n).
We conjecture limn = oo (H(n)- log n/ log 2) = oo but cannot even prove H(n) > log n/ log 2+1.
Classif.: * 05D05 Extremal set theory
04A20 Combinatorial set theory
Index Words: combinatorics
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag