Upper bound for the size of a maximal collection of subsets which, pairwise, have at most one common element

Question

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?

Answer 1

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.

Answer 2

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.