
## 5. Random matrix theory

1. ### Ramanujan graphs

#### Problem 5.1.

Let $G$ be Chung-Lu with power law degree distribution. Is $G$ “Ramanujan”? More precisely, we expect that the non-backtracking 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$.
• ### Non-backtracking operator

#### Problem 5.2.

[Laurent Massoulié] Take the SBM with $k$ communities of equal size. Take a random second-largest eigenvector $e_2 \in \mathbb{R}^{2E}$ of the non-backtracking operator $B$. Pass to a vector $x \in \mathbb{R}^V$. Use this to recover a coloring correlated with the truth.
• ### 2-lift of Ramanujan graph

#### Problem 5.3.

[Nikhil Srivastava] Is a random 2-lift 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{d-1} + \epsilon$ with constant probability?
• ### Alon-Boppana for non-regular graphs

#### Problem 5.4.

[Laurent Massoulié] A proposed definition of Ramanujan for non-regular graphs is that the non-backtracking 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 Alon-Boppana. 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 non-regular Ramanujan graphs

#### Problem 5.5.

What are some constructions of non-regular 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.