6
$\begingroup$

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?

$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$ Aug 10, 2010 at 21:54
  • $\begingroup$ Yes, that's exactly what I meant! Thanks! $\endgroup$ Aug 10, 2010 at 21:57

2 Answers 2

5
$\begingroup$

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: https://stackoverflow.com/questions/2955318/creating-combinations-that-have-no-more-one-intersecting-element/2955527#2955527

$\endgroup$
1
  • $\begingroup$ Do you happen to have a source for Frenkl's result? $\endgroup$ Jul 30, 2021 at 6:02
0
$\begingroup$

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: https://mathoverflow.net/questions/25067/given-n-k-element-subsets-of-n-is-there-a-small-subset-a-of-n-which-intersects-t

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.