What is the furthest graph from a hereditary property?
What is the furthest graph from a hereditary property?
复制标题
距离遗传财产最远的图是什么？
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Uri Stav
中科院分区：
文献类型：
--
作者：
N. Alon;Uri Stav
对于一个图属性P，图G到P的编辑距离，记为EP(G)，是使图G变成一个满足P的图所需的最小边修改(增加或删除)的次数。从P到n个顶点的最远的图是什么，到P的最大可能编辑距离是多少？用ed(n，P)表示这个最大距离。这个问题是由算法边修改问题引起的，在这个问题中，人们希望找到或近似给定输入图G的EP(G)的值。单调图的性质在去除边和顶点的情况下是闭合的。平凡的是，对于任何单调性质，最大编辑距离是由完全图获得的。我们表明，这是一个更广泛现象的简单例子。遗传图的性质在顶点移除的情况下是封闭的。证明了对于任一遗传图性质P，边密度依赖于P的随机图本质上达到了与P的最大距离，即：ED(n，P)=EP(G(n，p(P)+o(N2)。这些证明结合了几种工具，包括Szemerédi正则性引理的强化版本，随机图的性质和概率论据。©2008威利期刊公司随机结构。高，2008年
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., 2008