Some Mathematics behind Graph Property Testing
(invited lecture for ALT 2008)
Author: László Lovász
Affiliations: Department of Computer Science,
Eötvös Loránd University, Budapest, Hungary
Abstract.
Graph property testing is the third reincarnation of the same general
question, after statistics and learning theory. In its simplest form, we
have a huge graph (we don't even know its size), and we draw a sample of
the node set of bounded size. What properties of the graph can be
deduced from this sample?
The graph property testing model was first introduced by Goldreich,
Goldwasser and Ron (but related questions were considered before). In
the context of dense graphs, a very general result is due to Alon and
Shapira, who proved that every hereditary graph property is testable.
Using the theory of graph limits, Lovász and Szegedy defined an analytic
version of the (dense) graph property testing problem, which can be
formulated as studying an unknown 2variable symmetric function through
sampling from its domain and studying the random graph obtained when
using the function values as edge probabilities. This analytic version
allows for simpler formulation of the problems, and leads to various
characterizations of testable properties. These results can be applied
to the original graphtheoretic property testing. In particular, they
lead to a new combinatorial characterization of testable graph properties.
We survey these results, along with analogous results for graphs with
bounded degree.
©Copyright 2008 Author
