# 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?

-

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

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 21, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9221752285957336, "perplexity_flag": "head"}