Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

When considering something completely different yesterday I came across the following problem:

Let $X = \{ 1,2,3,...,n\}$. What is the maximal number of subsets of $X$ of order $m$ one can choose such that any two chosen subsets have at most $k$ elements in common?

If we call this number $F(n,m,k)$, it is quite easy to calculate $F$ for some low values of $n$,$m$ and $k$, such as:

  • $F(3,3,1) = 1$
  • $F(4,3,1) = 1$
  • $F(5,3,1) = 2$
  • $F(6,3,1) = 3$
  • $F(7,3,1) = 6$

and also $F(n,n,k)=1$, but I cannot seem to find anything general at all. Am I missing something trivial?

share|improve this question
3  
Sounds like a binary constant-weight code of length $n$, constant weight $m$ and minimum Hamming distance $2(m-k)$. In general the answer is unknown. Some general bounds (e.g. the Johnson bound) are known. The wikipedia page has links to tables of best known upper and lower bounds for small values of $n, m, 2(m-k)$. –  Jyrki Lahtonen Nov 26 '12 at 14:41
    
Thanks! :) I'll read that –  malin Nov 26 '12 at 16:57
2  
Lycka till, Malin! MacWilliams-Sloane is a more comprehensive source, but may you don't want to delve into that? It does explain the Johnson bound, which is a decent general bound. –  Jyrki Lahtonen Nov 26 '12 at 18:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.