Question

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.

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.