Given a family F of subsets of [n]={1,2,3,...,n}.
If the cardinality of the intersection of two arbitrary elements of F is not greate than a predefined value S-MIN.
Then what is the sum of cardinalities of all elements of F at most?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
If $A\in F$ has more than $s+1$ elements we may remove $A$ from $F$ and insert instead all the sets $C\subset A$ of cardinality at most $s+1$. Some may already be in $F$, but not those of cardinality $s+1$, forbidden in $F$ because of their intersection with $A$ (themselves), too large. So this increases $\sum _ {A\in F}|A|$, while does not increase the cardinality of the intersection of two arbitrary sets, in the modified family. Therefore, the maximum of $\sum _ {A\in F}|A|$ is attained exactly by the family of all subsets of $[n]$ of cardinality not larger than $s+1$, which is $\sum_{k=1}^{s+1}k \binom {n}{k}=n \sum_{k=0}^{s } \binom {n-1 }{k}$.
answered Dec 14, 2012 at 14:15
-
$\begingroup$ This solution is perfect. However, for s=1, the result reaches n*n somewhat bigger than expected. If we specify more conditions, the number may be reduced. Let's suppose that (1) each element of F is not a subnet of another one; and (2) cardinality of each element of F is not less than s. Then, whether or not the sum will become smaller? $\endgroup$ Dec 15, 2012 at 12:37