MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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}$.

share|cite|improve this question
See my answer to this earlier MO question:… . 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
Thanks, That's great! – Zur Luria Jul 12 '14 at 21:32
up vote 1 down vote accepted

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.


share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.