Skeletons and Spectra: Bernoulli graphings are relatively Ramanujan

Basic Information

• Paper ID: 2510.13323
• Title: Skeletons and Spectra: Bernoulli graphings are relatively Ramanujan
• Authors: Héctor Jardón-Sánchez, László Márton Tóth
• Classification: math.PR (Probability Theory), math.CO (Combinatorics)
• Publication Date: October 17, 2025
• Paper Link: https://arxiv.org/abs/2510.13323

Abstract

This paper investigates the spectral theory of unimodular random graphs and their graphing representations. The authors prove that Bernoulli graphings are relatively Ramanujan with respect to their skeleton Markov chains, meaning that the spectral part arising from random labels falls within appropriate Alon-Boppana bounds. This result complements an example by Frączyk: there exist ergodic unimodular random graphs with almost surely spectral gaps but non-expanding Bernoulli graphings. The paper emphasizes connections with finite random graph theory, utilizing results by Bordenave and Collins on random lifts being relatively almost Ramanujan to prove a strengthened version of the main theorem for unimodular quasi-transitive quasi-trees.

Research Background and Motivation

Problem Background

The core problem investigated is the relationship between the local spectral radius ρ(G,o) of unimodular random graphs and the global spectral radius ρ(B) of their Bernoulli graphings. In graph theory, the Ramanujan property is an important concept requiring that a graph's spectral radius achieves the theoretical lower bound given by the Alon-Boppana theorem.

Research Motivation

