How many combinations exist of \$M'\$ items from a set of \$M\$ items such that each combination is not similar at more than \$m\$ elements? - MathOverflow 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 How many combinations exist of \$M'\$ items from a set of \$M\$ items such that each combination is not similar at more than \$m\$ elements? 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 Answer by Chris Godsil for How many combinations exist of \$M'\$ items from a set of \$M\$ items such that each combination is not similar at more than \$m\$ elements? 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>