2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Lucia Jul 12 '14 at 20:45
  • 2
    $\begingroup$ 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! $\endgroup$ – Lucia Jul 12 '14 at 20:56
1
$\begingroup$

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.

See http://en.wikipedia.org/wiki/Steiner_system

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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