A characterization of one-sided error testable graph properties in bounded degeneracy graphs
Oded Lachish, Amit Levi, Ilan Newman, Felix Reidl · 2026
Read A characterization of one-sided error testable graph properties in bounded degeneracy graphs by Oded Lachish, Amit Levi, Ilan Newman, Felix Reidl (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-04466.txt.
Description
Lachish and colleagues characterize one-sided error testable properties in bounded degeneracy graphs under the random neighbor oracle model. A tester explores a graph by sampling neighbors; a property is testable with one-sided error when query complexity stays size-independent. But broader p-degenerate graphs allow high-degree hubs hiding forbidden subgraphs from local search. The team characterizes all one-sided error testable properties in p-degenerate graphs. Testability turns on forbidden-structure connectivity: a property is testable exactly when violations cannot fragment across high-degree neighborhoods.
Catalog record
| CREATOR | Oded Lachish, Amit Levi, Ilan Newman, Felix Reidl |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 108730 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.04466