Some Questions — Question 16

Definitions and mathematical statement

Let $G$ be a finite simple $d$-regular graph on $N$ vertices, where $d\geq2$ is fixed. Its adjacency matrix $A_G$ is real symmetric, with eigenvalues $\lambda_1,\ldots,\lambda_N$ counted with algebraic multiplicity. Define its empirical spectral distribution by \[ \mu_G=\frac1N\sum_{i=1}^N\delta_{\lambda_i}. \] Determine which probability measures can occur in this way, and find effective natural restrictions on these distributions. A related limiting formulation asks which measures are weak limits of such $\mu_G$ as $N$ tends to infinity; weak convergence means convergence of integrals against every continuous function on $[-d,d]$.

Every exact distribution is a finitely supported measure with rational atom weights, is supported in $[-d,d]$, and satisfies \[ \int t\,d\mu_G(t)=0,\qquad \int t^2\,d\mu_G(t)=d. \] More generally, $N\int t^k\,d\mu_G(t)=\operatorname{tr}(A_G^k)$ counts closed walks of length $k$. These elementary constraints illustrate the kind of restrictions sought; they are not asserted to characterize all possible distributions.

Connectedness is not required in the source, so disjoint unions are permitted. Exact realizability and weak-limit realizability should be distinguished: limits need not be atomic, and the single eigenvalue $d$ in a connected graph can have vanishing normalized mass. A characterization must account for regular-graph structure beyond the usual conditions on arbitrary symmetric matrices.

Short English statement

What intrinsic restrictions characterize eigenvalue distributions of finite regular graphs and their limits?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 1200016 (AMR-011-0016), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Abert - Some questions (pdf) (2010), Question 16. Original source indexed by AMR-011-0016. https://www.renyi.hu/~abert/questions.pdf.