Throw $n$ balls into $n$ bins and let $X_n$ be the maximum occupancy. That is the maximum number of balls found in any bin.
If you throw the balls uniformly and independently it is known that $\mathbb{E}(X_n) = \Theta(\log{n}/\log{\log{n}})$. If the process is merely pairwise independent (but still uniform) then it is known that $\mathbb{E}(X_n)$ can grow as quickly as $\Theta(\sqrt{n})$.
If the random process is $k$-wise independent, then for each $k$ there will be some tight asymptotic upper bound for $\mathbb{E}(X_n)$.
How do the asymptotics of a tight upper bound for $\mathbb{E}(X_n)$ depend on $k$?
This question may be hard to answer precisely but approximate answers and even conjectures would be very helpful too. Sometimes $k=4$ is a transition point as you can then use more powerful moment methods but I am not sure how to do that usefully here.
What are the asymptotics for a tight upper bound for $\mathbb{E}(X_n)$ when $k=4$?
Best Answer
I think https://arxiv.org/abs/1502.05729 might be at least a partial answer to my question. It shows "a $k$-independent family of functions that imply [heaviest loaded bin] size is $\Omega(n^{1/k})$".