Delocalized eigenvectors of transitive graphs and beyond

Basic Information

• Paper ID: 2407.12384
• Title: Delocalized eigenvectors of transitive graphs and beyond
• Authors: Nicolas Burq, Cyril Letrouit
• Classification: math.SP (Spectral Theory)
• Publication Date: October 15, 2025 (arXiv version v2)
• Paper Link: https://arxiv.org/abs/2407.12384

Abstract

This paper establishes delocalization properties of eigenvectors in vertex-transitive graphs through fundamental estimates of spectral projection operators, thereby recovering known results previously established through representation-theoretic arguments. Similar techniques demonstrate that for general symmetric matrices, most approximate eigenvectors spectrally localized within a given window containing sufficiently many eigenvalues are delocalized in the $L^q$ norm sense. Based on this observation, the authors prove delocalization results for approximate eigenvectors of large graphs with few short cycles, relying on assumptions about the resolvent that are verified in standard cases such as random lifts of fixed base graphs.

Research Background and Motivation

Research Questions

This paper investigates the spatial delocalization of eigenvectors of the adjacency matrix of graphs. For the adjacency matrix $A$ of a graph $G$, the authors focus on delocalization properties of its eigenvectors in the large $n$ limit.

Significance of the Problem

1. Quantum Chaos Theory: Localization/delocalization of eigenvectors is a central problem in quantum chaos theory, closely related to quantum ergodicity
2. Random Matrix Theory: This is a fundamental problem in random matrix theory, crucial for understanding statistical properties of complex systems
3. Graph Theory Applications: Widely applicable in network science, combinatorial optimization, and related fields

Limitations of Existing Methods

1. Complexity of Representation Theory: Previous results on delocalization of eigenvectors in Cayley graphs relied heavily on complex representation-theoretic techniques
2. Limited Applicability: Existing results are primarily restricted to specific graph types (e.g., regular graphs, Erdős-Rényi graphs)
3. Exact Eigenvector Requirement: Most results apply only to exact eigenvectors rather than approximate eigenvectors

Research Motivation

The authors aim to reprove known results through more direct and fundamental methods, and extend them to more general settings, particularly for approximate eigenvectors.

Core Contributions

1. Simplified Proof Method: Provides a more direct proof of eigenvector delocalization in vertex-transitive graphs through fundamental estimates of spectral projection operators, avoiding representation theory
2. General Symmetric Matrix Results: Establishes delocalization properties of most approximate eigenvectors of general symmetric matrices in the $L^q$ norm sense
3. Extension to General Graphs: Under two key assumptions, proves delocalization results for approximate eigenvectors of large graphs with few short cycles
4. Unified Framework: Provides a unified framework for handling eigenvector delocalization in different types of graphs

Detailed Methodology

Problem Definition

Given a graph $G$ with $n$ vertices and adjacency matrix $A$, we study delocalization properties of eigenvectors $u \in \mathbb{C}^n$. Delocalization is measured by: $\alpha_q(u) = \frac{\|u\|_{L^q}}{\|u\|_{L^2}}$ for $q \in (2,+\infty]$.

Core Technique: Spectral Projection Operator Analysis

Spectral Projection Operators

For an eigenvalue set $I \subset \mathbb{R}$, define the spectral projection operator $\Pi_I$ with kernel: $\Pi_I(i,j) = \sum_{\lambda_k \in I} \psi_{\lambda_k}(i)\psi_{\lambda_k}(j)$

Key Quantity Estimates

The authors' approach is based on detailed analysis of: $\sum_{i \in [n]} \Pi_I(i,i)^{q/2} = \left\|\sum_{\lambda_k \in I} \psi_{\lambda_k}^2\right\|_{L^{q/2}}^{q/2}$

Three Main Result Categories

1. Vertex-Transitive Graphs (Theorem 1.1)

For vertex-transitive graphs, by symmetry: $\frac{\tilde{\Pi}_I(x)}{N(I)} = \frac{1}{n}$ where $\tilde{\Pi}_I(x) = \Pi_I(x,x)$ and $N(I)$ is the number of eigenvalues in $I$.

Main Result: There exists $C > 0$ such that for any $\Lambda > 0$, with probability $\geq 1 - n^{2-\log(\Lambda)}$, any eigenvector $u$ satisfies: $\|u\|_{L^\infty} \leq C\Lambda\sqrt{\frac{\log n}{n}}$

2. General Symmetric Matrices (Theorem 1.6)

For a general symmetric matrix $H$ and interval $I$, when the random linear combination $u = \sum_{\lambda_k \in I} z_k \psi_{\lambda_k}$ is uniformly distributed on the unit sphere:

Main Result: There exists a universal constant $C > 0$ such that for any $q \in [2,+\infty)$ and $\Lambda \geq 1$: $P_I\left(\|u\|_{L^q} \geq C\Lambda\sqrt{q}N(I)^{\frac{1}{q} - \frac{1}{2}}\right) \leq 4\exp\left(-\frac{1}{8}C^2\Lambda^2 qN(I)^{\frac{2}{q}}\right)$

3. Graphs with Few Short Cycles (Theorem 1.9)

Under two key assumptions:

• (BST): The number of short cycles in the graph sequence $(G_n)$ tends to zero
• (Green): Boundedness assumption on Green's function for restricted rooted trees

