The ineffectiveness of the regularity lemma for bounded degree graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909734219546624 |
|---|---|
| author | Lyons, Clark Terlov, Grigory Vidnyánszky, Zoltán |
| author_facet | Lyons, Clark Terlov, Grigory Vidnyánszky, Zoltán |
| contents | We show that for any $Δ\geq 3$, there is no bound computable from $(\varepsilon, r)$ on the size of a graph required to approximate a graph of maximum degree at most $Δ$ up to $\varepsilon$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_06215 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The ineffectiveness of the regularity lemma for bounded degree graphs Lyons, Clark Terlov, Grigory Vidnyánszky, Zoltán Combinatorics Logic We show that for any $Δ\geq 3$, there is no bound computable from $(\varepsilon, r)$ on the size of a graph required to approximate a graph of maximum degree at most $Δ$ up to $\varepsilon$ 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. |
| title | The ineffectiveness of the regularity lemma for bounded degree graphs |
| topic | Combinatorics Logic |
| url | https://arxiv.org/abs/2505.06215 |