5. Random matrix theory

Ramanujan graphs
Problem 5.1.
Let $G$ be ChungLu with power law degree distribution. Is $G$ “Ramanujan”? More precisely, we expect that the nonbacktracking operator $B$ has one eigenvalue $\tilde d$ and all other eigenvalues contained in the disk (in the complex plane) centered at the origin with radius $\sqrt{\tilde d}$. Here $$\tilde d = \frac{\sum_v d_v^2}{\sum_v d_v}  1$$ where $d_v$ is the degree of vertex $v$. This is related to studying the following SDP: $\max \sum_{(u,v) \in E} \langle x_u,x_v \rangle$ subject to $\x_v\^2 = 1$ and $\\sum_v x_v\^2 = 0$. 
Nonbacktracking operator
Problem 5.2.
[Laurent Massoulié] Take the SBM with $k$ communities of equal size. Take a random secondlargest eigenvector $e_2 \in \mathbb{R}^{2E}$ of the nonbacktracking operator $B$. Pass to a vector $x \in \mathbb{R}^V$. Use this to recover a coloring correlated with the truth. 
2lift of Ramanujan graph
Problem 5.3.
[Nikhil Srivastava] Is a random 2lift of a Ramanujan graph also Ramanujan (or nearly) with constant probability? More precisely, let $G$ be a $d$regular Ramanujan graph with adjacency matrix $A$. Construct the matrix $S$ by $$S_{ij} = \left\{\begin{array}{cl} 0 & \text{if } A_{ij} = 0 \\ \text{randomly } \pm 1 & \text{if } A_{ij} = 1. \end{array}\right.$$ Is the spectral norm of $S$ less than $2\sqrt{d1} + \epsilon$ with constant probability? 
AlonBoppana for nonregular graphs
Problem 5.4.
[Laurent Massoulié] A proposed definition of Ramanujan for nonregular graphs is that the nonbacktracking matrix $B$ has spectrum satisfying $$\mathrm{Sp}(B) \subseteq \{\rho e^{i \theta}, \theta \in [0,2\pi]\} \cup \mathcal{B}(0,\sqrt{\rho}).$$ For this definition, prove the result analagous to AlonBoppana. Namely, for $\rho$ fixed and $n \to \infty$, show that every graph with $\lambda_1(B) = \rho$ satisfies $\lambda_2(B) \ge \sqrt{\rho}  o(1)$. 
Construction of nonregular Ramanujan graphs
Problem 5.5.
What are some constructions of nonregular Ramanujan graphs (using the definition of Ramanujan from the previous problem)?
Cite this as: AimPL: Connecting communities via the block model, available at http://aimpl.org/blockmodel.