Main Result: Under appropriate conditions, most approximate eigenvectors achieve optimal delocalization: $P_I\left(\|u\|_{L^q} \geq \Lambda C'n^{\frac{1}{q} - \frac{1}{2}}\right) \leq \Lambda^{-q}$

Technical Innovations

1. Avoidance of Representation Theory: Direct spectral projection operator estimates eliminate the need for complex representation-theoretic tools
2. Unified Approach: The same set of techniques applies to different types of graphs and matrices
3. Approximate Eigenvectors: Extension to approximate eigenvectors, which is more meaningful in practical applications
4. Probabilistic Methods: Utilizes measure concentration phenomena on the sphere

Experimental Setup

Theoretical Verification

This is primarily a theoretical work verified through rigorous mathematical proofs. Main verifications include:

1. Recovery of Known Results: Validates previous representation-theoretic results for Cayley graphs
2. Proof of New Results: Demonstrates method effectiveness through constructive proofs
3. Application Examples: Verifies theoretical predictions on random lift graphs

Specific Application Cases

The authors particularly analyze:

• Cayley Graphs: Validates results for Cayley graphs on quasi-random groups
• Random Lifts: Proves that random $n$-lifts of fixed base graphs satisfy required assumptions
• Product Graphs: Extends to graph products

Experimental Results

Main Theoretical Results

Optimal Bounds for Vertex-Transitive Graphs

For vertex-transitive graphs, the following bounds are proven:

• $L^\infty$ bound: $\|u\|_{L^\infty} \leq C\Lambda(\log n/n)^{1/2}$
• $L^q$ bound: $\|u\|_{L^q} \leq C\Lambda\sqrt{q}n^{1/q - 1/2}$

These bounds are nearly optimal, as counterexamples show they cannot be further improved.

Gaussian Statistics (Theorem 1.2)

In sufficiently large eigenspaces, the statistics of random eigenvector components approach standard Gaussian distribution, with convergence rate in bounded Lipschitz distance: $P[d_{BL}(\mu, \mathcal{N}(0,1)) > \varepsilon] \leq 48\sqrt{\pi}\varepsilon^{-3/2}\exp(-c(m-1)\varepsilon^5)$

Quantum Ergodicity (Theorem 1.3)

For large multiplicities, typical eigenbases are delocalized with probability at least: $1 - M\sum_{k=1}^K m_k\left(3e^{-\frac{t\sqrt{m_k}}{8}} + e^{-\frac{m_k}{12}}\right)$

Application to Random Lifts

For random lift graphs, in the continuous spectrum part: $P_I\left(\|u\|_{L^\infty} \geq \Lambda C'(\log n)^2 n^{-1/2}\right) \leq \Lambda^{-\frac{\log n}{2\log\log n}}$

Related Work

Main Research Directions

1. Erdős-Rényi and Regular Graphs: Work by Bauerschmidt et al., Erdős et al. established strong delocalization results
2. Wigner and Lévy Matrices: Research by Erdős et al., Bordenave-Guionnet, and others
3. Cayley Graphs: Representation-theoretic methods by Sah-Sawhney-Zhao, Magee-Thomas-Zhao
4. Non-homogeneous Graphs: Quantum ergodicity work by Anantharaman-Sabri and others

Advantages of This Work

1. Method Simplification: Avoids complex representation-theoretic tools
2. Expanded Applicability: Extends from exact eigenvectors to approximate eigenvectors
3. Unified Framework: Provides unified approach for different graph types

Conclusions and Discussion

Main Conclusions

1. Eigenvector delocalization can be effectively studied through fundamental estimates of spectral projection operators
2. Most approximate eigenvectors exhibit good delocalization properties
3. Under appropriate assumptions, approximate eigenvectors of general graphs can achieve optimal delocalization

Limitations

1. Exact Eigenvectors: For general graphs, the method applies only to approximate eigenvectors, providing no information about exact eigenvectors
2. Assumption Conditions: Theorem 1.9 requires relatively strong assumptions (few short cycles and bounded Green's function)
3. Probabilistic Results: Most results are probabilistic and cannot guarantee delocalization of all eigenvectors

Future Directions

1. Extension to Exact Eigenvectors: Seek methods to extend results to exact eigenvectors
2. Relaxation of Assumptions: Investigate delocalization under weaker assumptions
3. Computational Methods: Develop effective algorithms for verifying delocalization in practical computations

In-Depth Evaluation

Strengths

1. Methodological Innovation: Provides new perspective on studying eigenvector delocalization, avoiding complex representation theory
2. Theoretical Depth: Combines deep results from spectral theory, probability theory, and graph theory
3. Universality: The same set of methods applies to multiple different types of problems
4. Practical Value: Results on approximate eigenvectors are more meaningful in practical applications

Weaknesses

1. Clear Limitations: For general graphs, only approximate eigenvectors can be handled
2. Strong Assumptions: Some results require relatively strong technical assumptions
3. Insufficient Experimental Verification: Lacks numerical experiments validating theoretical predictions

Impact

1. Theoretical Contribution: Provides new tools and perspectives for eigenvector delocalization research
2. Methodological Value: Simplified proof methods may inspire research on related problems
3. Application Potential: Has potential applications in network science, quantum physics, and related fields

Applicable Scenarios

1. Large-Scale Network Analysis: Applicable to analyzing spectral properties of large-scale networks
2. Quantum System Research: Applications in quantum chaos and quantum ergodicity research
3. Random Matrix Theory: Provides new tools for studying eigenvectors of random matrices

References

The paper cites 43 related references, primarily including:

• Anantharaman-Sabri's work on quantum ergodicity
• Bordenave's survey on random graph spectra
• Sah-Sawhney-Zhao's representation-theoretic methods for Cayley graphs
• Erdős et al.'s classical results on Wigner matrices

Overall Assessment: This is a high-quality theoretical paper that simplifies proofs of known results through innovative methods and extends them to more general settings. While it has limitations in handling exact eigenvectors, its unified methodology and in-depth analysis of approximate eigenvectors possess significant theoretical value and practical significance.