Given 3 parameters $s, r$ and $t$, where $r \leq t$, I want to construct $t$ sets such that each integer $\{1, \ldots, s\}$ appears in exactly $r$ of these sets. The question is:
Is it possible to construct these sets such that the size of the maximum pairwise intersection between any two $t_i, t_j$ is $k$? Is this question $\mathsf{NP}$-complete? Or equivalently, is minimizing the maximum pairwise intersection between the sets $\mathsf{NP}$-hard?
There is a lower bound on the max pairwise intersection given by ceiling(number of identical value pairs / number of set pairs), meaning $\lceil (s \cdot {r \choose 2}) / {t \choose 2} \rceil$.
The problem seems related to, but slightly different from, the block design problem. In the block design problem, there is a parameter $\lambda$ that dictates in how many of the $t$ sets each pair of integers in $\{1, \ldots, s\}$ must appear, so if $\lambda$ is 1, the maximum pairwise intersection between sets is 1 (since each pair of values appears in at most 1 set together). I've seen claims that deciding the existence of a block design is $\mathsf{NP}$-complete, but no actual proof - would also appreciate any link to such a proof.
