0
$\begingroup$

I apologize if this has been answered before.

I would like to know how many ways there are to choose $M'$ elements from a set of $M$ elements such that any two sets selected are not similar at more than $m$ elements (for $M \geq M' \geq m$)?

For example, let's say $M=12$, $M'=4$ and $m = 3$. We take example elements: {A B C D E F G H I J K L}. Then {A B C D}, {A B E F}, {A C F G} are valid selections together, but we could not add {A B E G} as this would overlap with the second set on A, B, and E.

This may be related to coding theory. If I remember my coding theory correctly, I believe this question would be stated as how many block codes exist of length $M$ with weight $M'$ such that the minimum distance is $m$?

Thanks.

$\endgroup$
1
  • $\begingroup$ Yes, it is a basic question in coding theory. $\endgroup$ Jul 31, 2012 at 1:05

1 Answer 1

1
$\begingroup$

Suppose you have a collection $S$ of subsets of size $k$ from a set $\Omega$ of size $n$, such that no two distinct $k$-subsets have more than $m$ elements in common. Then the complements of the sets in $S$ are a collection of $(n-k)$-subsets of an $n$-element set, such that any two have at least $t=n-2k$ elements in common. Thus they form a $t$-intersecting family of subsets of $\Omega$. Ahlswede and Khachatrian have determined the maximum size of a $t$-intersecting family of subsets, for all possible values of $n$, $k$ and $t$. This is the so-called complete intersection theorem, and is the strongest possible form of the Erdos-Ko-Rado theorem. For details see their paper at http://www.math.uni-bielefeld.de/ahlswede/homepage/public/122.pdf

To oversimplify their result, the maximal family always consists of all $k$-subsets of $\Omega$ that meet a chosen subset of size $t+2i$ in at most $t+i$ points.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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