All reports by Author Oded Schramm:

__
TR08-010
| 17th January 2008
__

Itai Benjamini, Oded Schramm, Asaf Shapira#### Every Minor-Closed Property of Sparse Graphs is Testable

Itai Benjamini, Oded Schramm, Asaf Shapira

Testing a property P of graphs in the bounded degree model deals with the following problem: given a graph G of bounded degree d we should distinguish (with probability 0.9, say) between the case that G satisfies P and the case that one should add/remove at least \epsilon d n ... more >>>