Testing properties of graphs and functions

By L. Lov'asz, Balázs Szegedy. 2008

90 citations recorded by the source corpus.

We define an analytic version of the graph property testing problem, which can be formulated as studying an unknown 2-variable symmetric function through sampling from its domain and studying the random graph obtained when using the function values as edge probabilities. We give a characterization of properties testable this way, and extend a number of results about “large graphs” to this setting.These results can be applied to the original graph-theoretic property testing. In particular, we give a new combinatorial characterization of the testable graph properties. Furthermore, we define a class of graph properties (flexible properties) which contains all the hereditary properties, and generalize various results of Alon, Shapira, Fischer, Newman and Stav from hereditary to flexible properties.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics

View Paper: https://www.semanticscholar.org/paper/a5db924cebe1644bd62db6f9de59248ee3656d18

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

Citations in the corpus

Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges (2009, methodology): “A related random graph model generating dense graphs ( p = 1) was introduced in [49] and studied in [16].”
Estimating and understanding exponential random graph models (2011, background): “In a sequence of papers [9, 10, 11, 25, 37, 38, 39, 40, 41, 42, 43], Laszlo Lovász and coauthors V.”
Matrix estimation by Universal Singular Value Thresholding (2012, background): “ Graphons. A graphon is a measurable function f: [0;1]2 ![0;1] that satises f(x;y) f(y;x). The term ‘graphon’ was coined by Lovasz and coauthors in the growing literature on limits of dense graphs [21, 22, 23, 72, 73, 74]. Such functions also arise in the related study of weakly exchangeable random ”
Graph limits and exchangeable random graphs (2007, background): “It is natural to seek an approximation theory: What does it mean for a sequence of graphs to converge? When can a large complex graph be approximated by a small graph? In a sequence of papers [6, 7, 8, 9, 15, 18, 19, 20, 23, 22, 24, 21] Laszlo Lovász with coauthors (listed here in order of frequency”
The large deviation principle for the Erd\H{o}s-R\'enyi random graph (2010, background): “formulating such a program for random graphs is in constructing a single abstract space in which all graphs can be embedded. Fortunately, this issue has been settled recently. In a sequence of papers [5, 6, 7, 15, 19, 20, 21, 22, 23, 24, 25] Laszlo Lov´asz with coauthors (listed here in order of fre”