Zentralblatt MATH

Publications of (and about) Paul Erdös
Zbl.No:  179.02801
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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page