## Monotone Graph Properties

A graph property is *monotone* if it is closed under removal of
vertices and edges. After a brief discussion of some of the remarkable
extremal and enumerative features of such properties, I will describe a
recent joint work with Shapira and Sudakov that deals with the algorithmic
problem of estimating the distance of a given graph from satisfying a
specified monotone property.

It turns out that for any monotone graph property *P* and any *ε*>0 one can approximate, deterministically and in linear time,
the minimum number of edges that have to be deleted from an *n*-vertex
input graph to get a graph that satisfies *P*, up to an additive error
of *ε*n^{2}. Moreover, for any dense monotone property, that is,
a property for which there are graphs on *n* vertices with Ω(n^{2})
edges that satisfy it, it is NP-hard to approximate this minimum up to an
additive error of n^{2-ε}, for any fixed positive *ε*. The
second part answers a question raised by Yannakakis in 1981.

The proofs combine tools from Extremal Graph Theory with probabilistic and spectral techniques.

**Noga Alon, Tel Aviv University**