Let's consider the following setup.

I have access to $N$ objects. Thanks to these objects, I can build up sub-packets containing $k$ such objects. I know that there exists a total of $\displaystyle N\choose{\displaystyle k}$ different sub-packets.

Among these different sub-packets, I want to pick $n$ of them, so that I would have at my disposal a total of $n$ sub-packets of $k$ elements drawn from my ensemble of $N$ objects. However, I don't want to pick these $n$ sub-packets in a random way. Indeed, I want to choose them so as to minimize the maximum number of common elements between any two different sub-packets from my choice of $n$ sub-packets.

A simple example is the case $k = 1$ and $n < N$, where you can of course choose the sub-packets so as to be all disjoint one with another.

How could I proceed ? What is the value of this minimum as a function of $N$, $k$ and $n$ ?

As a conclusion, my practical case of application is given by the case $$ \begin{cases} N = 500 \, , \\ k = 32 \, , \\ n = 32 \, . \end{cases}$$ For this case, what is the value of this mininum ? How should I proceed to reach it ?

  • $\begingroup$ How many times do you count every repeating element? Do you count it with respect to multiplicity of sets containing it or just once? $\endgroup$ – Lada Dudnikova May 5 at 8:53
  • $\begingroup$ @LadaDudnikova I am not sure I have correctly understood your question, but let me try to rephrase my goal. For given values of ${N,k,n}$, I want to minimise the value of the number of common elements between $A$ and $B$, where ${ (A,B) }$ runs over all the pairs of subsets. Does this make sense? $\endgroup$ – jibe May 9 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.