Inspired by this question, I was wondering about the following problem:
Consider all $n\times n$ $(0,1)$-matrices with $k$ ones. Which of these matrices has the largest operator norm? And how does this largest possible operator norm behave with $n$ and $k$?
If any progress has already been made on this problem, I assume it's in the guise of directed graphs. For the case of symmetric matrices with zero diagonal, which graphs give the largest possible largest eigenvalue? $(k/n)$-regular graphs?