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
    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.2012-12-06
  • 0
    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?2012-12-06
  • 0
    @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.2012-12-06
  • 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
    I see that @hardmath has already done essentially the same thing for the specific case asked about.2012-12-06
  • 0
    +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...2012-12-06
  • 0
    @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.2012-12-06
  • 0
    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)$!)2015-11-21
  • 0
    @j_random_hacker: You’re absolutely right, and there was another typo as well. Thanks.2015-11-21