| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

5. Random matrix theory

    1. Ramanujan graphs


      Add remark

      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


          Add remark

          Problem 5.2.

          [Laurent Massoulié] 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


              Add remark

              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


                  Add remark

                  Problem 5.4.

                  [Laurent Massoulié] 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


                      Add remark

                      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.