What is the furthest graph from a hereditary property?
Authors:
- 2 April 2008
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 33 (1) , 87-104
Abstract
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. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008Keywords
This publication has 14 references indexed in Scilit:
- The Penultimate Rate of Growth for Graph PropertiesEuropean Journal of Combinatorics, 2001
- The Probabilistic Method2000
- The Speed of Hereditary Properties of GraphsJournal of Combinatorial Theory, Series B, 2000
- The Structure of Hereditary Properties and Colourings of Random GraphsCombinatorica, 2000
- Projections of Bodies and Hereditary Properties of HypergraphsBulletin of the London Mathematical Society, 1995
- On the entropy values of hereditary classes of graphsDiscrete Mathematics and Applications, 1993
- Excluding induced subgraphs: quadrilateralsRandom Structures & Algorithms, 1991
- On the connection between chromatic number, maximal clique and minimal degree of a graphDiscrete Mathematics, 1974
- On a valence problem in extremal graph theoryDiscrete Mathematics, 1973
- On the structure of linear graphsBulletin of the American Mathematical Society, 1946