Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 383.05002
Autor: Erdös, Paul; Szemeredi, E.
Title: Combinatorial properties of systems of sets. (In English)
Source: J. Comb. Theory, Ser. A 24, 308-313 (1978).
Review: A family of sets is called a strong (weak) \triangle system if the (cardinality of the) intersection of any two of its members is the same. The paper contains remarks, considerations, conjectures and results on the following functions: f(n,r) = smallest integer for which any family of f(n,r) sets of size n contains a subfamily of r sets which forms a strong \triangle system; g(n,r) is defined similary for weak \triangle systems; F(n,r) = largest integer so that there is a family of subsets of an n-set which does not contain a strong \triangle system of r elements; G(n,r) has the similar meaning for weak \triangle systems; F(n,r,k) and G(n,r,k) are defined similarly with the sole distrinction that only k-subsets are considered. The existence is proved of families of subsets of an n-set not containing weak \triangle systems and having at least n log n/4 log log n members.
Reviewer: W.Dörfler
Classif.: * 05A05 Combinatorial choice problems
04A20 Combinatorial set theory
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag