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

Improve this question
$\endgroup$
2
  • $\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
    Commented Jul 12, 2014 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
    Commented Jul 12, 2014 at 20:56

1 Answer 1

Reset to default
5
$\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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .