论文标题
关于随机图的编辑距离函数
On the edit distance function of the random graph
论文作者
论文摘要
给定图形的遗传特性$ \ nathcal {h} $和a $ p \ in [0,1] $，编辑距离函数$ {\ rm ed} _ {\ nathcal {\ nathcal {h}}（p）$是无效的范围的最大比例，以确保Edge-Edge-Eddudies $ grapplied $ plagral $ pp $ pp $ pp $ pp $ pp $ $ \ MATHCAL {H} $。编辑距离函数与其他研究的数量直接相关，例如$ \ Mathcal {H} $的速度函数和$ \ Mathcal {H} $ - 随机图的色度数。令$ \ mathcal {h} $为禁止erdős-rényi随机图$ f \ sim \ mathbb {g}（n_0，p_0）$的属性，然后让$φ$代表黄金比率。在本文中，我们表明，如果$ p_0 \在[1-1/φ，1/φ] $中，则为A.A.S。作为$ n_0 \ to \ infty $， \ begin {align*} {\ rm ed} _ {\ Mathcal {h}}（p）=（1+o（1））\，\ frac {2 \ log n_0} {n_0} \ cdot \ min \ left \ { \ frac {p} { - \ log（1-p_0）}， \ frac {1-p} { - \ log p_0} \正确的\}。 此外，\ end {align*}此外，对于任何$ p_0 \ in（0,1）$，它适用于[1/3,2/3] $中的$ p \。
Given a hereditary property of graphs $\mathcal{H}$ and a $p\in [0,1]$, the edit distance function ${\rm ed}_{\mathcal{H}}(p)$ is asymptotically the maximum proportion of edge-additions plus edge-deletions applied to a graph of edge density $p$ sufficient to ensure that the resulting graph satisfies $\mathcal{H}$. The edit distance function is directly related to other well-studied quantities such as the speed function for $\mathcal{H}$ and the $\mathcal{H}$-chromatic number of a random graph. Let $\mathcal{H}$ be the property of forbidding an Erdős-Rényi random graph $F\sim \mathbb{G}(n_0,p_0)$, and let $φ$ represent the golden ratio. In this paper, we show that if $p_0\in [1-1/φ,1/φ]$, then a.a.s. as $n_0\to\infty$, \begin{align*} {\rm ed}_{\mathcal{H}}(p) = (1+o(1))\,\frac{2\log n_0}{n_0} \cdot\min\left\{ \frac{p}{-\log(1-p_0)}, \frac{1-p}{-\log p_0} \right\}. \end{align*} Moreover, this holds for $p\in [1/3,2/3]$ for any $p_0\in (0,1)$.
