Every property of hyperfinite graphs is testable

DOI10.1137/120890946MaRDI QIDQ2848211zbMATH OpenOpenAlexFDO

Authors Ilan Newman, Christian Sohler

Publication date 25 September 2013

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/120890946

zbMATH Keywords

property testinggraph properties

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal combinatorics (05D99)

Recommendations

• Every property of hyperfinite graphs is testable
• Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty
• Every property of outerplanar graphs is testable
• Every minor-closed property of sparse graphs is testable
• On testable properties in bounded degree graphs

Cited in

(30)

• Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs
• Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs
• Edge correlations in Random regular hypergraphs and applications to subgraph testing
• scientific article; zbMATH DE number 7559054 (Why is no real title available?)
• Maximum weight t-sparse set problem on vector-weighted graphs
• On testability of first-order properties in bounded-degree graphs and connections to proximity-oblivious testing
• Finite graphs and amenability
• scientific article; zbMATH DE number 6846422 (Why is no real title available?)
• Approximating power node-deletion problems
• Approximating power node-deletion problems
• Convergence theorems for graph sequences
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• Planar graphs: random walks and bipartiteness testing
• Approximating bounded degree deletion via matroid matching
• Property testing for bounded degree databases
• Approximating partially bounded degree deletion on directed graphs
• An explicit construction of graphs of bounded degree that are far from being Hamiltonian
• Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty
• The subgraph testing model
• On the tree-width of even-hole-free graphs
• Every property of hyperfinite graphs is testable
• Testability in group theory
• Every property of outerplanar graphs is testable
• Infinite dimensional representations of finite dimensional algebras and amenability
• Distributed Testing of Graph Isomorphism in the CONGEST Model.
• Faster Property Testers in a Variation of the Bounded Degree Model
• scientific article; zbMATH DE number 7758318 (Why is no real title available?)
• On constant-size graphs that preserve the local structure of high-girth graphs
• On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
• A parameterized algorithm for bounded-degree vertex deletion

This page was built for publication: Every property of hyperfinite graphs is testable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848211)