Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  434.05001
Autor:  Deza, M.; Erdös, Paul; Singhi, N.M.
Title:  Combinatorial problems on subsets and their intersections. (In English)
Source:  Studies in foundations and combinatorics, Adv. Math., Suppl. Stud., Vol. 1, 259-265 (1978).
Review:  [For the entire collection see Zbl 432.00006.]
Let |S| = n, m(n,l1,l2,k) (respectively, m'(n,l1,l2,k)) denote the cardinality of the largest family of subsets Ai\subset S satisfying |Ai| = k (respectively, |Ai| \leq k) and |Ai1\cap Ai2| = l1 or l2. In this paper we prove
(a) m(n,0,l2,k) \leq \binom{n}{2}, m'(n,0,l2,k) \leq \binom{n}{2}+n+1; equality if k = 2;
(b) m(n,0,l2,k) \leq n, if l2\nmid k, with equality for an infinity of n.
For n \geq n0(k) we show that
(a) m(n,l1,l2,k) \leq \binom{n-l1}2, m'(n,l1,l2,k) \leq \binom{n-l1}{2}+(n-l1)+1;
(b) more exactly, m(n,l1,l2,k) \leq [\frac{n-l1}{k-l1}[\frac{n-l2}{k-l2}]], with equality for an infinity of n.
Classif.:  * 05A05 Combinatorial choice problems
Keywords:  family of subsets
Citations:  Zbl.432.00006

© 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