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 εn2. Moreover, for any dense monotone property, that is, a property for which there are graphs on n vertices with Ω(n2) edges that satisfy it, it is NP-hard to approximate this minimum up to an additive error of n2-ε, 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
