Sparse graphs and their Benjamini-Schramm limits: a spectral tour

Basic Information

• Paper ID: 2510.10299
• Title: Sparse graphs and their Benjamini-Schramm limits: a spectral tour
• Author: Charles Bordenave (CNRS & Aix-Marseille Université)
• Classification: math.PR (Probability Theory), math.CO (Combinatorics), math.SP (Spectral Theory)
• Publication Date: October 11, 2025
• Paper Link: https://arxiv.org/abs/2510.10299v1

Abstract

Sparse graphs with bounded average degree form a rich class of discrete structures in which local geometry strongly influences global behavior. Benjamini-Schramm (BS) convergence provides a natural framework for describing their asymptotic local structure. This paper surveys spectral aspects of BS convergence and their applications, with emphasis on random Schreier graphs and covering graphs. The author reviews recent advances in spectral decomposition of local operators on graphs, discusses the behavior of extreme eigenvalues and the important role of strong distributional convergence (which can exclude spectral outliers), and presents new applications of strong convergence to typical graph distances between vertices in Schreier graphs.

Research Background and Motivation

Core Problems

The core problems addressed in this paper concern understanding the asymptotic spectral properties of sparse graph sequences, particularly through the Benjamini-Schramm convergence framework:

1. How to characterize the relationship between local geometry and global spectral behavior in sparse graphs
2. Asymptotic behavior of extreme eigenvalues in large sparse graphs
3. How strong convergence excludes spectral outliers
4. Concrete applications of these theories in random graphs and covering graphs

Significance

This research is significant because:

1. Theoretical Value: BS convergence has become a core component of graph limit theory, particularly effective in the study of random graphs, Cayley graphs, Schreier graphs, and covering graphs
2. Broad Applications: Extended from initial combinatorial optimization problems and recurrence properties of random walks on planar graphs to hypergraphs and other discrete or geometric structures
3. Spectral Theory Connections: Bridges multiple mathematical branches including group theory, probability theory, and spectral geometry

Limitations of Existing Methods

1. Understanding of non-commutative distributional convergence remains incomplete
2. Characterization of extreme eigenvalue behavior lacks a unified framework
3. Application potential of strong convergence phenomena has not been fully developed
4. Spectral decomposition theory for random unimodular graphs is relatively underdeveloped

Core Contributions

1. Systematic Survey: Provides a comprehensive survey of spectral aspects of BS convergence, with particular focus on random Schreier graphs and covering graphs
2. Theoretical Unification: Unifies local operators, non-commutative distributional convergence, and spectral decomposition theory under the BS convergence framework
3. Strong Convergence Applications: Demonstrates new applications of strong convergence in excluding spectral outliers and typical graph distance problems
4. Open Problems Compilation: Systematically identifies important open problems in the field, providing direction for future research

Methodology Details

Task Definition

The core task of this paper is to study spectral properties of sparse marked graph sequences $(G_n)$, where:

• Input: Finite marked graph sequences $G_n = (V_n, E_n, \xi_n)$ satisfying BS convergence conditions
• Output: Spectral measure convergence of local operators, extreme eigenvalue behavior, strong convergence properties
• Constraints: Bounded average degree of graphs, satisfaction of unimodularity conditions

Core Theoretical Framework

1. Benjamini-Schramm Convergence

For a finite marked graph $G = (V,E,\xi)$, its neighborhood distribution is defined as: $U(G) = \frac{1}{|V|}\sum_{v \in V} \delta_{[G,v]}$

Definition 2.4: A sequence of finite marked graphs $(G_n)$ converges in the BS sense to $\mu \in P(\dot{G})$ if $U(G_n)$ converges weakly to $\mu$.

2. Local Operator Theory

For a marked graph $G = (V,E,\xi)$, the local operator $A = A_{G,a}$ is defined as: $A\phi(v) = \sum_{u \in V} a(G^{(uv)})\phi(u)$

where $a: \ddot{G} \to \mathbb{C}$ is a continuous function and $G^{(uv)}$ is the connected component containing vertices $u,v$.

3. Spectral Measure Convergence

Theorem 3.2: Let $a: \ddot{G} \to \mathbb{C}$ be a symmetric continuous function, and $(G_n)$ converge in the BS sense to $\mu$. Then: $m_{A_{G_n,a}} \to m_{\mu,a}$ where $m_{A,a}$ denotes the average spectral measure of operator $A$.

Technical Innovations

1. Strong Convergence Theory

Introduces the concept of strong distributional convergence: for a sequence of representations $\rho_n$ of group $\Gamma$, $\lim_{n \to \infty} \|\rho_n(a)\| = \|\lambda(a)\|, \quad \forall a \in \mathbb{C}[\Gamma]$

This is stronger than ordinary distributional convergence and can exclude spectral outliers.

2. Linearization Technique

Proposition 4.7: Through Pisier's linearization technique, the study of non-commutative *-polynomials is reduced to the study of matrix-coefficient linear expressions.

3. Extension of Ihara-Bass Formula

Theorem 3.4: For a finite graph $G$, its adjacency operator $A$ and non-backtracking operator $B$ satisfy: $\det(z\mathbf{1}_E - B) = (z^2-1)^{\chi-1}\det(z^2\mathbf{1}_V - zA + D - \mathbf{1}_V)$

Experimental Setup

Theoretical Verification

This paper is primarily a theoretical survey, with verification of theory through the following approaches:

1. Classical Random Graph Models

