  The largest eigenvalue of a matrix is always larger or equal than its largest
diagonal entry. We show that for a large class of random Laplacian matrices,
this bound is essentially tight: the largest eigenvalue is, up to lower order
terms, often the size of the largest diagonal entry.
  Besides being a simple tool to obtain precise estimates on the largest
eigenvalue of a large class of random Laplacian matrices, our main result
settles a number of open problems related to the tightness of certain convex
relaxation-based algorithms. It easily implies the optimality of the
semidefinite relaxation approaches to problems such as $\mathbb{Z}_2$
Synchronization and Stochastic Block Model recovery. Interestingly, this result
readily implies the connectivity threshold for Erd\H{o}s-R\'{e}nyi graphs and
suggests that these three phenomena are manifestations of the same underlying
principle. The main tool is a recent estimate on the spectral norm of matrices
with independent entries by van Handel and the author.
