Let $S_1,\dots,S_m \subseteq \{1,2,\dots,n\}$ be a collection of sets, each of size $k$. I'll say that they are almost-disjoint if, for every $i,j$ with $i\ne j$, we have $|S_i \cap S_j| \le 1$, i.e., each pair of sets has at most one element in common.
Is there an asymptotic upper-bound on the largest possible value of $m$, as a function of $n,k$, for any almost-disjoint collection of sets?
In particular, suppose $k=n^c$, for some $0 \le c \le 1$. Can I upper-bound $m$ as $m=O(n^{f(c)})$, for some function $f$? What's the best upper bound known?
If I replace "almost-disjoint" with "disjoint", the problem becomes an easy application of the pigeonhole principle; we find $m = O(n^{1-c})$. However, I don't know how to deal with the generalization to almost-disjoint collections. Is there some generalization of the pigeonhole principle that is applicable here? This question arose in the analysis of an algorithm I was thinking about. I wondered if it might be related to some kind of combinatorial design but I couldn't match it to any existing concept I know of.
We can use the projective plane over a finite field to construct an almost-disjoint collection of sets with $k=\Theta(n^{1/2})$ and $m=\Theta(n)$. That gives a lower bound. I'm hoping to get an upper bound on $m$ that is better than $m = O(n)$, so this implies I need to restrict attention to the case $c>1/2$.
$\quad$No there is not a really an upper bound in some cases. Take k=1, then to share at most 1 in common is trivial, there would be infinitely many 1 element sets, for any n value. With k=2, you can think of connecting distinct pairs of vertices of a regular n-gon. How many pairs are there ? $T_{n-1}$ where T stands for the set of triangular numbers.
$\quad$I suggest looking at the fact, that there are at least k-1 elements, the sets can't have in common. How many disjoint sets of size k-1 are there ? There can be at most, one set, with this as it's elements it doesn't share in our collection. So the upper bound is technically there, but hits infinity when $0<k\le\text{bound}$.