Every minor-closed property of sparse graphs is testable

DOI10.1016/J.AIM.2009.10.018MaRDI QIDQ962147zbMATH OpenOpenAlexFDO

Authors 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

sparse graphsproperty testingminor closedhyper finite

Mathematics Subject Classification ID

Graph minors (05C83)

Abstract: Suppose $G$ is a graph with degrees bounded by $d$, and one needs to remove more than $epsilonn$ of its edges in order to make it planar. We show that in this case the statistics of local neighborhoods around vertices of $G$ is far from the statistics of local neighborhoods around vertices of any planar graph $G^{\prime }$ with the same degree bound. In fact, a similar result is proved for any minor-closed property of bounded degree graphs. As an immediate corollary of the above result we infer that many well studied graph properties, like being planar, outer-planar, series-parallel, bounded genus, bounded tree-width and several others, are testable with a constant number of queries, where the constant may depend on $epsilon$ and $d$, but not on the graph size. None of these properties was previously known to be testable even with $o(n)$ queries.

Recommendations

• Random walks and forbidden minors. I: An \(n^{1/2+o(1)}\)-query one-sided tester for minor closed properties on bounded degree graphs
• Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs
• Random walks and forbidden minors II
• scientific article; zbMATH DE number 1559556
• On testable properties in bounded degree graphs

Cites work

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

Cited in

(20)

• Limits of locally-globally convergent graph sequences
• 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
• Planarity can be verified by an approximate proof labeling scheme in constant-time
• On testability of first-order properties in bounded-degree graphs and connections to proximity-oblivious testing
• Every property of hyperfinite graphs is testable
• Finite graphs and amenability
• Graph theory. Abstracts from the workshop held January 2--8, 2022
• Planar graphs: random walks and bipartiteness testing
• An analytic approach to stability
• An explicit construction of graphs of bounded degree that are far from being Hamiltonian
• The subgraph testing model
• Random walks and forbidden minors. I: An \(n^{1/2+o(1)}\)-query one-sided tester for minor closed properties on bounded degree graphs
• On the tree-width of even-hole-free graphs
• Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs
• Faster Property Testers in a Variation of the Bounded Degree Model
• Local 2-separators
• Testing outerplanarity of bounded degree graphs
• scientific article; zbMATH DE number 7758318 (Why is no real title available?)
• Hyperfinite graphings and combinatorial optimization

This page was built for publication: Every minor-closed property of sparse graphs is testable

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