Partition counting problem with cap on pairwise intersection

177 Views Asked by At

Fix $T_1,\ldots T_m$ as pair-wise disjoint $k$-subsets of $\{1,2,\ldots,m\cdot k\}$, so that $|T_i|=k$ and $|T_i\cap T_\ell|=0$. For any $j\le k$, how many sets of the form $\{C_1,\ldots,C_m\}$ are there such that each $C_i\subset\{1,2,\ldots,m\cdot k\}$, $|C_i|=k$, $|C_i\cap C_\ell|=0$, and $\max_{i,\ell} |C_i\cap T_\ell| = j$? Call this number $v_j$, and the cumulative sum where $\max_{i,\ell} |C_i\cap T_\ell| \le j$ instead $V_j$.

I'm interested in an exact solution or just asymptotic bounds for either $v_j$ or $V_j$.

If you remove the constraint $\max_{i,\ell} |C_i\cap T_\ell| = j$, which is $V_k$, then there are just $$V_k = \frac{(m\cdot k)!}{(k!)^m m!}$$ ways: There are $(m\cdot k)!$ ways of placing the $mk$ elements of $\{C_1,\ldots,C_m\}$ onto the positions $1,\ldots,mk$. This overcounts by $k!$ for each of the $C_i$'s and then $m!$ for the order of the $C_i$'s.

Using Chernoff bounds, I believe it is possible to show that for $j>k/m$, $$ V_k \ge V_j \ge V_k\left(1-k^2 e^{\frac{-2(j-\frac{k}{m})^2}{k}}\right),$$ by counting sets that overlap as well. Are these bounds asymptotically tight?