As the title suggests:

What is the maximum number of size $k$ subsets of $[1, \dots, n]$ such that no subsets overlap on more than $e$ elements?

I only really care about the asymptotics, so an answer that is correct up to constant factors is fine.

  • $\begingroup$ See this Answer to a previous Question by @BrianMScott, where no two sets overlap in more than $m$ elements. However that Question does not restrict the size of subsets, so it gives an upper bound to your problem. $\endgroup$ – hardmath Apr 29 '15 at 4:20

For $k \le e$, all possible subsets qualify, ${n \choose k}$

For $k = e+1$, all possible subsets again qualify because the sets are distinct so share at most $e$ elements, ${n \choose e+1}$

For $e+1< k \le \frac{n+e}{2}$, each subset uses a number of the $e+1$ cases, so the total is lower by at least that factor:

$$|\text{subsets}| \le \left\lfloor \frac{n \choose e+1}{k\choose e+1} \right\rfloor = \left\lfloor \frac{n!(e+1)!(k-e-1)!}{(e+1)!(n-e-1)!k!} \right\rfloor = \left\lfloor \frac{n!(k-e-1)!}{(n-e-1)!k!} \right\rfloor$$

For $k \gt \frac{n+e}{2}$, any two subsets will share more than $e$ elements so only $1$ such subset may be chosen.

  • $\begingroup$ Comments to improve the evaluation / limit in the "interesting" zone welcome. $\endgroup$ – Joffan Apr 29 '15 at 13:07

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.