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

CREATOROded Lachish, Amit Levi, Ilan Newman, Felix Reidl
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE108730
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.04466

Browse the full library · About the Tower of Babel