The complexity of properties of large graphs

Noga Alon
Tel Aviv University and IAS, Princeton

A graph property is a family of graphs closed under isomorphism. A property is hereditary if it is closed under taking induced subgraphs. The distance of a graph from a property is the minimum number of edges that have to be added to or deleted from the graph to get one that satisfies the property. It turns out that for many interesting graph properties, including all hereditary ones, it is possible to distinguish between graphs on n vertices that satisfy the property and ones that are of distance at least epsilon n^2 from satisfying it, by inspecting an induced subgraph on a randomly chosen set of vertices whose size is bounded by a function of epsilon, and is independent of n. Moreover, there is an efficient deterministic procedure that approximates the distance of a given n-vertex input graph from the property up to an additive error of epsilon n^2.
These results, which indicate that in some sense hereditary graph properties cannot be too complex, are obtained by a combination of combinatorial, probabilistic and analytic tools including Szemeredi's Regularity Lemma and Grothendieck's Inequality.

I will survey the topic, mentioning the main questions and giving a brief description of the relevant proof techniques.