Premium
Sets of finite sets satisfying union conditions
Author(s) -
Daykin David E.,
Frankl Peter
Publication year - 1982
Publication title -
mathematika
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.955
H-Index - 29
eISSN - 2041-7942
pISSN - 0025-5793
DOI - 10.1112/s0025579300012237
Subject(s) - mathematics , cardinality (data modeling) , combinatorics , conjecture , finite set , discrete mathematics , mathematical analysis , computer science , data mining
Let ℱ denote a set of subsets of X = {1, 2,…, n). Let deg( i ) be the number of members of ℱ containing i and val(ℱ) = min {deg ( i ): i ∈ X ). Suppose no k members of ℱ have union X . We conjecture val(ℱ) ≤ 2 n‐k‐1 for k ≥ 3. This is known for n ≤ 2k and we prove it for k ≥ 25. For k = 2 an example has val(ℱ) > 2 n‐2 (l−n ‐0·651 ) and we prove val(ℱ) ≤ 2 n‐2 (1–n ‐1 ). We also prove that if the union of k sets one from each of ℱ 1 ,…, ℱ k has cardinality at most n – t then min {cardinality ℱ j } < 2 n α t where α k = 2α − 1 and ½ < α < 1.