## Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  247.05007
Autor:  Erdös, Pál; Spencer, Joel
Title:  On a problem of Erdös and Hajnal. (In Hungarian)
Source:  Mat. Lapok 22(1971), 1-2 (1972).
Review:  Let |S| = n, f(A) a set function which maps every subset of S into an element of S so that f(A) \not in A. A subset B of S is said to be independent if for every A \subset B f(A) \not in B. h(n) is the greater integer for which for every function f there is an independent set having at least h(n) elements. The authors prove

{log n - log log n \over log 2}+o(log log n) < h(n) < {log n+3 log log n \over log 2}+o(log log n).

Classif.:  * 05A10 Combinatorial functions
05A05 Combinatorial choice problems

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag