Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Yes, it is a basic question in coding theory. –  Brendan McKay Jul 31 '12 at 1:05
add comment

1 Answer 1

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.

share|improve this answer
add comment

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.