The ineffectiveness of the regularity lemma for bounded degree graphs

2025/05/09 by Clark Lyons, Lyons, Clark, Grigory Terlov +3 · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory #Logic (math.LO) #Markov Chains and Monte Carlo Methods

paper · pdf · doi:10.48550/arxiv.2505.06215

openalex publication_date 2025/05/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that for any Δ≥ 3, there is no bound computable from (ε, r) on the size of a graph required to approximate a graph of maximum degree at most Δ up to ε error in r-neighborhood statistics. This provides a negative answer to a question posed by Lovász. Our result is a direct consequence of the recent celebrated work of Bowen, Chapman, Lubotzky, and Vidick, which refutes the Aldous-Lyons conjecture.

Citations

• There Is An Equivalence Relation Whose von Neumann Algebra Is Not Connes Embeddable
• Invariant Schreier decorations of unimodular random networks
• Action convergence of operators and graphs
• On invariant Schreier structures
• On the density of triangles and squares in regular finite and unimodular random graphs

Cited by

• Invariant Random Subgroups, Soficity, and Lück's determinant conjecture

Related

• The Regularity Lemma with bounded VC Dimension
• Every Minor-Closed Property of Sparse Graphs is Testable
• On Generalized Regularity
• Spectral radius minus average degree: a better bound
• Revealing Structure in Large Graphs: Szemer 'edi's Regularity Lemma and\n its Use in Pattern Recognition