What is the furthest graph from a hereditary property?

TY - JOUR

T1 - What is the furthest graph from a hereditary property?

AU - Alon, Noga

AU - Stav, Uri

PY - 2008/8

Y1 - 2008/8

N2 - For a graph property P, the edit distance of a graph G from P, denoted EP(G), is the minimum number of edge modifications (additions or deletions) one needs to apply to G 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 EP (G) 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 that depends on P essentially achieves the maximal distance from P, that is: ed(n, P) = EP (G(n,p(P)))+ o(n2) with high probability. The proofs combine several tools, including strengthened versions of the Szemerédi regularity lemma, properties of random graphs and probabilistic arguments.

AB - For a graph property P, the edit distance of a graph G from P, denoted EP(G), is the minimum number of edge modifications (additions or deletions) one needs to apply to G 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 EP (G) 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 that depends on P essentially achieves the maximal distance from P, that is: ed(n, P) = EP (G(n,p(P)))+ o(n2) with high probability. The proofs combine several tools, including strengthened versions of the Szemerédi regularity lemma, properties of random graphs and probabilistic arguments.

KW - Hereditary graph properties

KW - Random graphs

KW - Regularity lemma

UR - http://www.scopus.com/inward/record.url?scp=52349122623&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=52349122623&partnerID=8YFLogxK

U2 - 10.1002/rsa.20209

DO - 10.1002/rsa.20209

M3 - Article

SN - 1042-9832

VL - 33

SP - 87

EP - 104

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 1

ER -