# An upper bound on families of subsets with a small pairwise intersection

Given integers $n,r,s$, we can define $M(n,r,s)$ to be the maximal size of a family $F$ of $r$-subsets of $\{1,...,n\}$ such that the pairwise intersection between any two subsets is at most $s$. Is there any way to get a (non-trivial) upper bound on $M(n,r,s)$?

If we want the intersections to be at least $s$ (instead of at most $s$), we have a generalization of the Erdos-Ko-Rado problem, and this question has been asked before on this site.

I am chiefly interested in the case where $r$ is linear in $n$ and $s=\frac{r}{2}$.

• See my answer to this earlier MO question: mathoverflow.net/questions/161159/… . In particular, the paper by Frankl that I linked discusses general such problems, and Theorem 4.3 there (by Deza, Erdos and Frankl) would give non-trivial bounds in your question. – Lucia Jul 12 '14 at 20:45
• Actually, as noted in my earlier answer the upper bound $\binom{n}{s+1}/\binom{r}{s+1}$ is easy to obtain. I don't know if this is enough, or if you're looking for stronger bounds. Non-trivial can be vague! – Lucia Jul 12 '14 at 20:56

The maximum size is attained by a Steiner system $S(t+1,r,n)$ when it exists. It consists of $\binom{n}{t+1}/\binom{r}{t+1}$ blocks.