Loading Web-Font TeX/Math/Italic
| Register
\newcommand{\Cat}{{\rm Cat}} \newcommand{\A}{\mathcal A} \newcommand{\freestar}{ \framebox[7pt]{$\star$} }

1. Problems

    1. Second Eigenvalue Multiplicity

      Problem 1.1.

      Let G be a graph with maximum degree bounded by \Delta. For the following choices of Hermitian matrix M_G associated with G, what is the maximum multiplicity of the second largest eigenvalue of M_G? For the following choices of Hermitian matrix M_G associated with G, what is the maximum multiplicity of the second largest eigenvalue of M_G?
      1. The adjacency matrix: in this case a sublinear upper bound was proved by [1], with an improvement in the case of regular graphs provided by [undefined] and also for the normalized adjacency matrix of general bounded degree graphs. Constructions of graphs establishing lower bounds were given by [undefined].
      2. The Laplacian matrix.
      3. Schrödinger operators: any matrix of the form D+A_G where A_G is the adjacency matrix and D is an arbitrary diagonal matrix.
      4. Weighted adjacency matrices: any Hermitian matrix M_G such that M_G[i,j] = 0 if \{i,j\}\notin E(G).
        • Problem 1.2.

          For a fixed choice of parameters \rho and \Delta, what is the largest possible multiplicity of the second eigenvalue of the adjacency matrix A_G with the constraint that \lambda_2(A_G) = \rho.
            • Nonbacktracking Matrix

                  Basic questions about the eigenvalues and eigenvectors of the nonbacktracking matrix of irregular graphs remain open.

              Problem 1.3.

              Let G be any graph on n vertices and m edges, and let B_G denote the nonbacktracking matrix of G, which is a 2m\times 2m matrix whose rows and columns are indexed by directed edges of G, defined as follows: B_G[uv, xy] = \begin{cases} 1 & \text{if $v = x$, $u\ne y$} \\ 0 &\text{otherwise}. \end{cases}
              1. It was proved by [undefined] that if G is a regular graph, then every Jordan block of B_G has size at most 2. Prove upper and lower bounds on the function: f(n) := \max_{\substack{G~\text{$n$-vertex graph} \\ \text{with no leaves}}} \max_{S~\text{Jordan block of $B_G$}} |S|.
                Is f(n) bounded by a constant or is it growing with n? If f(n) is indeed growing with n, as a weak step towards proving a bound, can we show that it is sublinear in n?
              2. Prove an Alon–Boppana bound for B_G. Concretely, show that: |\lambda|_2(B_G) \ge \sqrt{\rho(B_G)} - o_n(1)
                where \rho(B_G) is the spectral radius of B_G.
                • Positive and negative \ell_2-mass on spectrum

                  Problem 1.4.

                  Let G be a connected graph and let \lambda_1\ge\dots\ge\lambda_s\ge 0>\lambda_{s+1}\ge\dots\ge\lambda_n be the eigenvalues of the adjacency matrix of G. Defining: \begin{align*} S^+(G) &:=\sum_{i=1}^s \lambda_i^2\\ S^-(G) &:= \sum_{i=s+1}^n \lambda_i^2. \end{align*}
                  Some conjectures and questions of interest are the following.
                  1. Prove that \min\{S^+(G), S^-(G)\} \ge n-1.
                  2. Denoting E(\overline{G}) = \{e_1,\dots,e_{\ell}\}, and defining G_i:= G\cup\{e_1,\dots,e_i\}, prove that S^+(G_i) is a monotonically increasing sequence, and that S^-(G_i) is a unimodal sequence. Note that this would imply the first statement by choosing G' as a tree, and the sequence e_1,\dots,e_{\ell} so that some G'_i=G.
                  3. For any r\ge 1, is \sum_{t=1}^r \lambda_t(G_i)^2 monotonically increasing?
                  4. Given some threshold \tau, is \sum_{t:\lambda_t\ge\tau} \lambda_t(G_i)^2 monotonically increasing?

                      Cite this as: AimPL: Spectral graph and hypergraph theory: connections and applications, available at http://aimpl.org/spectralhypergraph.