×

What is the furthest graph from a hereditary property? (English) Zbl 1146.05046

Summary: For a graph property \(\mathcal P\), the edit distance of a graph \(G\) from \(\mathcal P\), denoted \(E_{\mathcal P}(G)\), is the minimum number of edge modifications (additions or deletions) one needs to apply to \(G\) to turn it into a graph satisfying \(\mathcal P\). What is the furthest graph on \(n\) vertices from \(\mathcal P\) and what is the largest possible edit distance from \(\mathcal P\)? Denote this maximal distance by \(ed(n,\mathcal P)\). This question is motivated by algorithmic edge-modification problems, in which one wishes to find or approximate the value of \(E_{\mathcal P}(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 \(\mathcal P\), a random graph with an edge density that depends on \(\mathcal P\) essentially achieves the maximal distance from \(\mathcal P\), that is: \(ed(n,\mathcal P) = E_{\mathcal P}(G(n,p(\mathcal P))) + o(n^{2})\) with high probability. The proofs combine several tools, including strengthened versions of the Szemerédi regularity lemma, properties of random graphs and probabilistic arguments.

MSC:

05C99 Graph theory
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alekseev, Discrete Math Appl 3 pp 191– (1993)
[2] , , , and , Efficient testing of large graphs, Proc 40th IEEE Symp Foundations of Computer Science, 1999, pp. 656–666.
[3] Also: Combinatorica 20 (2000), 451.
[4] , and , A characterization of the (natural) graph properties testable with one-sided error, Proc 46th IEEE Symp Foundations of Computer Science, 2005, pp. 429–438.
[5] , , and , Additive approximation for edge-deletion problems, Proc 46th IEEE Symp Foundations of Computer Science, 2005, pp. 419–428.
[6] , and , The probabilistic method, 2nd edition, Wiley, New York, 2000. · doi:10.1002/0471722154
[7] Alon, J Combin Theory Ser B
[8] Andrásfai, Discrete Math 8 pp 205– (1974)
[9] Axenovich, J Graph Theory
[10] Balogh, J Combin Theory Ser B 79 pp 131– (2000)
[11] Balogh, Eur J Combin 22 pp 277– (2001)
[12] Bollobás, Bull London Math Soc 27 pp 417– (1995)
[13] , and , ”Hereditary and monotone properties of graphs,” The Mathematics of Paul Erdos II, and (Editors), Algorithms and Combinatorics 14, Springer-Verlag, Berlin, 1997, pp. 70–78.
[14] Bollobás, Combinatorica 20 pp 173– (2000)
[15] , , , , , and , Graph limits and parameter testing, Proc 38th ACM STOC, 2006, pp. 261–270. · Zbl 1301.68199
[16] Borgs, metric properties and testing
[17] Erdos, Studia Sci Math Hungar 1 pp 51– (1966)
[18] Erdos, Discrete Math 5 pp 323– (1973)
[19] Erdos, Bull Amer Math Soc 52 pp 1087– (1946)
[20] , and , ”Szemerédi’s regularity lemma and its applications in graph theory,” Combinatorics, Paul Erdos is Eighty, Vol. II, , , and (Editors), János Bolyai Math Soc, Budapest, 1996, pp. 295–352. · Zbl 0851.05065
[21] , and , Testing properties of graphs and functions (in press).
[22] Prömel, Random Structures Algorithms 2 pp 55– (1991)
[23] Prömel, Discrete Appl Math 44 pp 283– (1993)
[24] Prömel, Random Structures Algorithms 3 pp 19– (1992)
[25] Scheinerman, J Combin Theory Ser B 61 pp 16– (1994)
[26] , ”Regular partitions of graphs,” Proc Colloque Int CNRS, , , , and (editors), Paris, 1978, pp. 399–401.
[27] Turán, Mat Fiz Lapok 48 pp 436– (1941)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.