# Choosing subsets of a set with a specified amount of maximum overlap between them

How can I determine the size of the largest collection of k-element subsets of an n-element set such that each pair of subsets has at most m elements in common?

-
The question is slightly confusing: I believe you mean something like "what is the largest collection of k-element subsets of an n-element set such that each pair of subsets has at most m elements in common?" but I might be wrong. – Qiaochu Yuan Aug 10 '10 at 21:54
Yes, that's exactly what I meant! Thanks! – Paul Reiners Aug 10 '10 at 21:57

I think this problem is still open, but the following might be useful:

Ray-Chaudhuri-Wilson Theorem:

Let $L$ be a set of $m$ integers and $F$ be an $L$-intersecting $k$-uniform family of subsets of a set of $n$ elements, where $m \le k$, then

$|F| \le {n \choose m}$

$\bullet$

$k$-uniform family is a set of subsets, each subset being of size k.

An $L$-intersecting family is such that the intersection size of any two distinct sets in the family is in $L$.

The following result of Frankl gives us a lower bound

Frankl's Result:

For every $k \ge m \ge 1$ and $n \ge 2k^{2}$ there exists a $k$-uniform family $F$ of size $> (\frac{n}{2k})^{m}$ on $n$ points such that $|A \cap B| \le m-1$ for any two distinct sets $A,B \in F$.

$\bullet$

For an algorithm for constructing such sets (based on Frankl's result) refer: http://stackoverflow.com/questions/2955318/creating-combinations-that-have-no-more-one-intersecting-element/2955527#2955527

-