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?

  • $\begingroup$ 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. $\endgroup$
    – joriki
    Dec 6 '12 at 17:42
  • $\begingroup$ 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? $\endgroup$
    – hardmath
    Dec 6 '12 at 17:59
  • $\begingroup$ @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. $\endgroup$ Dec 6 '12 at 18:23
  • $\begingroup$ @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! $\endgroup$
    – mathnoob
    Dec 8 '12 at 13:00

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.

  • 2
    $\begingroup$ 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. $\endgroup$ 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}k\;.$$

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}k\;.$$ On the other hand, $[A]^{\le m}$ is such a collection, and $$\left|[A]^{\le m}\right|=\sum_{k=0}^m\binom{n}k\;,$$ so the bound is sharp.

  • $\begingroup$ I see that @hardmath has already done essentially the same thing for the specific case asked about. $\endgroup$ Dec 6 '12 at 19:19
  • $\begingroup$ +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... $\endgroup$
    – hardmath
    Dec 6 '12 at 19:37
  • $\begingroup$ @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. $\endgroup$ Dec 6 '12 at 19:49
  • $\begingroup$ I'm pretty sure that $m$ should be changed to $k$ in the first and last two instances of $\binom{n}m$ (since otherwise, the summation could just be simplified to multiplication by $(m+1)$!) $\endgroup$ Nov 21 '15 at 16:56
  • $\begingroup$ @j_random_hacker: You’re absolutely right, and there was another typo as well. Thanks. $\endgroup$ Nov 21 '15 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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