4
$\begingroup$

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?

  • 0
    @malin, I think if you fix $k=1$ you have another related problem: https://math.stackexchange.com/questions/442043/covering-with-most-possible-equal-size-subsets-having-pairwise-singleton-interse.2017-08-12

0 Answers 0