# Maximum number of size $k$ subsets where no two overlap on more than $e$ elements.

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.

• 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. – 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.