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

Question

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.

Answer 1

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.