2.1. Background on CRGs

The key element to studying the edit distance problem is the coloured regularity graph, which was defined by Alon and Stav [Reference Alon and Stav2] but appeared as types in the prior literature by Bollobás and Thomason (see [Reference Bollobás and Thomason6]).

CRGs approximate large graphs and we want to know whether a forbidden graph F is in a graph approximated by a given CRG. We express this in terms of embeddings of graphs into CRGs.

For any CRG K, we will treat the elements of ${\mathbb{R}}^{V(K)}$ both as functions on V(K) and as vectors indexed by the vertices of K. For any two such ${\bf x},{\bf y}\in {\mathbb{R}}^{V(K)}$ , we define $\langle {\bf x},{\bf y}\rangle \,:\!=\, \sum_{u\in V(K)}{\bf x}(u){\bf y}(u)$ . We also let $M_K(p)\in{\mathbb{R}}^{V(K)\times V(K)}$ be the matrix whose uv-th entry is

(5) \begin{equation} m_{uv} \,:\!=\, \left\{\begin{array}{rl} p, &\mbox{$u\neq v$ and $uv\in {\textrm{EW}}(K)$, or $u=v$ and $u\in {\textrm{VW}}(K)$;} \\ 1-p, &\mbox{$u\neq v$ and $uv\in {{\textrm{EB}}}(K)$, or $u=v$ and $u\in {\textrm{VB}}(K)$;} \\ 0, &\mbox{$u\neq v$ and $uv\in{{\textrm{EG}}}(K)$.} \end{array} \right.\end{equation}

The all-ones vector ${\bf 1}\in{\mathbb{R}}^{V(K)}$ is defined by ${\bf 1}(u) = 1$ for all $u\in V(K)$ and the all-zeroes vector is just ${\bf 0} = 0\cdot {\bf 1}$ . Furthermore, we let $\Delta_K$ be the standard simplex associated to K which consists of all ${\bf x}\in{\mathbb{R}}^{V(K)}$ so that ${\bf x}\geq{\bf 0}$ in the component-wise sense and $\langle {\bf x}, {\bf 1}\rangle = 1$ . The elements of $\Delta_K$ will be called weight vectors.

Now define

\begin{align*} g_K(p,{\bf x}) &\,:\!=\, \langle {\bf x},M_K(p){\bf x}\rangle\text{ and }\\ g_K(p) &\,:\!=\, \min\left\{g_K(p,{\bf x}) \,:\, {\bf x}\in\Delta_K\right\}.\end{align*}

A weight vector ${\bf x}\in\Delta_K$ is said to be optimal for K if $g_K(p,{\bf x}) = g_K(p)$ . For any $p\in [0,1]$ , a CRG K is said to be p-core if for any optimal weight vector x, ${\bf x}(u) > 0$ for all $u\in V(K)$ . It follows that for K a p-core CRG, there exists a unique optimal weight vector.

For any hereditary property ${\mathcal{H}} = {\textrm{Forb}}({\mathcal{F}})$ we define the following family of CRGs:

\begin{align*} {\mathcal{K}}_{\mathcal{H}} \,:\!=\, \{K\text{ a CRG} \,:\, F\not\mapsto K\text{ for all }F\in{\mathcal{F}}\}.\end{align*}

Theorem 10 is the main technique for computing ${\textrm{ed}}_{\mathcal{H}}(p)$ , hence understanding the set ${\mathcal{K}}_{\mathcal{H}}$ is crucial to understanding ${\textrm{ed}}_{\mathcal{H}}(p)$ . The first equality was given by Balogh and Martin [Reference Balogh and Martin4] and the second by Marchant and Thomason [Reference Marchant and Thomason10].

Theorem 10. Let ${\mathcal{H}}$ be a non-trivial hereditary property. Then for all $p\in [0,1]$ ,

(6) \begin{equation} {\textrm{ed}}_{\mathcal{H}}(p) = \inf_{K\in{\mathcal{K}}_{\mathcal{H}}}g_K(p) = \min_{K\in{\mathcal{K}}_{\mathcal{H}}} g_K(p). \end{equation}

It follows by definition that the minimum in Theorem 10 is obtained by a p-core CRG and as Theorem 11 shows, p-core CRGs have a well-defined structure.

To summarize, if $p\leq 1/2$ , then a p-core CRG has no black edges and all white edges must be between black vertices. If $p\geq 1/2$ , then a p-core CRG has no white edges and all black edges must be between white vertices. As a result, if $p=1/2$ , p-core CRGs have neither black nor white edges.

2.2. p-prohibited CRGs

In this paper, we introduce the notion of a prohibited CRG.

For example, Theorem 11 shows that if $p\in [0,1/2)$ , then the only 2-vertex CRGs that are not p-prohibited are those with a grey edge or the CRG with two black vertices and a white edge. See Figure 1.

Figure 1. All two-vertex CRGs. The five on the left are p-prohibited for all $p\in [0,1/2]$ . The four on the right are p-core for all $p\in [0,1/2)$ .

We also want to introduce the notion of the complement of a CRG.

For a graph G, the notation is $G^c$ is used to denote the graph complement, so as to avoid confusion. There is symmetry in the edit distance function about $p=1/2$ with respect to complements.

Proof. This follows from the equality of the matrices $M_K(p)=M_{\overline{K}}(1-p)$ :

\begin{align*} g_K(p) &= \min\left\{\langle {\bf x},M_K(p){\bf x}\rangle \,:\, {\bf x}\in\Delta_K\right\} \\&= \min\left\{\langle {\bf x},M_{\overline{K}}(1-p){\bf x}\rangle \,:\, {\bf x}\in\Delta_K\right\} = g_{\overline{K}}(1-p) . \end{align*}

There is also symmetry in the edit distance function about $p=1/2$ when it comes to p-prohibition.

Proof. Suppose J is p-prohibited but $\overline{J}$ is not $(1-p)$ -prohibited. Then, there is a $(1-p)$ -core CRG $\overline{K}$ that contains $\overline{J}$ as a sub-CRG. If K is not p-core, then there is a $K'\subseteq K$ such that $g_{K'}(p)=g_K(p)$ , but Proposition 16 gives that $g_{\overline{K'}}(1-p)=g_{\overline{K}}(1-p)$ , a contradiction to $\overline{K}$ being $(1-p)$ -core.

Next, we introduce terminology which is useful in describing the structure of p-core and p-prohibited CRGs.

We associate CRGs to graphs for the purposes of discussing p-core CRGs. See Figure 2 for an example. Since $1/2$ -core CRGs are precisely those which have only grey edges, the definition of the CRG associated to a graph for $p=1/2$ is made purely out of convenience.

Figure 2. A CRG with five components. One component is the CRG associated to the cycle $C_4$ for $p\in [0,1/2)$ . The edges satisfy the necessary conditions from Theorem 11 for a p-core CRG with $p\in [0,1/2)$ .

In order to apply Lemma 20 below, we need the minimum adjacency eigenvalue to be at most $-1$ . This occurs for all non-empty graphs. See [Reference Brouwer and Haemers7] for a more detailed discussion about eigenvalues associated to graphs.

Lemma 20. Let G be a non-empty graph and let $\lambda\leq-1$ be the minimum eigenvalue of the adjacency matrix of G. The CRG associated to G is p-prohibited for all

\begin{align*} p\in \left[\dfrac{1}{1-\lambda},1-\dfrac{1}{1-\lambda}\right] . \end{align*}

In Section 2.3, we prove Lemma 20. First, we need some essential terms.

See Figure 3 for dalmatian CRGs of small order.

Figure 3. The dalmatian CRGs $D_\infty=\overline{D_1},\, D_1=\overline{D_{\infty}},D_2, D_3,$ and $D_4$ .

Remark 22. For all $p\in [0,1]$ and each $K\in {\mathcal{D}}_p$ , K is a p-core CRG. Moreover, if $p\in [0,1/2]$ , then $g_{D_\infty}(p)=p$ and for each positive integer t,

\begin{align*} g_{D_t}(p) = \min_{{\bf x}\in\Delta_{D_t}}\langle {\bf x}, M_{D_t}(p){\bf x}\rangle = \dfrac1{t^2}\langle {\bf 1}, M_{D_t}(p){\bf 1}\rangle = p + \dfrac{1-2p}{t} . \end{align*}

If $p\in [1/2,1]$ , then $g_{\overline{D_\infty}}(p)=1-p$ and for each positive integer t, $g_{\overline{D_t}}(p) = 1-p + \frac{2p-1}{t}$ .

In Theorem 23, we show that for all $p\in [1-\varphi^{-1},\varphi^{-1}]$ , the only p-core CRGs are those that belong to ${\mathcal{D}}_p$ .

In Section 2.4, we prove Theorem 23.

2.3. Proof of Lemma 20

The result from Theorem 25 below was originally shown by Sidorenko [Reference Sidorenko12] using different language and has appeared in several other forms throughout the study of hereditary properties. See [Reference Martin11] for a more detailed history. For convenience, we state it in the language of CRGs.

Theorem 25. Let K be a p-core CRG with optimal weight vector ${\bf x}\in\Delta_K$ . Then

\begin{align*} M_K(p)\,{\bf x} = g\,{\bf 1}. \end{align*}

So, Theorem 25 establishes that the optimal weight vector produces a weighting that is balanced.

Lemma 26. Let $0\leq p\leq 1$ and J be a CRG. If there exists a non-zero vector ${\boldsymbol{\delta}}\in{\mathbb{R}}^{V(J)}$ so that $\langle{\boldsymbol{\delta}},{\bf 1}\rangle=0$ and

(7) \begin{equation} \langle{\boldsymbol{\delta}}, M_J(p)\,{\boldsymbol{\delta}}\rangle \leq 0 , \end{equation}

then J is p-prohibited.

Proof. We proceed by contradiction. Suppose J is not p-prohibited and that there exists ${\boldsymbol{\delta}}$ as above. Then there exists a p-core CRG K containing J and we may let x denote the optimal weight vector for K. We extend ${\boldsymbol{\delta}}$ to a vector ${\boldsymbol{\delta}}'\in{\mathbb{R}}^{V(K)}$ by letting ${\boldsymbol{\delta}}'(u)\,:\!=\,0$ if $u\in V(K)\setminus V(J)$ and ${\boldsymbol{\delta}}'(u)\,:\!=\,{\boldsymbol{\delta}}(u)$ if $u\in V(J)$ . Note that $\langle{\boldsymbol{\delta}}',{\bf 1}\rangle=0$ .

Since x is the optimal weight vector for the p-core CRG K, ${\bf x}(u) > 0$ for all $u\in V(K)$ and it follows that there exists some $\varepsilon > 0$ so that ${\bf x}'\,:\!=\,{\bf x} + \varepsilon{\boldsymbol{\delta}}'$ lies in $\Delta_K$ and ${\bf x}'(u) = 0$ for some $u\in V(K)$ . By the definition of $g_K(p)$ , the fact that x is optimal, and Theorem 25,

\begin{align*} 0 &< g_K(p,{\bf x}') - g_K(p,{\bf x})\\ &= \langle {\bf x}+\varepsilon{\boldsymbol{\delta}}', M_K(p)({\bf x}+\varepsilon{\boldsymbol{\delta}}')\rangle - \langle {\bf x}, M_K(p){\bf x}\rangle\\ &= 2\varepsilon\langle {\boldsymbol{\delta}}, M_K(p){\bf x}\rangle + \varepsilon^2\langle {\boldsymbol{\delta}}', M_K(p){\boldsymbol{\delta}}'\rangle\\ &= 2\varepsilon\langle {\boldsymbol{\delta}}', g_K(p){\bf 1}\rangle + \varepsilon^2\langle {\boldsymbol{\delta}}, M_J(p){\boldsymbol{\delta}}\rangle\\ &= \varepsilon^2\langle {\boldsymbol{\delta}}, M_J(p){\boldsymbol{\delta}}\rangle \leq 0, \end{align*}

a contradiction to the assumption that J is not p-prohibited.

We include one more well-known fact about p-core CRGs.

Proposition 27 (See [Reference Martin11]). Let $K_1,\ldots,K_{\ell}$ be CRGs and let $K=K_1\oplus\cdots\oplus K_{\ell}$ . Then for all $p\in [0,1]$ ,

(8) \begin{equation} g_{K}(p)^{-1} = \sum_{i=1}^{\ell} g_{K_i}(p)^{-1} . \end{equation}

In particular, K is p-core if and only if each of $K_1,\ldots,K_{\ell}$ are p-core.

Proof. To prove the forward implication, if J is p-prohibited, then no p-core CRG can contain $k\cdot J$ because it would contain J. To prove the reverse implication, if J is not p-prohibited then there exists a p-core CRG, L, containing J. Then $J\oplus K$ is contained in $L\oplus K$ , which is p-core by Proposition 27, as desired.

With the primary tools of Lemmas 26 and 28 established, we now proceed to prove Lemma 20 itself.

Let J be the CRG associated to a non-empty graph G. If $p=1/2$ , then by Theorem 11, J is $1/2$ -prohibited if and only if J has an edge that is not grey. Thus, any non-empty G gives that J is $1/2$ -prohibited, settling the case where $p=1/2$ .

Now suppose $p\in (0,1/2)$ . Write A for the adjacency matrix of G and suppose $A{\bf x} = \lambda {\bf x}$ for some unit vector x where $\lambda$ is the minimum eigenvalue of A. Then J is the the CRG on V(G) with all vertices black, and where edge uv is white if $uv\in E(G)$ , and uv is grey if $uv\in E(G^c)$ . So $M_J(p) = (1-p)I + pA$ .

For convenience, we write $V_1$ and $V_2$ for the vertex sets in $2\cdot J$ corresponding to each copy of J. Let ${\boldsymbol{\delta}}\in{\mathbb{R}}^{V(2\cdot J)}$ be defined by

\begin{align*} {\boldsymbol{\delta}}(u) \,:\!=\, \left\{ \begin{array}{rl} {\bf x}(u), & u\in V_1; \\ -{\bf x}(u), & u\in V_2 . \end{array}\right.\end{align*}

By definition, $\langle {\bf 1}, {\boldsymbol{\delta}}\rangle = 0$ . Moreover note that

\begin{align*} \langle{\boldsymbol{\delta}}, M_{2\cdot J}(p){\boldsymbol{\delta}}\rangle &= \langle {\bf x}, M_J(p){\bf x} \rangle + \langle -{\bf x}, M_J(p)(-{\bf x}) \rangle \\ &= 2 \langle {\bf x}, M_J(p){\bf x} \rangle \\ &= 2 \langle {\bf x}, ((1-p)I+pA){\bf x} \rangle \\ &= 2(1-p) \langle {\bf x}, I{\bf x} \rangle + 2p \langle {\bf x}, A{\bf x} \rangle \\ &= 2(1-p) \langle {\bf x}, {\bf x} \rangle + 2p \lambda \langle {\bf x}, {\bf x} \rangle \\ &= 2\cdot(1-(1-\lambda)p) \cdot \langle {\bf x}, {\bf x} \rangle.\end{align*}

If $p\geq 1/(1-\lambda)$ , then $\langle{\boldsymbol{\delta}}, M_{2\cdot J}(p){\boldsymbol{\delta}}\rangle\leq 0$ . By Lemma 26, the CRG $2\cdot J$ is p-prohibited and by Lemma 28, J itself is p-prohibited. This settles the case where $p\in (0,1/2)$ .

Finally, for the case of $p\in (1/2,1)$ , Proposition 17 gives that J is p-prohibited if and only if J is $(1-p)$ -prohibited. This concludes the proof of Lemma 20.

2.4. Proof of Theorem 23

Lemma 29 below is a result in pure graph theory that is reminiscent of the theorem that categorizes $\{P_4,C_4,C_4^c\}$ -free graphs as threshold graphs. A dominant vertex in a graph is one for which every other vertex is its neighbour.

Proof. Let u be a vertex of G which attains the maximum degree $\Delta=\Delta(G)$ and let $A\,:\!=\,N_G(u)$ and $B\,:\!=\,V(G)\setminus(A\cup\{u\})$ . If $B = \emptyset$ , then u is the desired vertex, so we assume otherwise. Let $w\in B$ . Since G avoids induced $P_4$ -s, connectivity implies G has diameter at most 2.

In particular, ${\textrm{dist}}_G(u,w) = 2$ , so there exists some vertex $v\in A$ so that uvw is an induced path on 3 vertices. Let $v'\in A\setminus\{v\}$ . Note that v ^′ uvw is a path on 4 vertices but since it cannot be induced and cannot form an induced $C_4$ , either $uw\in E(G)$ or $vv'\in E(G)$ . However, $uw\notin E(G)$ because ${\textrm{dist}}_G(u,w)=2$ . Thus, it follows that $vv'\in E(G)$ . So v is adjacent to $\{u,w\}\cup (A\setminus\{v\})$ and has degree at least $\Delta+1$ , a contradiction.

Lemma 29 yields a very strong structural theorem on CRGs, Lemma 30. Recall the definition of the underlying graph of CRG, K, in Definition 18: the graph whose vertices are the vertices of K and whose edges are the non-grey edges of K.

Proof. If $p=1/2$ , then as we saw in Remark 12, a p-core CRG has only grey edges and so the underlying graph is empty.

Let $p\in [1/3,1/2)$ . Every trivial component of the underlying graph is simply a vertex in the CRG. Let K be a non-trivial component of the CRG. By Theorem 11, the vertices of K must be black and by Lemma 29, the underlying graph of K has a dominant vertex u.

Let ${\bf x}\in\Delta_K$ be the optimal weight vector for K and define $g \,:\!=\, g_K(p)$ . By Theorem 25, $M_K(p){\bf x} = g{\bf 1}$ and by inspecting the entry indexed by u,

\begin{align*} g = (1-p){\bf x}(u) + p\cdot\sum_{u\neq v\in V(K)}{\bf x}(v) = p + (1-2p){\bf x}(u) > p. \end{align*}

For a contradiction, we now suppose K is not a dalmatian CRG. Hence, there exists some grey edge vw, and the sub-CRG K ^′ on v and w is the disjoint union of two black vertices. Since K is p-core,

\begin{align*} g < g_{K'}(p) = \min_{{\bf y}\in \Delta_{K'}}(1-p)({\bf y}(v)^2+{\bf y}(w)^2) = \dfrac{1-p}{2}. \end{align*}

Altogether, $p<g<(1-p)/2$ which implies that $p < 1/3$ , a contradiction.

The case where $p\in (1/2,2/3]$ follows by symmetry.

We now prove Theorem 23 itself with the primary tool being Lemma 30. As mentioned in Remark 14, we leave it as an exercise to verify that the CRG associated with $P_4$ is p-core for $p\in (0,1-\varphi^{-1})\cup (\varphi^{-1},1)$ . Hence, $P_3$ is not p-prohibited in this range, proving the forward implication.

For the reverse implication, let $p\in [1-\varphi^{-1},\varphi^{-1}]$ . Since the minimum eigenvalues of the adjacency matrices of $C_4$ and $P_4$ are $-2$ and $-\varphi^{-1}$ respectively, Lemma 20 implies that the CRGs associated with $C_4$ and $P_4$ are p-prohibited for $p\in [1-\varphi^{-1},\varphi^{-1}]$ .

Suppose K is a p-core CRG. Since $p\in [1/3,2/3]$ , it follows from Lemma 30 that the components of the underlying graph of K are cliques. No such graph contains an induced $P_3$ and so $P_3$ is p-prohibited for all $p\in [1-\varphi^{-1},\varphi^{-1}]$ , as desired.

For the second statement of the theorem, since $P_3$ is p-prohibited, the only underlying graphs of a p-core CRG can be disjoint cliques, which is exactly the condition of being in ${\mathcal{D}}_p$ . As observed in Remark 22, all CRGs in ${\mathcal{D}}_p$ are p-core. This concludes the proof of Theorem 23.

3.1. Trimming p-core CRGs

The main result in this subsection is Lemma 31, which establishes that, for $p\in(1/3,2/3)$ , a CRG has a sub-CRG with bounded component sizes and a negligible change in the value of the g-function.

The first part of the proof is to remove vertices from a CRG K one-by-one in a way which does not affect $g_K(p)$ too much. Once enough vertices are removed, we show that each remaining vertex is incident to a bounded number of non-grey edges. Finally, we use Lemma 20 to bound the diameter of p-core CRGs on the interval $p\in (1/3,2/3)$ . The underlying graph has bounded degree and diameter, thus its connected components have bounded order.

The proof consists of a sequence of propositions:

Proposition 32. Fix $p\in [0,1]$ and suppose K is a p-core CRG with least two vertices. If ${\bf x}\in\Delta_K$ is the optimal weight vector for K, i.e., $g = g_K(p) = g_K(p,{\bf x})$ , then for all $u\in V(K)$ ,

\begin{align*} g_{K\setminus\{u\}}(p) \leq g + \dfrac{{\bf x}(u)^2}{(1-{\bf x}(u))^2}. \end{align*}

Proof. Let $K'\,:\!=\,K\setminus\{u\}$ . Since K is p-core with at least two vertices, ${\bf x}(u)<1$ and we may define ${\bf x}'\in\Delta_K$ by

\begin{align*} {\bf x}'(v)\,:\!=\,\left\{\begin{array}{ll} 0, &v=u\\[4pt] \dfrac{{\bf x}(v)}{1-{\bf x}(u)}, &\text{otherwise} \end{array}\right. . \end{align*}

In other words, if ${\bf e}_u\in{\mathbb{R}}^{V(K)}$ is the indicator vector for the vertex u, then $(1-{\bf x}(u)){\bf x}' = {\bf x} - {\bf x}(u){\bf e}_u$ . Recall that $M_K(p)$ denotes the weighted adjacency matrix of K. By Theorem 25, $M_K(p){\bf x} = g{\bf 1}$ and so

\begin{align*} (1-{\bf x}(u))^2\langle {\bf x}', M_K(p){\bf x}'\rangle &= \langle {\bf x}-{\bf x}(u){\bf e}_u, M_K(p)( {\bf x}-{\bf x}(u){\bf e}_u )\rangle \\ &= \langle {\bf x},g{\bf 1}\rangle - 2{\bf x}(u)\langle {\bf e}_u, g{\bf 1}\rangle + {\bf x}(u)^2\langle {\bf e}_u, M_K(p){\bf e}_u\rangle\\ &\leq g - 2g\,{\bf x}(u) + {\bf x}(u)^2. \end{align*}

By definition of $g_{K'}(p)$ and since ${\bf x}'(u) = 0$ ,

\begin{align*} g_{K'}(p) &\leq g_K(p,{\bf x}') \\ &= \dfrac{\langle {\bf x}', M_K(p){\bf x}'\rangle}{(1-{\bf x}(u))^2} \\ &= \dfrac{g - 2g\,{\bf x}(u)+{\bf x}(u)^2}{(1-{\bf x}(u))^2} \\ &= g + \dfrac{(1 - g){\bf x}(u)^2}{(1-{\bf x}(u))^2}\\ &\leq g+\dfrac{{\bf x}(u)^2}{(1-{\bf x}(u))^2}, \end{align*}

which completes the proof.

Proof. Define a finite sequence of sub-CRGs

\begin{align*} K = K_0\supset K_1\supset\cdots \supset K_\ell, \end{align*}

as follows: First let $K\,:\!=\,K_0$ and $g_0 \,:\!=\, g_K(p)$ . For any $k\geq 0$ so that $|V(K_k)| \geq 2$ , do the following:

1. (i) Let ${\bf x}_k\in\Delta_{K_k}$ be the optimal weight vector for $K_k$ , i.e., $g_{K_k}(p,{\bf x}_k) = g_{K_k}(p)$ .

2. (ii) Let $u_k\in V(K_k)$ so that ${\bf x}_k(u_k) = \min\left\{{\bf x}_k(v) \,:\, v\in V(K_k)\right\}$ .

3. (iii) Let $K_{k+1}$ be any p-core sub-CRG of $K_k\setminus\{u_k\}$ .

Since each step removes at least one vertex, $\ell\leq|V(K)|$ . For each $k\in\{0,\ldots,\ell\}$ , denote $g_k\,:\!=\,g_{K_k}(p)$ .

Let $a\in\{0,\ldots,\ell\}$ be the minimum index a so that $|V(K_a)| \leq 4/(\varepsilon g)$ . By the definition of a and by the fact that $\varepsilon,g < 1$ ,

\begin{align*} {\bf x}_k(u_k) \leq 1/|V(K_k)| \leq (\varepsilon g)/4 \leq 1/4, \end{align*}

for all $k\in\{0,\ldots,a-1\}$ . By Proposition 32,

\begin{align*} g_{k+1} \leq g_k + \dfrac{{\bf x}_k(u_k)^2}{(1-{\bf x}_k(u_k))^2} \leq g_k + \dfrac{{\bf x}_k(u_k)^2}{(3/4)^2} < g_k + \dfrac{2}{|V(K_k)|^2}. \end{align*}

Because $|V(K_k)| \geq |V(K_{a-1})| + (a-1-k)$ for all $k\in\{0,\ldots,a-1\}$ ,

\begin{align*} g_a &< g + \sum_{ k=0 }^{ a-1 }\dfrac{2}{|V(K_k)|^2} \\[3pt] &\leq g + \sum_{ k=0 }^{ a-1 }\dfrac{2}{\left(|V(K_{a-1})| + (a-1-k)\right)^2} \\[3pt] &< g + \sum_{i = |V(K_{a-1})|}^\infty\dfrac{2}{i^2} \\[3pt] &< g + \int_{i = |V(K_{a-1})|-1}^\infty \dfrac{2}{x^2} \, dx \\[3pt] &= g + \frac{2}{|V(K_{a-1})|-1} \\[3pt] &\leq g + \frac{2}{\lfloor 4/(\varepsilon g)\rfloor} . \end{align*}

Since $\varepsilon g < 1$ , it is the case that $\lfloor 4/(\varepsilon g)\rfloor > 2/(\varepsilon g)$ . Consequently,

(10) \begin{align} g_a \leq (1 + \varepsilon) g . \end{align}

Let b be the least index $a\leq b\leq \ell$ so that ${\bf x}_b(u)\geq \varepsilon g$ for all $u\in V(K_b)$ . Note that b is well defined since ${\bf x}_{\ell}(u) = 1 > \varepsilon g$ where ${\bf x}_{\ell}$ is the optimal weighting for $K_\ell$ , a CRG with a single vertex. For any $k\in\{a,\ldots,b-1\}$ , it is the case that ${\bf x}_k(u_k) < \varepsilon g$ and that ${\bf x}_k(u_k) \leq 1/|V(K_k)|\leq 1/2$ and again by Proposition 32,

\begin{align*} g_{k+1} \leq g_k + \dfrac{{\bf x}_k(u_k)^2}{(1-{\bf x}_k(u_k))^2} < g_k + \dfrac{(\varepsilon g)^2}{(1/2)^2} = g_k + 4\varepsilon^2g^2. \end{align*}

Finally by (10) and since $b-a\leq |V(K_a)|\leq 4/(\varepsilon g)$ ,

\begin{align*} g_b \leq g_a + \sum_{ k=a }^{b-1}4\varepsilon^2g^2 \leq (1+\varepsilon)g + |V(K_a)|\cdot 4\varepsilon^2g^2 \leq (1+17\varepsilon)g. \end{align*}

Letting $K'\,:\!=\,K_b$ , we have the desired sub-CRG.

Proposition 34 below implies that we can decrease the degree of the underlying graph of a CRG K without changing $g_K(p)$ too much.

Proof. We prove the claim for a fixed $p\in (0,1/2]$ . By duality (that is, by replacing K with $\overline{K}$ and p with $1-p$ ) the claim holds also for all $p\in [1/2,1)$ . For ease of notation, let $g=g_K(p)$ .

By Proposition 33 applied to K and $\varepsilon/17$ , there exists a sub-CRG K ^′ of K so that $g_{K'}(p)\leq (1+\varepsilon)g$ and whose optimal weight vector ${\bf x}\in\Delta_{K'}$ has ${\bf x}(u)\geq \varepsilon g/17$ for all $u\in V(K')$ . Let $g'=g_{K'}(p)$ .

By Theorem 11, the white vertices of K ^′ are incident to no white or black edges. So it suffices to prove the desired inequality for black vertices. Suppose $u\in {\textrm{VB}}(K')$ . By Theorem 25, $M_{K'}(p){\bf x} = g'{\bf 1}$ and it follows that

\begin{align*} \dfrac{(1+\varepsilon)g}{p} > \dfrac{g'}{p} - \dfrac{1-p}p\,{\bf x}(u) = \sum_{uv\in{\textrm{EW}}(K')}{\bf x}(v) \geq \dfrac{\varepsilon g}{17}\cdot \left|\{v \,:\, uv\in{\textrm{EW}}(K')\}\right| . \end{align*}

So the number of vertices adjacent to a vertex via a non-grey edge is at most $17(1+\varepsilon)/(\varepsilon p)\leq 34/(\varepsilon p)$ , as desired.

Next, we uniformly bound the diameter of all p-core CRGs, for each $p\in (1/3,2/3)$ .

Proposition 35. For all positive integers d, the CRG associated to the path $P_d$ on d vertices is p-prohibited for all

(11) \begin{align} p\in \left[\dfrac{1}{1+2\cos(\pi/(d+1))}, 1-\dfrac{1}{1+2\cos(\pi/(d+1))}\right]. \end{align}

Proof. It is a well-known fact from spectral graph theory that the spectrum of the adjacency matrix of $P_d$ , the path on d vertices is the multiset $\left\{2\cos\left(\frac{\pi k}{d+1}\right) \,:\, k\in\left\{1,\ldots,d\right\}\right\}$ . See, for example, [Reference Cvetković, Rowlinson and Simić8]. In particular, the minimum such eigenvalue is $-2\cos(\pi/(d+1))$ . Lemma 20 gives that $P_d$ is p-prohibited for p in the stated range.

Finally, we prove Lemma 31.

Proof of Lemma 31. Since the sequence $\left\{\frac{1}{1+2\cos(\pi/(d+1))}\right\}$ is monotone decreasing and converges to $1/3$ , there exists a positive integer $d = d_p$ so that $P_d$ is p-prohibited. Let K ^′ be the sub-CRG from Proposition 34 and write G for its underlying graph. Then by construction, G has degree at most

\begin{align*} D = 34\varepsilon^{-1}\cdot \max\left\{ \dfrac1p, \dfrac1{1-p} \right\}. \end{align*}

Let C be any component of G. Since $P_d$ is p-prohibited, C has diameter at most $d-1$ . It follows that

\begin{align*} |C| \leq 1 + D + D(D-1)+\cdots+D(D-1)^{d-1} \,=\!:\, B(p,\varepsilon), \end{align*}

as desired.

3.2. Forbidding a random graph

Now we proceed to prove our main result, Theorem 4. First, recall that Theorem 7 says that if $F'\sim{\mathbb{G}}(n^{\prime}_0,p_0)$ then a.a.s.,

\begin{align*} \chi_{\mathcal{H}}(F') = (1+o(1))\,c_{\mathcal{H}}(p_0)\,\dfrac{n^{\prime}_0}{2\log_2n^{\prime}_0}.\end{align*}

This is useful because in the proof of Lemma 37, we repeatedly decompose induced subgraphs of a random graph of order $n_0\gg n^{\prime}_0$ . An essential tool is the following, which is a restatement of Theorem 4.4 from [13]. Recall from (9) that $p^*=\frac{\log (1-p_0)}{\log(p_0(1-p_0))}$ .

Lemma 36 (Thomason [13]). Let K be a CRG and define ${\mathcal{H}}$ to be the hereditary property of graphs, G, such that $G\mapsto K$ . For all $p_0\in (0,1)$ ,

\begin{align*} c_{\mathcal{H}}(p_0) = -\log_2(p_0(1-p_0)) \cdot g_K\left(p^*\right) . \end{align*}

Lemma 37. Let $p_0$ and $\varepsilon$ be fixed such that $p_0\in (0,1)$ and $\varepsilon\in (0,1)$ . Moreover, fix ${\mathcal{B}}$ to be a finite set of CRGs. If $F\sim{\mathbb{G}}(n_0,p_0)$ , the following holds a.a.s. as $n_0\to\infty$ : For all CRGs K such that all components of K lie in ${\mathcal{B}}$ and $F\not\mapsto K$ , then

(12) \begin{align} (1+\varepsilon)\, g_{K}\left(p^*\right) \geq\dfrac{2\log n_0}{-\log(p_0(1-p_0))\cdot n_0} . \end{align}

Proof. For any function $\mu\,:\,{\mathcal{B}}\to\{0,1,\dots\}$ , define the CRG, $K_{\mu}$ as follows:

\begin{align*} K_\mu \,:\!=\, \bigoplus_{B\in{\mathcal{B}}}\mu(B)\cdot B. \end{align*}

That is, $K_{\mu}$ consists of a disjoint union of $\mu(B)$ copies of B, for all $B\in{\mathcal{B}}$ . For any induced subgraph G of the random graph $F\sim{\mathbb{G}}(n_0,p_0)$ and any CRG K, we will denote the event that G embeds into K by $[G\mapsto K]$ . Additionally, let

\begin{align*} E_{\mu} \,:\!=\, [F\mapsto K_\mu]. \end{align*}

Let

\begin{align*} {\mathcal{B}}_0 \,:\!=\, \left\{ \mu\,:\,{\mathcal{B}}\to\{0,1,\dots\} \,:\, (1+\varepsilon) g_{K_\mu}(p^*) < \dfrac{2\log n_0} {-\log(p_0(1-p_0))\cdot n_0} \right\}. \end{align*}

To prove the desired claim, it is equivalent to show that the probability that $F\not\mapsto K_{\mu}$ for all $\mu\in{\mathcal{B}}_0$ goes to zero. That is,

(13) \begin{align} \lim_{n_0\to\infty} {\mathbb{P}}\left[ \bigcup_{\mu\in{\mathcal{B}}_0} \overline{E_{\mu}} \right] = 0. \end{align}

Recall $F\sim{\mathbb{G}}(n_0,p_0)$ . We will partition V(F) by setting

\begin{align*} C \,:\!=\, \left\lceil 2|{\mathcal{B}}|\cdot \dfrac{1+\varepsilon/2}{\varepsilon/2}\right\rceil, \end{align*}

and let $I_1,\ldots,I_C$ be an equipartition of V(F), i.e., $|I_k|\in\{\lfloor n_0/C\rfloor,\lceil n_0/C\rceil\}$ for $k\in \{1,\ldots,C\}$ . Let $n^{\prime}_0=\lceil n_0/C\rceil$ .

For any $B\in{\mathcal{B}}$ , set

\begin{align*} m_B \,:\!=\, \left\lfloor \dfrac{(1+\varepsilon/2)\cdot (n_0/C) \cdot \left(-\log(p_0(1-p_0))\right) \cdot g_B(p^*)}{2\log (n_0/C)} \right\rfloor . \end{align*}

We expect to be able to $(m_B\cdot B)$ -colour a ${\mathbb{G}}(n^{\prime}_0, p_0)$ graph (hence a ${\mathbb{G}}(n^{\prime}_0-1, p_0)$ graph as well). Now for any $k\in\{1,\ldots,C\}$ and any $B\in{\mathcal{B}}$ , we define the event

\begin{align*} E_{k,B} \,:\!=\, [F[I_k]\mapsto m_B\cdot B] . \end{align*}

In other words, $E_{k,B}$ is the event that the subgraph of F that is induced by vertices in $I_k$ is colourable by $m_B$ copies of the CRG B.

The induced subgraphs $F[I_1],\dots,F[I_C]$ are each independently sampled according to the Erdős–Rényi random graph model ${\mathbb{G}}(n^{\prime}_0,p_0)$ . Moreover, the number of events of the form $E_{k,B}$ is equal to $C\cdot |{\mathcal{B}}|$ , which is bounded as a function of the constants $\varepsilon$ and $|\mathcal{B}|$ .

For any $K\in{\mathcal{B}}$ , the property of all graphs G such that $G\mapsto K$ is not satisfied by all graphs. Then by Theorem 7 and Lemma 36, since the number of vertices in each $I_k$ uniformly tends to $\infty$ ,

(14) \begin{align} \lim_{n_0\to\infty} {\mathbb{P}}\left[\bigcup_{k\in\{1,\ldots,C\}} \bigcup_{B\in{\mathcal{B}}} \overline{E_{k,B}}\right] = 0. \end{align}

It suffices to show that

\begin{align*} \bigcup_{\mu\in{\mathcal{B}}_0} \overline{E_{\mu}} \subseteq \bigcup_{k\in\{1,\ldots,C\}} \bigcup_{B\in{\mathcal{B}}} \overline{E_{k,B}} , \end{align*}

because then (14) will imply (13) and complete the proof.

Indeed, suppose $\mu\in {\mathcal{B}}_0$ and suppose $\varphi_{k,B}$ are embeddings defined by the events $E_{k,B}$ , for all $k\in \{1,\ldots,C\}$ and all $B\in{\mathcal{B}}$ . Further, for any $B\in{\mathcal{B}}$ , let

\begin{align*} M_B \,:\!=\, \left\lfloor\dfrac{\mu(B)}{m_B}\right\rfloor . \end{align*}

We will show that if $\sum_{B\in{\mathcal{B}}} M_B\geq C$ , then F can be coloured by $M_B$ copies of $m_B\cdot B$ , over all $B\in{\mathcal{B}}$ , and so $F\mapsto K_{\mu}$ . We begin by summing the $M_B$ ’s.

\begin{align*} \sum_{B\in{\mathcal{B}}} M_B &= \sum_{B\in{\mathcal{B}}} \left\lfloor\dfrac{\mu(B)}{m_B}\right\rfloor\\ &\geq \sum_{B\in{\mathcal{B}}} \left(\dfrac{\mu(B)}{m_B}-1\right) \\ &= -|{\mathcal{B}}| + \sum_{B\in{\mathcal{B}}} \dfrac{\mu(B)\cdot 2\log(n_0/C)}{(1+\varepsilon/2)\cdot (n_0/C) \cdot \left(-\log(p_0(1-p_0))\right)\cdot g_B(p^*)} \\ &= -|{\mathcal{B}}| + \dfrac{2C\log(n_0/C)}{(1+\varepsilon/2)n_0} \cdot \sum_{B\in{\mathcal{B}}} \dfrac{\mu(B)}{-\log(p_0(1-p_0))\cdot g_B(p^*)} . \end{align*}

By Proposition 27,

\begin{align*} \sum_{B\in{\mathcal{B}}} M_B &\geq -|{\mathcal{B}}| + \dfrac{2C\log(n_0/C)}{(1+\varepsilon/2)n_0} \cdot \dfrac{1}{-\log(p_0(1-p_0))\cdot g_{K_\mu}(p^*)} . \end{align*}

By the definition of ${\mathcal{B}}_0$ ,

\begin{align*} \sum_{B\in{\mathcal{B}}} M_B &\geq -|{\mathcal{B}}| + \dfrac{2C\log(n_0/C)}{(1+\varepsilon/2)n_0} \cdot \dfrac{(1+\varepsilon)n_0}{2\log n_0} \\ &= -|{\mathcal{B}}| + C \left(1 - \frac{\log C}{\log n_0}\right) \left(1 + \frac{\varepsilon}{2+\varepsilon}\right) \\ &= C + C \left(\frac{\varepsilon}{2+\varepsilon} - \frac{2+2\varepsilon}{2+\varepsilon}\cdot\frac{\log C}{\log n_0}\right) - |{\mathcal{B}}|. \end{align*}

With $\varepsilon$ fixed and $n_0 \gg C \gg |{\mathcal{B}}|$ , we have $\sum_{B\in{\mathcal{B}}} M_B \geq C$ , as desired. Thus, the index set $\{1,\ldots,C\}$ may be partitioned as

\begin{align*} \{1,\ldots,C\} = {\bigcup{{$\bullet$}}}_{\,\,B\in{\mathcal{B}}} S_B \end{align*}

so that $|S_B|\leq M_B$ , for each $B\in{\mathcal{B}}$ . Also, for each $B\in{\mathcal{B}}$ , we combine the embeddings $\varphi_{B,k}$ for all $k\in S_B$ to form an embedding

Combining all such embeddings, $F\mapsto K_\mu$ , as desired. So

\begin{align*} \bigcap_{k\in\{1,\ldots,C\}} \bigcap_{B\in{\mathcal{B}}} E_{k,B} \subseteq \bigcap_{\mu\in{\mathcal{B}}_0} E_{\mu} \qquad\Longleftrightarrow\qquad \bigcup_{\mu\in{\mathcal{B}}_0} \overline{E_{\mu}} \subseteq \bigcup_{k\in\{1,\ldots,C\}} \bigcup_{B\in{\mathcal{B}}} \overline{E_{k,B}} . \end{align*}

This completes the proof of the desired claim.

Finally, we are ready to prove Theorem 4.

3.3. Proof of Theorem 4

Formally, our goal is to show that for each $\varepsilon\in(0,1)$ , the following occurs a.a.s. as $n_0\rightarrow\infty$ :

(15) \begin{align} \sup_{p\in I}\left|{\textrm{ed}}_{{\mathcal{H}}}(p) \left(\dfrac{2\log n_0}{n_0} \cdot \min\left\{\dfrac{p}{-\log(1-p_0)}, \dfrac{1-p}{-\log p_0}\right\}\right)^{-1} - 1\right|<\varepsilon , \end{align}

where

\begin{align*} I = \left\{ \begin{array}{rl} \left[0,1\right] , & \mbox{if $p^*\in [1-\varphi^{-1},\varphi^{-1}]$;} \\ \left[1/3,1\right] , & \mbox{if $p^*\in [0,1-\varphi^{-1})$;} \\ \left[0,2/3\right] , & \mbox{if $p^*\in (\varphi^{-1},1]$.} \end{array}\right. \end{align*}

We first establish an upper bound for ${\textrm{ed}}_{{\mathcal{H}}}(p)$ for all $p\in [0,1]$ . By the main result in [Reference Bollobás5], if $F\sim{\mathbb{G}}(n_0,p_0)$ , then a.a.s. as $n_0\rightarrow\infty$ ,

\begin{align*} \chi(F)-1 &\geq (1-\varepsilon/2)\; \dfrac{n_0}{2 \log_{1/(1-p_0)} n_0} , \\ \chi(F^c)-1 &\geq (1-\varepsilon/2)\; \dfrac{n_0}{2 \log_{1/p_0} n_0} . \end{align*}

Clearly F does not map into $\chi(F)-1$ white vertices or $\chi(F^c)-1$ black vertices. By, for example, Theorem 10, and the fact that $1/(1-\varepsilon/2) < 1+\varepsilon$ , then the following occurs a.a.s.:

(16) \begin{align} {\textrm{ed}}_{{\mathcal{H}}}(p) & \leq (1+\varepsilon)\; \min\left\{\dfrac{p}{n_0/(2 \log_{1/(1-p_0)} n_0)}, \dfrac{1-p}{n_0/(2 \log_{1/p_0} n_0)}\right\} \nonumber \\[5pt] & = (1+\varepsilon)\; \dfrac{2\log n_0}{n_0} \cdot \min\left\{\dfrac{p}{-\log(1-p_0)}, \dfrac{1-p}{-\log p_0}\right\} . \end{align}

We now find a lower bound to match Inequality (16) over the interval I as stated above. We will do this by finding the lower bound for $p\in (1/3,2/3)$ and then use concavity show how this extends to I in the various cases.

We will choose a $\tilde{p}\in (1/3,2/3)$ depending on the case:

\begin{align*} \tilde{p} &\,:\!=\, \left\{ \begin{array}{rl} p^*, & \mbox{if $p^*\in (1/3,2/3)$;} \\ 1/3+\varepsilon/9, & \mbox{if $p^*\in (0,1/3]$;} \\ 2/3-\varepsilon/9, & \mbox{if $p^*\in [2/3,1)$.} \end{array} \right. \end{align*}

Let $K = K(\tilde{p})\in{\mathcal{K}}_{\mathcal{H}}$ be a $\tilde{p}$ -core CRG that satisfies ${\textrm{ed}}_{{\mathcal{H}}}(\tilde{p}) = g_K(\tilde{p})$ , as guaranteed by Theorem 10.

Since $\tilde{p}\in (1/3,2/3)$ , Lemma 31 gives that there exists a sub-CRG $K' = K'(\tilde{p},\varepsilon/4)$ of K so that

(17) \begin{align} g_K(\tilde{p}) \leq g_{K'}(\tilde{p}) \leq (1+\varepsilon/4) \, g_K(\tilde{p}), \end{align}

and whose components lie in some finite set ${\mathcal{B}} = {\mathcal{B}}(\tilde{p},\varepsilon/4)$ of CRGs.

The function $g_{K'} \,:\, [0,1]\to [0,1]$ is concave down. To see this, let $M_{K'}(p)$ be the matrix defined by the CRG K ^′. Let $p_1,p_2\in [0,1]$ , $t\in [0,1]$ , and let ${\bf x}\in\Delta_{K'}$ be the vector that witnesses the value of $g_{K'}$ at $t p_1 + (1-t) p_2$ ,

\begin{align*} g_{K'}\left(t p_1 + (1-t) p_2\right) &= \langle {\bf x}, M_{K'}\left(t p_1 + (1-t) p_2\right) {\bf x}\rangle \\ &= t\cdot\langle{\bf x}, M_{K'}(p_1){\bf x}\rangle + (1-t)\cdot\langle {\bf x}, M_{K'}(p_2) {\bf x}\rangle \\ &\geq t\cdot g_{K'}(p_1) + (1-t)\cdot g_{K'}(p_2) , \end{align*}

establishing the concavity of $g_{K'}$ . Since $g_{K'}(0),g_{K'}(1)\geq 0$ , the graph of $g_{K'}$ lies above the line segment from (0,0) to $(p^*,g_{K'}(p^*))$ and above the line segment from $(p^*,g_{K'}(p^*))$ to (1,0). So, for every $p\in [0,1]$ ,

(18) \begin{align} g_{K'}(p) \geq g_{K'}(p^*)\cdot \min\left\{\dfrac{p}{p^*}, \dfrac{1-p}{1-p^*}\right\} . \end{align}

Also by Lemma 37 (recall that $p^*=\frac{\log (1-p_0)}{\log(p_0(1-p_0))}$ from (9)), the following is true a.a.s.:

(19) \begin{align} g_{K'}(p^*) \geq (1-\varepsilon/4)\cdot\dfrac{2\log n_0}{-\log(p_0(1-p_0)) \cdot n_0}. \end{align}

Combining (17), (18), and (19),

(20) \begin{align} {\textrm{ed}}_{\mathcal{H}}(\tilde{p}) &= g_K(\tilde{p}) \nonumber \\[5pt] &\geq \frac{1}{1+\varepsilon/4}\, g_{K'}(\tilde{p}) \nonumber \\[5pt] &\geq \frac{1}{1+\varepsilon/4}\, g_{K'}(p^*)\cdot \min\left\{\dfrac{\tilde{p}}{p^*}, \dfrac{1-\tilde{p}}{1-p^*}\right\} \nonumber \\[5pt] &\geq \frac{1-\varepsilon/4}{1+\varepsilon/4}\cdot \frac{2\log n_0}{-\log (p_0(1-p_0))\cdot n_0}\cdot \min\left\{\dfrac{\tilde{p}}{p^*}, \dfrac{1-\tilde{p}}{1-p^*}\right\} \nonumber \\[5pt] &\geq (1-\varepsilon/2)\, \frac{2\log n_0}{-\log (p_0(1-p_0))\cdot n_0}\cdot \min\left\{\dfrac{\tilde{p}}{p^*}, \dfrac{1-\tilde{p}}{1-p^*}\right\} . \end{align}

Case 1. $p_0\in (1-\varphi^{-1},\varphi^{-1})$ $\Longleftrightarrow$ $p^*\in (1/3,2/3)$ .

In this case, $\tilde{p} = p^*$ . By (20),

\begin{align*} {\textrm{ed}}_{{\mathcal{H}}}(p^*) &\geq (1-\varepsilon/2)\, \frac{2\log n_0}{-\log (p_0(1-p_0))\cdot n_0} . \end{align*}

By the concavity of ${\textrm{ed}}_{{\mathcal{H}}}(p)$ and the fact that ${\textrm{ed}}_{{\mathcal{H}}}(0)={\textrm{ed}}_{{\mathcal{H}}}(1)=0$ , if $p\in[0,1]$ then

\begin{align*} {\textrm{ed}}_{{\mathcal{H}}}(p) &\geq (1-\varepsilon/2)\, \frac{2\log n_0}{-\log (p_0(1-p_0))\cdot n_0}\cdot \min\left\{\dfrac{p}{p^*}, \dfrac{1-p}{1-p^*}\right\} \\[5pt] &= (1-\varepsilon/2)\, \frac{2\log n_0}{n_0}\cdot \min\left\{\dfrac{p}{-\log (1-p_0)}, \dfrac{1-p}{-\log p_0}\right\} . \end{align*}

This satisfies (15) for all $p\in [0,1]$ , completing the proof in this case.

Case 2. $p_0\in (0,1-\varphi^{-1}]$ $\Longleftrightarrow$ $p^*\in (0,1/3]$ .

In this case, $\tilde{p} = 1/3 + \varepsilon/9 > p^*$ . By (20),

\begin{align*} {\textrm{ed}}_{{\mathcal{H}}}(\tilde{p}) &\geq (1-\varepsilon/2)\, \frac{2\log n_0}{-\log (p_0(1-p_0))\cdot n_0}\cdot \dfrac{1-\tilde{p}}{1-p^*} \end{align*}

By the concavity of ${\textrm{ed}}_{{\mathcal{H}}}(p)$ and the fact that ${\textrm{ed}}_{{\mathcal{H}}}(0)={\textrm{ed}}_{{\mathcal{H}}}(1)=0$ , if $p\in[0,1]$ then

\begin{align*} {\textrm{ed}}_{{\mathcal{H}}}(p) &\geq (1-\varepsilon/2)\, \frac{2\log n_0}{-\log (p_0(1-p_0))\cdot n_0}\cdot \dfrac{1-\tilde{p}}{1-p^*}\cdot \min\left\{\dfrac{p}{\tilde{p}}, \dfrac{1-p}{1-\tilde{p}}\right\} . \end{align*}

Observe that $-\log (p_0(1-p_0)) (1-p^*) = -\log p_0$ . Substituting $\tilde{p}=1/3+\varepsilon/9$ and $p=1/3$ ,

\begin{align*} {\textrm{ed}}_{{\mathcal{H}}}(1/3) &\geq (1-\varepsilon/2)\, \frac{2\log n_0}{-\log (p_0(1-p_0))\cdot n_0}\cdot \dfrac{2/3-\varepsilon/9}{1-p^*}\cdot \dfrac{1/3}{1/3+\varepsilon/9} \\[5pt] &= \dfrac{(1-\varepsilon/2)(1/3-\varepsilon/18)}{1/3+\varepsilon/9}\cdot \frac{2\log n_0}{n_0}\cdot \dfrac{2/3}{-\log p_0} \\[5pt] &\geq (1-\varepsilon)\, \frac{2\log n_0}{n_0}\cdot \dfrac{2/3}{-\log p_0} . \end{align*}

Again by concavity,

\begin{align*} {\textrm{ed}}_{{\mathcal{H}}}(p) \geq (1-\varepsilon)\, \frac{2\log n_0}{n_0}\cdot \dfrac{2/3}{-\log p_0}\cdot \min\left\{\dfrac{p}{1/3},\dfrac{1-p}{2/3}\right\} . \end{align*}

This matches the upper bound (16) for all $p\in [1/3,1]$ and, in fact, if $p^*=1/3$ , then it matches the upper bound for all $p\in [0,1]$ . This completes the proof in this case.

Case 3. $p_0\in [\varphi^{-1},1)$ $\Longleftrightarrow$ $p^*\in [2/3,1)$ .

This case may be shown with a similar argument as Case 2. In this case, $\tilde{p} = 2/3-\varepsilon/9 < p^*$ . By (20), the concavity of ${\textrm{ed}}_{\mathcal{H}}(p)$ , and substituting $\tilde{p}=2/3-\varepsilon/9$ and $p=2/3$ ,

\begin{align*} {\textrm{ed}}_{{\mathcal{H}}}(p) \geq (1-\varepsilon)\, \frac{2\log n_0}{n_0}\cdot \dfrac{2/3}{-\log (1-p_0)}\cdot \min\left\{\dfrac{p}{2/3},\dfrac{1-p}{1/3}\right\} . \end{align*}

This matches the upper bound (16) for all $p\in [0,2/3]$ and if $p^*=2/3$ , then it matches the upper bound for all $p\in[0,1]$ . This completes the proof in this case and the proof of Theorem 4.

5.1. p-core CRGs

Theorem 23 classifies all p-core CRGs on the interval $[1-\varphi^{-1},\varphi^{-1}]$ .

Question 41. For which $a\in (0,1-\varphi^{-1})$ does there exist an elementary classification of all p-core CRGs for all $p\in [a,1-a]$ ? Additionally, are all sufficiently large connected p-core CRGs either dalmatian CRGs (if $p\leq 1/2$ ) or the complement of a dalmatian CRG (if $p\geq 1/2$ )?

A crucial part of the proof of Theorem 4 is Lemma 31, which establishes that, for $p\in (1/3,2/3)$ , a p-core CRG can be approximated so that the g function does not increase by much, but the components are bounded.

Question 42. Does Lemma 31 hold if the interval $(1/3,2/3)$ is widened to $(a,1-a)$ for some $a \in (0,1/3)$ ?

5.2. Inhomogeneous random graphs

Since the development of graph limits, inhomogeneous generalizations ${\mathbb{G}}(n,W)$ of the Erdős–Rényi random graph models have emerged as a topic of research interest (see [Reference Lovász9]). Here, $W\,:\,\Omega^2\to[0,1]$ is a graphon, which is a symmetric measurable function where $\Omega$ is a probability space, frequently [0,1] equipped with the Lebesgue measure. To form a W-random graph $G\sim{\mathbb{G}}(n,W)$ , sample n elements $x_1,\dots,x_n\sim \Omega$ independently and form a graph on $\{1,\ldots,n\}$ by adding edge ij independently with probability $W(x_i,x_j)$ . We may also generate a sequence of W-random graphs $(G_n)_{n=1}^\infty\sim{\mathbb{G}}(\mathbb{N},W)$ adding the vertices corresponding to $x_1,x_2,\ldots$ , one at a time.

There are several questions we may ask related to the edit distance problem and inhomogeneous random graphs.

First, note that Theorem 4 implies that with $p_0\in [1-\varphi^{-1},\varphi^{-1}]$ and $(F_n)\sim {\mathbb{G}}(\mathbb{N},p_0)$ , then a.a.s. as $n_0\to\infty$ ,

(22) \begin{align} {\textrm{ed}}_{{\textrm{Forb}}(F_n)} = (1+o(1))\, r(n_0)\cdot s(p),\end{align}

where $r\,:\,\mathbb{N}\to[0,1]$ and $s\,:\,[0,1]\to[0,1]$ are some functions.

Question 43. If W is a graphon, does equation (22) a.a.s. hold for $(F_n)\sim{\mathbb{G}}(\mathbb{N},W)$ with some suitable functions $r = r_W$ and $s = s_W$ ?

For the next question, we note the following expression for the distance from a homogeneous random graph to a hereditary property. Combining Theorems 2 and 10, we see that if ${\mathcal{H}}$ is a (fixed) non-trivial hereditary property and $p\in [0,1]$ , then with $G_n\sim{\mathbb{G}}(n,p)$ ,

(23) \begin{align} \lim_{n\to\infty}{\mathbb E}[{\textrm{dist}}(G_n,{\mathcal{H}})] = \inf_{K\in {\mathcal{K}}_{\mathcal{H}}}g_K(p) = \min_{K\in {\mathcal{K}}_{\mathcal{H}}}g_K(p).\end{align}

Question 44. If instead $G_n\sim{\mathbb{G}}(n,W)$ , is there a similar expression for $\limsup_{n\to\infty} {\mathbb E}$ $[{\textrm{dist}}(G_n,{\mathcal{H}})]$ ? In particular, can we extend the functions $g_K(\cdot)$ from [0,1] to the set of all graphons so that equation (23) holds?