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?
Tell me more
×
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.
|
|
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 |
||||
|
|
|
Hi Please refer this link: http://gilkalai.wordpress.com/2008/10/06/extremal-combinatorics-iv-shifting/ You can also look here as well to get more idea for this type of problems: http://mathoverflow.net/questions/25067/given-n-k-element-subsets-of-n-is-there-a-small-subset-a-of-n-which-intersects-t |
|||
|
|
