Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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

2 Answers 2

up vote 2 down vote accepted

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

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.