1. Theoretical Completeness: While Bernoulli graphings are known to possess the Ramanujan property for Cayley graphs and regular trees (ρ(G,o) = ρ(B)), it remains unclear whether this property holds for general unimodular random graphs.
2. Existence of Counterexamples: Frączyk constructed a counterexample showing cases where ρ(G,o) < 1 but ρ(B) = 1, indicating that simple Ramanujan property does not always hold.
3. Finite-Infinite Connection: The paper aims to establish bridges between finite random graph theory (such as Friedman's theorem) and infinite graphing theory.

Limitations of Existing Methods

• Existing results are primarily limited to special cases (e.g., Cayley graphs, regular trees)
• Lack of deep understanding of spectral structure for general unimodular random graphs
• Insufficient clarity in connections between finite and infinite graph theories

Core Contributions

1. Main Theorem: Proves that Bernoulli graphings are Ramanujan relative to their skeleton, i.e., σR(B) ⊆ -ρ(G,o), ρ(G,o)
2. Spectral Inclusion Relations: Establishes inclusion relationships between local and global spectra: σ(G,o) ⊆ σR(B)
3. Counterexample Analysis: Provides and analyzes Frączyk's counterexample, demonstrating the necessity of relative Ramanujan property
4. Finite-Infinite Connection: Utilizing Bordenave-Collins results, proves a strengthened version of the theorem for unimodular quasi-transitive quasi-trees
5. Graph-Theoretic Characterization: Provides complete characterization of unimodular quasi-transitive quasi-trees (Theorem 1.7)

Methodology Details

Core Concept Definitions

Unimodular Random Graphs: Random rooted graphs (G,o) satisfying the mass transport principle, i.e., for any Borel function f: ∫∑f(G,o',o)d(G,o) = ∫∑f(G,o,o')d(G,o)

Bernoulli Graphings: Borel graphs B defined on G+• where vertices are rooted graphs with iid uniform 0,1 labels

Spectral Decomposition: Decomposition of L²(G+•,μ*) into structural subspace S and random subspace R:

• S: Functions depending only on graph structure
• R = S⊥: Functions depending on random labels

Technical Framework

1. Spectral Decomposition Method

The core technique decomposes the spectrum σ(B) of Bernoulli graphings into:

• Structural spectrum: σS(B) = σ(M|S)
• Random spectrum: σR(B) = σ(M|R)

where M is the Markov operator.

2. Skeleton Markov Chain

Defines skeleton Markov chain S on G•: pS((G,u),(H,v)) = |{w ∈ NG(u) : (G,w) ≅ (H,v)}|/degG(u)

Proves that σS(B) = σ(N), where N is the Markov operator of the skeleton.

3. Block Factor Approximation

Uses block factors to approximate functions in the random subspace, whose values depend only on labels within finite radius from the root.

Key Proof Techniques

Proof Strategy for Theorem 1.1:

1. Using Beurling spectral radius formula, it suffices to prove for any normalized block factor f ∈ R: n√⟨Mnf,f⟩ ≤ (1+o(1))ρ(G,o)
2. Decompose inner products into contributions from vertices within and beyond distance 2r from root
3. For vertices beyond distance 2r, contributions vanish due to block factor property and random subspace characterization
4. Complete proof using Cauchy-Schwarz inequality and annealed spectral radius results

Experimental Setup

This is a pure theory paper, verified primarily through mathematical proofs rather than numerical experiments. However, the paper provides important constructive examples:

Frączyk Counterexample Construction

• Base Group: Free group F₂ = ⟨a,b⟩
• Homomorphism: φ: F₂ → Z, φ(a) = φ(b) = 1
• Graph Construction: Starting from 4-regular tree T, construct markings via homomorphism φ, then obtain (G,o) as a factor
• Key Property: ρ(G,o) < 1 but ρ(B) = 1

Main Results

Core Theorems

Theorem 1.1: Bernoulli graphing B is Ramanujan relative to its skeleton: σR(B) ⊆ -ρ(G,o), ρ(G,o)

Theorem 1.2: For all aperiodic graphings G, ρ(G,o) ≤ ρ(G)

Theorem 1.4: For ergodic unimodular random graphs, ρ(G,o) = ρR(B)

Strengthened Results

Theorem 1.6: For unimodular quasi-transitive quasi-trees G, σR(B) = σ(G)

This is a strict strengthening of Theorem 1.1, showing that for this special graph class, the random spectrum exactly equals the graph's spectrum.

Graph-Theoretic Characterization

Theorem 1.7: For locally finite connected graphs G, the following are equivalent:

1. G is a unimodular quasi-transitive quasi-tree
2. There exists a free quasi-transitive action Fd ↷ G
3. There exist finite graph H and map φ such that G ≅ H̃/ker(φ)

Related Work

Finite Graph Theory

• Alon-Boppana Theorem: Provides lower bounds for spectral radius of d-regular graphs
• Friedman's Theorem: Random d-regular graphs are almost surely Ramanujan
• Bordenave-Collins Results: New characterization of eigenvalue convergence for random lifts

Infinite Graph Theory

• Kesten's Theorem: Connects spectral radius with reachability
• Backhausz-Szegedy-Virág Results: Bernoulli graphings of regular trees are Ramanujan
• Graphing Theory: Limit theory developed by Lovász and others

Conclusions and Discussion

Main Conclusions

1. Relative Ramanujan Property: While Bernoulli graphings are not always Ramanujan, the spectral part arising from randomness always satisfies Ramanujan bounds
2. Structure-Randomness Separation: Clear separation between structural and random parts of spectrum, with the former determined by skeleton
3. Finite-Infinite Correspondence: Establishes profound connections between finite random graph results and infinite graphing results

Limitations

1. Special Cases: Complete characterization holds only for unimodular quasi-transitive quasi-trees
2. Constructivity: Some proofs are existential, lacking explicit constructions
3. Computational Complexity: Methods for computing spectra in practice remain difficult

Future Directions

The paper proposes several important open problems in Section 6:

1. Configuration Model: Are non-regular random graphs almost Ramanujan?
2. Galton-Watson Trees: Are their Bernoulli graphings Ramanujan?
3. General Case: Does σR(G) = σ(G,o) always hold?
4. Strong Convergence: Does strong convergence of random representations provide additional spectral information?

In-Depth Evaluation

Strengths

1. Theoretical Depth: Establishes important results in spectral theory of unimodular random graphs, filling theoretical gaps
2. Technical Innovation: Spectral decomposition method and relative Ramanujan concept are original
3. Broad Connections: Effectively connects finite graphs, infinite graphs, probability theory, and combinatorics
4. Clear Structure: Well-organized paper with clear progression from motivation to technical details

Weaknesses

1. Limited Applications: Primarily theoretical results with unclear practical application scenarios
2. Computational Difficulty: While establishing theoretical framework, actual computation remains difficult
3. Specificity: Strongest results apply only to special graph classes

Impact

1. Theoretical Contribution: Provides foundational results for spectral theory of unimodular random graphs
2. Methodological Value: Spectral decomposition method may apply to other problems
3. Cross-disciplinary Impact: Connects multiple mathematical branches, potentially inspiring further research

Applicable Scenarios

1. Theoretical Research: Graph spectral theory, random graph theory, ergodic theory
2. Network Analysis: Spectral property analysis of large-scale networks
3. Algorithm Design: Design of graph algorithms based on spectral properties

Technical Details Supplement

Key Inequalities

The core technical result of the paper is that for any normalized block factor f ∈ R:

n√⟨Mnf,f⟩ ≤ K^(2/n) * n√E_ν*[p_n(o,o)] ≤ (1+o(1))ρ(G,o)

Application of Mass Transport Principle

The mass transport principle plays crucial roles in multiple places:

• Proving stationarity of skeleton Markov chains
• Establishing relationships between local and global measures
• Controlling norms of block factors

This systematic application demonstrates the authors' deep understanding of this tool.