4
$\begingroup$

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?

  • 0
    @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!2012-12-08

2 Answers 2

4

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
    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.2012-12-06
3

Fix $m\in\Bbb N$ with $m\le n$. If $\mathscr{F}\subseteq\wp(A)$ has the property that $|X\cap Y| 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.

  • 0
    @j_random_hacker: You’re absolutely right, and there was another typo as well. Thanks.2015-11-21