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