Every minor-closed property of sparse graphs is testable

DOI10.1016/j.aim.2009.10.018zbMath1223.05291arXiv0801.2797MaRDI QIDQ962147

Itai Benjamini, Oded Schramm, Asaf Shapira

Publication date: 6 April 2010

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0801.2797

zbMATH Keywords

property testing; sparse graphs; minor closed; hyper finite

Mathematics Subject Classification ID

05C83: Graph minors

Related Items

An analytic approach to stability, Finite graphs and amenability, Limits of locally-globally convergent graph sequences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. XX: Wagner's conjecture
• Lower bound of the Hadwiger number of graphs by their average degree
• Hyperfinite graph limits
• Testing the expansion of a graph
• Self-testing/correcting with applications to numerical problems
• The extremal function for complete minors
• A sublinear bipartiteness tester for bounded degree graphs
• The combinatoral cost
• Graph limits and parameter testing
• Parameter testing in bounded degree graphs of subexponential growth
• On Testing Expansion in Bounded-Degree Graphs
• Property testing and its connection to learning and approximation
• An extremal function for contractions of graphs
• Graph minor theory
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• A Separator Theorem for Nonplanar Graphs
• Efficient Planarity Testing
• Testing the diameter of graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Local Graph Partitions for Approximation and Testing
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• SOFSEM 2005: Theory and Practice of Computer Science
• An Expansion Tester for Bounded Degree Graphs
• Property testing in bounded degree graphs