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