Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a finite set $A$ with $n$ elements, what would be a good upper bound for the size of a largest collection $\mathcal{F}$ of subsets of $A$ which satisfy the following condition: Any two elements of $\mathcal{F}$ have at most one element of $A$ in common.

Following advice I got on #math, I tried feeding oeis with the values of this count for the first few values of $n$ (namely: $1, 2, 4, 7, 11$), but in the results there I couldn't find any reference to the kind of thing I am interested in.

Would you know of good upper bounds for this? Where/what should I look up?

share|improve this question
    
That yields $150$ results; I don't suppose you looked through all of those? You should calculate one or two more values until you get only a handful of results. –  joriki Dec 6 '12 at 17:42
    
The values for small $n$ you give seem to be $\binom{n}{0}+\binom{n}{1}+\binom{n}{2}$. Is there an example that does better? –  hardmath Dec 6 '12 at 17:59
    
@joriki: There are clearly at least $26$ (hardmath’s observation) and at most $32$, and OEIS gives no useful return for any of the possible values. –  Brian M. Scott Dec 6 '12 at 18:23
    
@joriki: Yes, I did look through all of them, by searching for "subset". Though Brian's answer handles the more general case, I will accept hardmath's answer, since that was what I asked. All: Thank you for your replies and explanations. I get it now. Thanks! –  mathnoob Dec 8 '12 at 13:00

2 Answers 2

up vote 2 down vote accepted

Excluding the empty set and the singleton subsets of $A$, there can be at most $\binom{n}{2}$ subsets of $A$ in $\mathscr{F}$ containing more than one element. This follows by matching unordered pairs in $A$ with sets in $\mathscr{F}$ containing such pairs.

Thus $|\mathscr{F}| \le 1 + n + n(n-1)/2$ and the bound is sharp.

share|improve this answer
1  
1. To say the same thing in different words: consider all the sets in $\mathcal{F}$ of size at least $2$. From each such set we pick two elements, giving an unordered pair $\{a,b\}$ of elements from $A$. All these unordered pairs must be distinct (for the sets' intersection to have size at most $1$), and there are only $\binom{n}{2}$ distinct unordered pairs possible. So $\mathcal{F}$ can have at most $\binom{n}{2}$ sets of size at least $2$. It can also have the empty set and all the $n$ singleton sets, so $\mathcal{F} \le 1 + n + \binom{n}{2}$. And we can achive this bound in an obvious way. –  ShreevatsaR Dec 6 '12 at 19:38

Fix $m\in\Bbb N$ with $m\le n$. If $\mathscr{F}\subseteq\wp(A)$ has the property that $|X\cap Y|<m$ for distinct $X,Y\in\mathscr{F}$, then $$|\mathscr{F}|\le\sum_{k=0}^m\binom{n}m\;.$$

Proof. Let $\mathscr{F}'=\{F\in\mathscr{F}:|F|\ge m\}$. For each $M\in[A]^m$ (the set of $m$-element subsets of $A$) let $\mathscr{F}_M=\{F\in\mathscr{F}:M\subseteq F\}$. Clearly $|\mathscr{F}_M|\le 1$ for each $M\in[A]^m$, so $\left|\mathscr{F}'\right|\le\left|[A]^m\right|=\binom{n}m$, and therefore $$|\mathscr{F}|\le\sum_{k=0}^m\binom{n}m\;.$$ On the other hand, $[A]^{\le m}$ is such a collection, and $$\left|[A]^{\le2}\right|=\sum_{k=0}^m\binom{n}m\;,$$ so the bound is sharp.

share|improve this answer
    
I see that @hardmath has already done essentially the same thing for the specific case asked about. –  Brian M. Scott Dec 6 '12 at 19:19
    
+1 for generality. I was posting from my smartphone as an extra degree of difficulty! Then, driving home I began to worry that I'd misunderstood the question... –  hardmath Dec 6 '12 at 19:37
    
@hardmath: You and Asaf! That certainly explains why it seemed unusually concise for you. I’m always impressed when folks manage to make useful posts by phone. –  Brian M. Scott Dec 6 '12 at 19:49

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.