Accumulation points of the edit distance function

DOI10.1016/J.DISC.2022.112857MaRDI QIDQ2138953zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 17 May 2022

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2107.06706

zbMATH Keywords

edit distancecolored regularity graphs

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75)

Abstract: Given a hereditary property $mathcalH$ of graphs and some $pin[0,1]$, the edit distance function $operatorname{ed}_{mathcalH}(p)$ is (asymptotically) the maximum proportion of "edits" (edge-additions plus edge-deletions) necessary to transform any graph of density $p$ into a member of $mathcalH$. For any fixed $pin[0,1]$, $operatorname{ed}_{mathcalH}(p)$ can be computed from an object known as a colored regularity graph (CRG). This paper is concerned with those points $pin[0,1]$ for which infinitely many CRGs are required to compute $operatorname{ed}_{mathcalH}$ on any open interval containing $p$; such a $p$ is called an accumulation point. We show that, as expected, $p=0$ and $p=1$ are indeed accumulation points for some hereditary properties; we additionally determine the slope of $operatorname{ed}_{mathcalH}$ at these two extreme points. Unexpectedly, we construct a hereditary property with an accumulation point at $p=1/4$. Finally, we derive a significant structural property about those CRGs which occur at accumulation points.

Recommendations

• On the edit distance function of the random graph
• The edit distance function and symmetrization
• On the computation of edit distance functions
• The edit distance in graphs: methods, results, and generalizations
• The maximum edit distance from hereditary graph properties

Cites work

• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 970795 (Why is no real title available?)
• Edit distance and its computation
• Extremal graphs and multigraphs with two weighted colours
• On the edit distance from \(K_{2,t}\)-free graphs
• On the edit distance function of the random graph
• On the structure of linear graphs
• The edit distance function and symmetrization
• The edit distance in graphs: methods, results, and generalizations
• The structure of hereditary properties and colourings of random graphs
• What is the furthest graph from a hereditary property?

Cited in

(1)

• On the edit distance function of the random graph

This page was built for publication: Accumulation points of the edit distance function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2138953)