Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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}$.

share|improve this answer
    
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? –  liaomingxue Dec 15 '12 at 12:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.