##
**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