Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
    
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 at 20:45
2  
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 at 20:56
    
Thanks, That's great! –  Zur Luria Jul 12 at 21:32

1 Answer 1

up vote 0 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.

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

share|improve this answer

Your Answer

 
discard

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.