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

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