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

1. Problems

    1. Second Eigenvalue Multiplicity


      Add remark

      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 [JTYZZ21], with an improvement in the case of regular graphs provided by [MRS21] and also for the normalized adjacency matrix of general bounded degree graphs. Constructions of graphs establishing lower bounds were given by [HSZZ21].
      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)$.


        • Add remark

          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.

              Add remark

              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 [LP16] 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


                  Add remark

                  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.