The ineffectiveness of the regularity lemma for bounded degree graphs
Abstract We show that for any , there is no bound computable from on the size of a graph required to approximate a graph of maximum degree at most up to error in ‐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.
Authors
- Grigory Terlov (ORCID: https://orcid.org/0000-0002-0365-2675)
- Zoltán Vidnyánszky (ORCID: https://orcid.org/0000-0001-8168-9353)
- Clark Lyons
Institutions
- Eötvös Loránd University (HU)
- University of North Carolina at Chapel Hill (US)
- HUN-REN Alfréd Rényi Institute of Mathematics (HU)
Publication Details
- Journal
- Bulletin of the London Mathematical Society
- Published
- 2025-08-19
- DOI
- https://doi.org/10.1112/blms.70176
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Hawaii Academy of Science
- European Research Council
- National Research, Development and Innovation Office