• d-regular random graphs: Verification of Friedman's theorem and Alon-Boppana bounds
• Erdős-Rényi graphs: Study of asymptotic behavior of extreme eigenvalues
• Galton-Watson trees: Typical examples as BS limits

2. Concrete Computational Examples

• Spectral measure of infinite d-regular trees: Kesten-McKay measure $m_{T_d} = \frac{d\sqrt{4(d-1)-x^2}}{2\pi(d^2-x^2)}dx$
• Spectral properties of Poisson(d)-distributed Galton-Watson trees

Experimental Results

Main Theoretical Results

1. Non-backtracking Version of Friedman's Theorem

Theorem 4.4: For random d-regular graphs, the second-largest eigenvalue of the non-backtracking operator satisfies: $|\lambda_2| \leq \sqrt{\lambda_1} + \epsilon$ where $\lambda_1 = d-1$.

2. Applications of Strong Convergence

Lemma 4.8: For strongly convergent representations of non-amenable groups, the typical graph distance satisfies: $\lim_{n \to \infty} \max_{v \in V_n} \frac{|\{u \in V_n: d(u,v) \geq (1+\epsilon)\frac{\ln|V_n|}{\beta_S}\}|}{|V_n|} = 0$

3. Strong Convergence of Random Representations of Free Groups

Theorem 4.9: For random representations of the free group $F_d$ with Haar distribution, strong convergence to the left regular representation occurs when restricted to the orthogonal complement of the invariant subspace.

Spectral Decomposition Results

Complete Characterization of Galton-Watson Trees

Theorem 3.3: For Galton-Watson trees with Poisson(d) distribution:

• Atomic spectrum: $m_d(\{\lambda\}) > 0$ if and only if $\lambda$ is a completely real algebraic integer
• Continuous spectrum: Non-trivial continuous part exists when $d > 1$
• Absolutely continuous spectrum: Non-trivial absolutely continuous part exists when $d > d_1$

Related Work

Historical Development

1. Origins: Aldous 2 on combinatorial optimization problems, Benjamini-Schramm 14 on random walks on planar graphs
2. Spectral Theory Applications: Early work 25 began applying BS limits to graph spectral theory
3. Random Matrix Theory: Haagerup-Thorbjørnsen 47 on strong convergence theory

Related Fields

1. Graph Limit Theory: Contrasts with Lovász theory for dense graphs
2. Group Representation Theory: Spectral theory of Cayley and Schreier graphs
3. Random Matrix Theory: Free probability and strong convergence phenomena
4. Quantum Percolation: Eigenstate localization in disordered media

Conclusions and Discussion

Main Conclusions

1. Spectral Continuity of BS Convergence: Average spectral measures are continuous under BS convergence
2. Power of Strong Convergence: Can completely exclude spectral outliers with important applications in geometric graph theory
3. Advantages of Non-backtracking Operators: More suitable than adjacency operators for studying spectral gaps in random graphs
4. Special Nature of Free Groups: Strong convergence of random representations provides unified solutions to many concrete problems

Limitations

1. Rarity of Strong Convergence: Currently only random matrix theory provides non-trivial examples of strong convergence
2. Computational Complexity: Computation of concrete spectral measures remains difficult
3. General Groups: Strong convergence theory beyond free groups remains incomplete
4. Singular Continuous Spectrum: Its existence remains an open problem

Future Directions

1. More General Groups: Strong convergence theory for right-angled Artin groups, surface groups, etc.
2. Quantum Percolation: Eigenstate delocalization in higher dimensions
3. Precise Characterization of Spectral Gaps: Particularly on random hyperbolic surfaces
4. Algorithmic Applications: Applications in community detection and compressed sensing

In-Depth Evaluation

Strengths

1. Strong Systematicity: Comprehensively surveys spectral theory of BS convergence, connecting multiple mathematical branches
2. Theoretical Depth: Organically combines abstract operator algebra theory with concrete graph-theoretic problems
3. Application-Oriented: Not only develops theory but also demonstrates concrete applications in geometric graph theory
4. Openness: Honestly identifies open problems and technical challenges in the field

Weaknesses

1. Limited Computational Examples: Relatively few concretely computable examples
2. Algorithmic Complexity: While theoretically elegant, practical computation remains challenging
3. Limited Application Scope: Applications of strong convergence are mainly restricted to free group cases

Impact

1. Theoretical Contribution: Provides a unified framework for spectral theory of sparse random graphs
2. Cross-disciplinary Value: Bridges probability theory, spectral geometry, group theory, and other fields
3. Practical Value: Potential applications in network analysis, community detection, and related areas
4. Educational Value: As a survey article, provides excellent introductory material for learners in the field

Applicable Scenarios

1. Theoretical Research: Graph limit theory, random graph theory, spectral geometry research
2. Applied Mathematics: Network science, percolation models in statistical physics
3. Computer Science: Community detection algorithms, theoretical foundations of graph neural networks
4. Teaching: Advanced courses in probability theory and algebraic graph theory

References

The article contains 84 references spanning from classical Alon-Boppana bounds to recent strong convergence theory, reflecting the complete development trajectory of the field. Important references include:

• Original Benjamini-Schramm papers 14
• Haagerup-Thorbjørnsen strong convergence theory 47
• Friedman's Ramanujan graph theory 41
• Author's series of works 15-28

Overall Assessment: This is a high-quality survey paper that systematically summarizes the development of spectral theory for BS convergence of sparse graphs, combining deep theoretical analysis with concrete applications. It is of significant value for both researchers and learners in the field.