most recent 30 from http://mathoverflow.net 2013-05-22T15:38:09Z http://mathoverflow.net/feeds/question/103557 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/103557/how-many-combinations-exist-of-m-items-from-a-set-of-m-items-such-that-each Alex Beutel 2012-07-30T22:40:35Z 2012-07-31T01:48:52Z

<p>I apologize if this has been answered before.</p> <p>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$)?</p> <p>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. </p> <p>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$?</p> <p>Thanks.</p>

http://mathoverflow.net/questions/103557/how-many-combinations-exist-of-m-items-from-a-set-of-m-items-such-that-each/103574#103574 Chris Godsil 2012-07-31T01:48:52Z 2012-07-31T01:48:52Z

<p>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 <a href="http://www.math.uni-bielefeld.de/ahlswede/homepage/public/122.pdf" rel="nofollow">http://www.math.uni-bielefeld.de/ahlswede/homepage/public/122.pdf</a></p> <p>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. </p>