generalizing ball-bin problem to k-universal family
Let $B_j$ be the number of balls in the $j$'th bin. Then
$$
\mathbb{E}\left[\sum_{j=1}^n \binom{B_j}{k}\right] =
\sum_{i_1 &lt; \cdots &lt; i_k} \Pr[h(i_1) = \cdots = h(i_k)] =
\frac{\binom{n}{k}}{n^{k-1}} \leq \frac{n}{k!}.
$$
Let $C_j = B_j - (k-1)$. Then
$$
\mathbb{E}\left[\sum_{j=1}^n C_j^k\right] \leq k! \mathbb{E}\left[\sum_{j=1}^n \binom{B_j}{k}\right] \leq n,
$$
and so with probability at least $1/2$,
$$
\max_j C_j^k \leq \sum_{j=1}^n C_j^k \leq 2n,
$$
hence $C_j \leq (2n)^{1/k}$, implying that $l_{\max} \leq (2n)^{1/k} + k-1$.