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?
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
2
|
|
|
|
|
2
|
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}$. |
|||
|
