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

graph propertiesproperty testing

Mathematics Subject Classification ID

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

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

(40)

• Finite graphs and amenability
• On the tree-width of even-hole-free graphs
• Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs
• On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
• Infinite dimensional representations of finite dimensional algebras and amenability
• A parameterized algorithm for bounded-degree vertex deletion
• Property testing for bounded degree databases
• scientific article; zbMATH DE number 6846422 (Why is no real title available?)
• Every property of outerplanar graphs is testable
• Testing local properties of arrays
• The subgraph testing model
• Convergence theorems for graph sequences
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty
• Planar graphs: random walks and bipartiteness testing
• Edge correlations in Random regular hypergraphs and applications to subgraph testing
• Approximating partially bounded degree deletion on directed graphs
• Approximating bounded degree deletion via matroid matching
• On constant-size graphs that preserve the local structure of high-girth graphs
• Every property of hyperfinite graphs is testable
• An explicit construction of graphs of bounded degree that are far from being Hamiltonian
• Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs
• Approximating power node-deletion problems
• Testability in group theory
• scientific article; zbMATH DE number 7758318 (Why is no real title available?)
• Distributed Testing of Graph Isomorphism in the CONGEST Model.
• Faster Property Testers in a Variation of the Bounded Degree Model
• 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
• Approximating power node-deletion problems
• Faster property testers in a variation of the bounded degree model
• Testing C_k-freeness in bounded-arboricity graphs
• On testing isomorphism to a fixed graph in the bounded-degree graph model
• Testing isomorphism in the bounded-degree graph model
• On locally-characterized expander graphs (a survey)
• A characterization of testable hypergraph properties
• Approximate homomorphisms and sofic approximations of orbit equivalence relations
• Pliability and approximating Max-CSPs
• Testing depth first search numbering
• Testing cluster structure of graphs

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)