Testing linear inequalities of subgraph statistics
METADATA ONLY
Loading...
Author / Producer
Date
2021-05
Publication Type
Journal Article
ETH Bibliography
no
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
Property testers are fast randomized algorithms whose task is to distinguish between inputs satisfying some predetermined property and those that are far from satisfying it. A landmark result of Alon et al. states that for any finite family of graphs, the property of being induced ‐free (i.e., not containing an induced copy of any) is testable. Goldreich and Shinkar conjectured that one can extend this by showing that for any linear inequality involving the densities of the graphs in the input graph, the property of satisfying this inequality is testable. Our main result in this paper disproves this conjecture. The proof deviates significantly from prior nontestability results in this area. The main idea is to use a linear inequality relating induced subgraph densities in order to encode the property of being a quasirandom graph.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
58 (3)
Pages / Article No.
468 - 479
Publisher
Wiley
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Graph property testing; Subgraph density
Organisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin