1. Problems
-
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?- 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].
- The Laplacian matrix.
- 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.
- 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}- 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?
- 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.
- 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|.
-
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.- Prove that \min\{S^+(G), S^-(G)\} \ge n-1.
- 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.
- For any r\ge 1, is \sum_{t=1}^r \lambda_t(G_i)^2 monotonically increasing?
- 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.