Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 100.01902
Autor: Erdös, Pál; Ko, Chao; Rado, R.
Title: Intersection theorems for systems of finite sets. (In English)
Source: Q. J. Math., Oxf. II. Ser. 12, 313-320 (1961).
Review: Let { a1,...,a2} be a system of subsets of a set of finite cardinality m such that a\mu \not\subset a\nu for \mu \ne \nu. The authors impose an upper limitation l on the cardinals of the sets a\nu, in symbols |a\nu| \leq l, and a lower limitation k on the cardinals of the intersection of any two sets a\mu and a\nu, in symbols |a\mu a\nu| \geq k, and deduce upper estimates for the number n. If k = 1 and 1 \leq l \leq 1/2 m, then n \leq {m-1 \choose l-1}, the inequality being strict in case |a\nu| < l for some \nu. Let k \leq l \leq m, n \geq 2 and either 2l \leq 1+m or 2l \leq k+m, |a\nu| = l for each \nu. Then (i) either |a1 ··· an| \geq k, n \leq {m-k \choose l-1} or |a1 ··· an| < k < l < m, n \leq {m-k-1 \choose l-k-1} {l \choose k}3; (ii) if m \geq k+(l-k){l \choose k}3, then n \leq {m-k \choose l-k}. Finally, the authors discuss the inequality imposed on m in (ii) and present some problems due to the replacement of the condition a\mu \not\subset a\nu by a\mu \ne a\nu.
Reviewer: A.Salomaa
Classif.: * 05D05 Extremal set theory
Index Words: combinatorics
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag