Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 384.05001
Autor: Deza, M.; Erdös, Paul; Frankl, P.
Title: Intersection properties of systems of finite sets. (In English)
Source: Combinatorics, Keszthely 1976, Colloq. Math. Janos Bolyai 18, 251-256 (1978).
Review: [For the entire collection see Zbl 378.00007.]
Let X be a finite set of cardinality n. If L = {l1,...,\lr} is a set of nonnegative integers l1 < l2 < ... < lr, and k is a natural number then by an (n,L,k)-system we mean a collection of k-element subsets of X such that the interesection of any two different sets has cardinality belonging to L. We prove that if A is an (n,L,k)-system, |A| > cnr-1 (c = c(k) is a constant depending on k) then (i) there exists an l1-element subset D of X such that D is contained in every member of A, (ii) (l2-l1)|/l3-l2)|...|(lr-lr-1)|(k-lr), (iii) prodi = 1r\frac{n-li}{k-li} \geq | A| for n \geq n0(k)).
Parts of the results are generalized for the following cases: (a) we consider t-wise intersections, t \geq 2, (b) the condition |A| = k is replaced by |A| in K where K is a set of integers, (c) the intersection condition is replaced by the following: among q+1 different members A1,...,Aq+1 there are always two subsets Ai, Aj such that |Ai\cap Aj| in L. We consider some related problems. An open question: Let L'\subset L. Does there exist an (n,L,k)-system of maximal cardinality (A) and an (n,L',k)-system of maximal cardinality (A) such that A\supset A'?
Classif.: * 05A05 Combinatorial choice problems
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag