What is the furthest graph from a hereditary property?

Noga Alon, Uri Stav

Research output: Contribution to journalArticle

13 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)87-104
Number of pages18
JournalRandom Structures and Algorithms
Volume33
Issue number1
DOIs
StatePublished - Aug 1 2008
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Keywords

  • Hereditary graph properties
  • Random graphs
  • Regularity lemma

Fingerprint Dive into the research topics of 'What is the furthest graph from a hereditary property?'. Together they form a unique fingerprint.

  • Cite this