Combinatorics Seminar

When: Sunday, May 13, 10am Where: Schreiber 309 Speaker: Uri Stav, Tel Aviv University Title: Graph edit-distance and hereditary properties

Abstract:

For a graph property P, the edit distance of a graph G from P, denoted Delta(G,P), is the minimum number of edge modifications (additions or deletions) one needs to apply to G in order to turn it into a graph satisfying P. What is the furthest graph on $n$ vertices from P and what is the largest possible edit distance from P? Denote this maximal distance by ed(n,P). This question is motivated by algorithmic edge-modification problems, in which one wishes to find or approximate the value of Delta(G,P) given an input graph G.

A monotone graph property is closed under removal of edges and vertices. Trivially, for any monotone property, the largest edit distance is attained by a complete graph. We show that this is a simple instance of a much broader phenomenon. A hereditary graph property is closed under removal of vertices. We prove that for any hereditary graph property P, a random graph with an edge density p(P) that depends on P essentially achieves the maximal distance from P, that is: ed(n,P)= \Delta(G(n,p(P)),P) + o(n^2) with high probability. We determine the values of p(P) and ed(n,P) for some subfamilies of hereditary properties; thus deducing these parameters for some well studied hereditary graph properties, such as being Perfect, Chordal, Interval, Permutation, Claw-Free, Cograph and more. In addition, even stronger results, close in nature to classical stability-type results in Extremal Graph Theory, are shown. For example, if one turns G(n,1/2) into an induced C_4-free graph in the most economical way, then a graph of a very restricted form (namely, a split graph) is obtained w.h.p.

In the talk I will survey the main results and sketch parts of the proofs, demonstrating the methods we use.

Joint work with Noga Alon.