Proof. We proceed by creating an injective function that takes a homomorphism $\varphi (x)$ from $H$ to $G$ satisfying the assumptions in the theorem and maps it to a homomorphism $\varphi '(x)$ from $H$ to $G'$ . For intuition, we attempt to map $\varphi$ to a $\varphi '$ such that $\varphi '(x) = \varphi (x)$ whenever possible.

If $\varphi (x) \not = u,v$ then we simply let $\varphi '(x) = \varphi (x)$ . If $\varphi (x) = u$ , then we again let $\varphi '(x) = \varphi (x)$ so long as there is not an edge $xy \in E(H)$ with $\varphi (y) \in N(u) \setminus \overline{N(v)}$ . If there is such an edge $xy \in E(H)$ , then we instead set $\varphi '(x) = v$ . Finally, if $\varphi (x) = v$ then we set $\varphi '(x)= \varphi (x)$ unless there is an edge $xy \in E(H)$ such that $\varphi (y) = u$ and $\varphi '(y) = v$ . If such an edge exists, then we set $\varphi '(x) = u$ . Formally,

\begin{equation*}\varphi '(x) = \begin {cases} v & \exists y\; :\; xy \in E(H) \text { and } \varphi (x) = u \text { and } \varphi (y) \in N(u) \setminus \overline {N(v)} \\ u & \exists y, z\; :\; xy, yz \in E(H) \text { and } \varphi (x) = v \text { and } \varphi (y) = u \text { and } \varphi (z) \in N(u) \setminus \overline {N(v)} \\ \varphi (x) & \text {otherwise}. \end {cases} \end{equation*}

We start with the following claim.

Proof. It suffices to check that the edges incident to vertices mapping to $u$ or $v$ are preserved. Let $a,b \in V(H)$ be such that $ab \in E(H)$ and $\varphi (a) = u$ . Since $\varphi$ is a homomorphism, we must have that $\varphi (b) \in N(u)$ . We now take cases.

1. Case I. $\varphi (b) \in N(u) \cap N(v)$

   Since $\varphi (b) \not = u,v$ , $\varphi '(b) = \varphi (b)$ . Moreover, $\varphi '(a)\varphi '(b) \in E(G')$ since $a$ maps to either $u$ or $v$ under $\varphi '$ and both $u\varphi '(b)$ and $v\varphi '(b)$ are edges in $G'$ .

2. Case II. $\varphi (b) \in N(u) \setminus \overline{N(v)}$ .

   If we are in this case, then $\varphi '(a) = v$ as $ab \in E(H)$ , $\varphi (a) = u$ and $\varphi (b) \in N(u) \setminus \overline{N(v)}$ . Moreover, $\varphi '(b) = \varphi (b)$ as $\varphi (b) \not = u,v$ . Since $v\varphi (b) \in E(G')$ , we are again done.

3. Case III. $\varphi (b) = v$ and $\varphi '(a) = u$ (see Figure 3)

   We claim that $\varphi '(b) = v$ . Suppose not. Then $\exists y, z\; :\; by, yz \in E(H), \varphi (y) = u, \text{ and } \varphi (z) \in N(u) \setminus \overline{N(v)}$ . Since $yz \in E(H)$ , $\varphi '(y) = v$ and thus $y \not = a$ . But now note $\varphi (a) = \varphi (y) = u$ , so $ay \not \in E(H)$ . Moreover, $bz \not \in E(H)$ since $\varphi (z) \in N(u) \setminus \overline{N(v)}$ and $\varphi (b) = v$ . It then follows that $abyz$ is a path in $H$ . But then $\varphi$ maps the forbidden path $abyz$ to $u,v,$ and a vertex in $N(u) \setminus \overline{N(v)}$ , which is a contradiction.

4. Case IV. $\varphi (b) = v$ and $\varphi '(a) = v$ (see Figure 3)

   Note that since $\varphi '(a) = v$ we must have that there is a $y$ such that $ay \in E(H)$ and $\varphi (y) \in N(u) \setminus \overline{N(v)}$ . But it then follows that $\varphi '(b) = u$ since $ba, ay \in E(H)$ .

Figure 3. Forbidden paths in proof of Claim 15.

Now let $a$ and $b$ be vertices such that $\varphi (a) = v$ and $ab \in E(H)$ where $\varphi (b) \not = u$ . Then we have one of two cases

1. Case V. $\varphi '(a) = v$

   Since $\varphi$ is a homomorphism we have that $\varphi (b) \in N_G(v)$ . But then we have that the edge $ab$ is preserved by the homomorphism since $N_{G}(v) \subseteq N_{G'}(v)$ .

2. Case VI. $\varphi '(a) = u$

   In this case there exists $y, z$ such that $ay, yz \in E(H)$ , $\varphi (y) = u$ and $\varphi (z) \in N(u) \setminus \overline{N(v)}$ . Now we claim $\varphi (b) \in N(u)$ . Suppose not, then $\varphi (b) \in N(v) \setminus \overline{N(u)}$ . We now note that $bayz$ is a forbidden path: $by \not \in E(H)$ as $\varphi (y) = u$ and $\varphi (b) \not \in N(u)$ and $az \not \in E(H)$ as $\varphi (a) = v$ and $\varphi (z) \in N(u) \setminus \overline{N(v)}$ . But then $bayz$ is forbidden path with $u,v$ and $\varphi (z) \in N(u) \setminus \overline{N(v)}$ in the image of $\varphi$ , a contradiction.

Since these are all the cases we indeed have that $\varphi '$ is a valid homomorphism.

To see that the map is injective, suppose that we had that $\varphi _1, \varphi _2 \mapsto \varphi '$ . Clearly $\varphi _1(x) = \varphi _2(x)$ for all $x$ such that $\varphi '(x) \not = u,v$ . Now suppose that for some $x \in V(H)$ , $\varphi _1(x) = u$ and $\varphi _2(x) = v$ . If $\varphi '(x) = v$ , then $x$ is adjacent to some $y$ such that $\varphi _1(y) \in N(u) \setminus \overline{N(v)}$ . But then $\varphi _2$ also maps $y$ to the same vertex, but $v$ is not adjacent to $\varphi _2(y)$ in $G$ , which contradicts the fact that $\varphi _2$ is a homomorphism.

So now suppose that $\varphi '(x) = u$ . Then there exist $y, z$ such that $xy, yz \in E(H) \text{ and } \varphi _2(y) = u \text{ and } \varphi _2(z) \in N(u) \setminus \overline{N(v)}$ . But then we must have that $\varphi _1(y) = v$ since $xy \in E(H)$ and $\varphi _1(x) = u$ . Similarly, we have that $\varphi '(y) = v$ as $xy \in E(H)$ and $\varphi '(x) = u$ . But now $y$ is a vertex such that $\varphi _1(y) = v$ and $\varphi _2(y) = u$ and $\varphi '(y) = v$ , which we just showed yields a contradiction.

Hence the map is injective as desired and the statement holds.

Proof. If $H$ does not contain induced subgraphs isomorphic to $P_4$ and $C_4$ , then we have that $H$ has no forbidden paths. Hence $H$ has at least as many homomorphisms to $G'$ as it does to $G$ .

Proof. Let $abcd$ be a forbidden path in $H$ . Then we must choose one of the four vertices to map to $u$ , one of the remaining three to map to $v$ , and one of the remaining two to map to a vertex in $S$ . The remaining $|H|-3$ vertices in the graph could go to any of $n$ vertices. Hence, we have that there are at most

\begin{equation*}4! |S| n^{|H|-3}\end{equation*}

such homomorphisms. Since there are only a constant number of forbidden paths in $H$ , which we denote by $k_H$ , we have that there are at most

\begin{equation*}4! k_H |S| n^{|H|-3} = O_H(|S| n^{|H|-3})\end{equation*}

homormophism mapping a forbidden path to a set including $u$ , $v$ and a vertex from $S$ .

Proof. We prove this by induction on the number of vertices.

For the base case, note that a graph with a single vertex is threshold. Now assume the statement holds for graphs with at most $n$ vertices and let $G$ be a graph on $n+1$ vertices. Let $v_{n+1}$ be the vertex of maximum degree and $v_1, \ldots, v_n$ be the remaining vertices. Consider applying the following $n$ moves: Move the neighbours of $v_1$ to $v_{n+1}$ , then move the neighbours of $v_2$ to $v_{n+1}$ , continue in this way until moving the neighbours from $v_{n}$ to $v_{n+1}$ .

Let $G'$ be the graph after applying all the above moves. Clearly $N_{G'}(v_1) \cup N_{G'}(v_2) \cup \ldots \cup N_{G'}(v_n) \subseteq \overline{N_{G'}(v_{n+1})}$ . Hence if $v_i v_j \in E(G')$ and $j \not = n+1$ , then we have that $v_{n+1} v_j \in E(G')$ . We then conclude that if $v_{n+1} v_j \not \in E(G')$ for $j \not = n+1$ , then it must be the case that $v_j$ is isolated.

Let $I$ denote the vertices in $G'$ that are isolated. Applying the inductive hypothesis to $G'[V \setminus (I \cup \{v_{n+1}\})]$ , we have that there is a set of at most $n^2$ moves that transforms $G'[V \setminus (I \cup \{v_{n+1}\})]$ to a threshold graph $T$ with total movement at most $|E(G'[V \setminus (I \cup \{v_{n+1}\})])|$ . Applying these moves to $G'$ gives us a graph $G''$ . But now note that $G''$ can be described as adding a dominating vertex to $T$ followed by $|I|$ isolated vertices. So $G''$ is a threshold graph. Note that we made at most $n^2 + n \leq (n+1)^2$ moves.

To bound the total movement cost, note that any edge incident to $v_{n+1}$ was moved at most once by the initial set of $n$ moves. So by the inductive hypothesis, the total movement cost is at most $E(G'[V \setminus (I \cup \{v_{n+1}\})]) + \deg _{G'}(v_{n+1}) = |E(G)|$ , as desired.

Proof. We use the local moves to transform the true maximum graph into a threshold graph and argue that we haven’t lost too many homomorphisms. By Lemma 19, there exists a sequence of local moves on pairs $(u_1, v_1)$ , …, $(u_k, v_k)$ with total movement at most $|E(G)|$ that transforms $G$ into a threshold graph $T$ . Let $G_i$ be the graph defined by applying $(u_i, v_i)$ to $G_{i-1}$ . By Lemmas 14 and 17, we have that

\begin{equation*}\hom\! (H, G_i) \geq \hom\! (H, G_{i-1}) - O_H(|N_{G_{i-1}}(u_i) \setminus \overline {N_{G_{i-1}}(v_i)}| n^{|H|-3} ).\end{equation*}

We thus conclude that

\begin{equation*}\hom\! (H,T)\geq \hom\! (H,G) - \sum _{i=1}^k O_H(|N_{G_{i-1}}(u_i) \setminus \overline {N_{G_{i-1}}(v_i)}| n^{|H|-3} ) \geq \hom\! (H,G) - O_H( n^{|H|-1} ) \end{equation*}

where the final inequality uses that the total movement of our sequence of local moves is at most $|E(G)| \leq n^2$ .

Proof. Let $\Delta = \alpha ^*(H) - \alpha ^*(H') \geq 0$ . By Theorem 22 and some algebraic manipulation we see that

\begin{align*} \mathcal{M}(H',n,m) & = O_H \left ( \left (\frac{m}{n} \right )^{|H'| - \alpha ^*(H')} n^{\alpha ^*(H')} \right ) \\ & = O_H \left ( \left (\frac{m}{n} \right )^{|H| - k - \alpha ^*(H) + \Delta } n^{\alpha ^*(H) - \Delta } \right ) \\ & = O_H \left ( \left (\frac{m}{n}\right )^{-k} \left ( \frac{m}{n^2} \right )^\Delta m^{{|H| - \alpha ^*(H)}} n^{2 \alpha ^*(H) - |H|} \right ) \\ & = O_H(\mathcal{M}(H,n,m)/\left (\frac{m}{n} \right )^k). \end{align*}

where the last equality used that $\mathcal{M}(H,n,m) = \Omega _H(m^{|H|-\alpha ^*(H)} n^{2 \alpha ^*(H) - |H|})$ and $m \leq n^2$ .

Proof. Let $abcd$ be a forbidden path. Then there are clearly $O(|S|)$ ways to map $3$ vertices from $a,b,c,d$ into $u,v$ and some vertex from $|S|$ . For ease of notation, assume these three vertices are $a,b,c$ . Now consider $H' = H[V(H) \setminus \{a,b,c\}]$ . We note that the number of homomorphisms is at most $O_H(|S| \mathcal{M}(H',n,m))$ . So it suffices to show that $\mathcal{M}(H',n,m) = O_H \left (\mathcal{M}(H,n,m)/\left (\frac{m}{n} \right )^3 \right )$ . But this follows from Lemma 23.

Proof. The proof follows almost identically to Theorem 3. Let $G^\star$ be the graph on $n$ vertices and $m$ edges with

\begin{equation*}\hom\! (H,G^\star ) = \mathcal {M}(H, n, m).\end{equation*}

By Lemma 19, there exists a sequence of local moves on pairs $(u_1, v_1)$ , $\ldots$ , $(u_k, v_k)$ with total movement at most $|E(G^\star )|$ that transforms $G^\star$ into a threshold graph $T$ . Let $G_i^\star$ be the graph defined by applying $(u_i, v_i)$ to $G_{i-1}^\star$ . By Lemmas 14 and 24, we have that

\begin{equation*}\hom\! (H, G_i^\star ) \geq \hom\! (H, G_{i-1}^\star ) - O_H \left (|N_{G_{i-1}^\star }(u_i) \setminus \overline {N_{G_{i-1}^\star }(v_i)} | \cdot \mathcal {M}(H,n,m)/ \left (\frac {m}{n} \right )^3 \right ).\end{equation*}

We thus conclude that

\begin{align*} \hom\! (H,T) &\geq \hom\! (H,G^\star ) - \sum _{i=1}^k O_H\left(|N_{G_{i-1}^\star }(u_i) \setminus \overline{N_{G_{i-1}^\star }(v_i)} | \cdot \mathcal{M}(H,n,m)/ \left (\frac{m}{n} \right )^3 \right) \\ &\geq \mathcal{M}(H,n,m) - O_H \left ( \frac{n^3}{m^2} \cdot \mathcal{M}(H,n,m) \right ) \end{align*}

where the final inequality uses the total movement of our moves is $|E(G)|$ .

Proof. We again construct an injective map from a subset of $\hom\! (H,G)$ to $\hom\! (H,G')$ . Specifically, given $\varphi \in \hom\! (H,G)$ , we map it to

\begin{equation*}\varphi '(x) = \begin {cases} v & \varphi (x) = u \text { and }\exists e \in E(H)\; :\; x \in e \text { and } (\varphi (e) \setminus \{u\}) \cup \{v\} \not \in E(G) \\ \varphi (x) & \text {otherwise}. \end {cases}\end{equation*}

We can easily verify that $\varphi '$ is a homomorphism if $\varphi$ uses at most one of $u$ and $v$ . To see that the map is injective, suppose $\varphi _1, \varphi _2 \in \hom\! (H,G)$ both map to a homomorphism $\varphi ' \in \hom\! (H,G')$ . Towards a contradiction, assume $\varphi _1 \not = \varphi _2$ . By definition, $\varphi '(x) = \varphi _1(x)$ whenever $\varphi _1(x) \not = u$ . As an analogous statement holds for $\varphi _2$ , we have that $\varphi _1(x) = \varphi _2(x) = \varphi '(x)$ for all $x$ such that $\varphi _1(x) \not = u$ and $\varphi _2(x) \not = u$ . So without loss of generality there exists an $x$ such that $\varphi _1(x) = u$ and $\varphi _2(x) = v$ . Then $\varphi '(x) = v$ and there exists an $e \in E(H)$ containing $x$ such that $(\varphi _1(e) \setminus \{u\}) \cup \{v\} \not \in E(G)$ . But now note that $\varphi _2(e) = (\varphi _1(e) \setminus \{u\}) \cup \{v\} \not \in E(G)$ , so we have reached a contradiction.

Proof of Lemma 6, assuming Lemma 28 . Let $G$ be a hypergraph with $n$ vertices. By Lemma 28 we can use $o_k(n^2)$ hypergraph moves $(u_1, v_1), \ldots, (u_\ell, v_\ell )$ and remove at most $o_k(n^k)$ edges to turn it into a threshold hypergraph $T$ . Now note the number of homormorphisms $H$ to any hypergraph $G'$ that use any two specific vertices $u,v \in V(G')$ is at most $O_H(n^{|H|-2})$ . Similarly, there are at most $O_{H,k}(n^{|H|-k})$ homomorphisms that use every vertex in a hyperedge $e \in E(G')$ . Thus by Lemma 27 each hypergraph move $(u_i, v_i)$ removes at most $O_H(n^{|H|-2})$ homomorphisms. Moreover, removing a hyperedge $e$ removes at most $O_{H,k}(n^{|H|-k})$ homomorphisms. We conclude that

\begin{equation*}\hom\! (H,T) \geq \hom\! (H,G) - o_k(n^2) \cdot O_H(n^{|H|-2}) - o_k(n^k) \cdot O_{H,k}(n^{|H|-k}) = \hom\! (H,G) - o_{H,k}(n^{|H|}). \end{equation*}

Proof. Assume that $\delta \gt k \log (n)$ as otherwise we can simply take $D = A$ . We will follow the classical proof for dominating sets given in [Reference Alon and Spencer3]. Take a random set $S$ such that every vertex of $A$ is in $S$ independently with probability $p$ and let $N$ denote the set of vertices in $B$ without a neighbour in $S$ . Build a set $D$ by adding a neighbour of each vertex in $N$ to $S$ . Then observe that $N_G(D) = B$ and in expectation we have

\begin{equation*}\mathbb {E}[|D|] \leq \mathbb {E}[|S| + |N|] \leq pn + n^k (1-p)^{\delta } \leq pn + n^k e^{-p \delta }.\end{equation*}

Taking $p = \frac{1}{\delta } \log (\delta n^{k-1})$ then gives

\begin{equation*}E[|D|] \leq \frac {kn\log (n)}{\delta } + \frac {n}{\delta } = O_k \left ( \frac {n\log (n)}{\delta } \right ).\end{equation*}

Proof. First note that if $|S| \lt \sqrt{n} + 1$ we can take $D = S$ . So we assume $|S| \geq \sqrt{n} + 1$ . We then have that $|B| \leq n^{k-1} \leq |A|^{2k-2}$ . By Lemma 30, it follows that there exists a set $D \subseteq S$ of size at most $O_k(n \log (n)/ n^{2/3}) = O_k(\sqrt{n})$ such that $N_I(D) = B$ .

We claim that $D \cup \{v\}$ is a dominating set of $S$ with respect to $v$ . Indeed, let $s \in S$ and $e$ be an edge containing $s$ with $v \not \in e$ . If $e \setminus \{s\} \cup \{v\} \in E$ then we are done, so suppose this is not the case. It then follows that $e \setminus \{s\} \in B$ , so there exists a vertex $d \in D$ that is a neighbour of $e \setminus \{s\}$ in $I$ , which implies $(e \setminus \{s\}) \cup \{d\} \in E(G)$ , as desired.

Proof. Fix $s \in S$ and an edge $e \in E(G_k)$ containing $s$ such that $v \not \in e$ . We will show that $e \setminus \{s\} \cup \{v\} \in E(G_k)$ . First, observe that we never remove hyperedges containing $v$ as no subsets $b$ in the induced incidence graph contain $v$ or are neighbours of $v$ . Since we only add edges incident to $v$ , $e \in E(G_i)$ for all $i$ . It then follows that there exists $d_1, \ldots, d_k$ such that $e \setminus \{s\} \cup \{d_i\} \in E(H_i)$ . Note that if $e \setminus \{s\} \cup \{d_i\}$ exists when we apply the local move from $d_i$ to $v$ , then clearly $e \setminus \{s\} \cup \{v\} \in G_{i+1}$ . As we never remove edges containing $v$ , $e \setminus \{s\} \cup \{v\} \in G_{k}$ .

Now towards a contradiction, suppose that for each $i$ we applied a local move from $d_i' \in D_i$ to $v$ before the move from $d_i$ to $v$ , and the move from $d_i'$ causes the removal of $e \setminus \{s\} \cup \{d_i\}$ . Observe that $d_i' \not = d_j'$ for $i \lt j$ . Indeed suppose $d_i' = d_j'$ . Note $d_i' \ll _{G_{i+1}} v$ . Since we only add edges incident to $v$ and never remove edges containing $v$ , we have that $d_i' \ll _{H_{\ell }} v$ for all $\ell \gt i$ . In particular, at the time of making the move from $d_j'$ to $v$ we have that $d_j' \ll v$ , so the local move from $d_j'$ to $v$ would remove no edges, a contradiction.

But we now observe that $\{d_1', \ldots, d_k'\} \subseteq e \setminus \{s\}$ , a contradiction as $|e \setminus \{s\}| = k - 1$ .

Proof. We start with the case that $w = v$ .

Since after applying the hypergraph move we have that $u \ll _{G'} v$ , we have also shown that $u \ll _{G'} x$ . So it only remains to handle the case of $w \not = u,v$ .

Since we have handled all the cases, that is, $w = v$ , $w = u$ and $w \not = u,v$ , the proof now follows.

Proof. Let $e \in E(G')$ be an edge containing $x$ and not $y$ . We will show that $f = e \setminus \{x\} \cup \{y\} \in E(G')$ . Since $E(G') \subseteq E(G)$ , $e \in E(G)$ . Combining this with the fact that $x \ll _G y$ implies $f \in E(G)$ . Now fix some $s \in f \cap S \subseteq e \cap S$ . We will show that $f \setminus \{s\}$ does not lead to the removal of $f$ . To do so, we take cases on why $e \setminus \{s\}$ didn’t lead to the removal of $e$ .

1. Case I. $\deg _I(e \setminus \{s\}) \gt n^{2/3}$

   Note that $s \not = x$ as $x \not \in f$ . Combining this with the fact that $x \ll _G y$ , we observe that for any $t \not = y$ , if $e \setminus \{s\} \cup \{t\} \in E(G)$ then $e \setminus \{s, x\} \cup \{t,y\} = (f \setminus \{s\}) \cup \{t\} \in E(G)$ . So, $\deg _I(f \setminus \{s\}) \geq \deg _I(e \setminus \{s\}) \gt n^{2/3}$ and $f \setminus \{s\}$ doesn’t lead to the removal of $f$ .

2. Case II. $v \in e$

   If $x \not = v$ , then $v \in f$ . Observe that by construction, the incidence graph has no edges corresponding to hyperedges in $G$ containing $v$ . So we never remove edges containing $v$ , and $f \in E(G')$ . Now assume that $x = v$ . Since $s \ll _G y$ , we have that $e \setminus \{s\} \cup \{y\} \in E(G)$ . But now note $f \setminus \{s\} \cup \{v\} = e \setminus \{s\} \cup \{y\}$ . It then follows that $f \setminus \{s\} \not \in B$ . Thus, we conclude $f \setminus \{s\}$ doesn’t lead to the removal of $f$ .

3. Case III. $e \setminus \{s\} \cup \{v\} \in E(G)$

   Since $x \ll _G y$ , $e \setminus \{s,x\} \cup \{v,y\} \in E(G)$ . But $e \setminus \{s,x\} \cup \{v,y\} = f \setminus \{s\} \cup \{v\}$ . Thus $f \setminus \{s\} \not \in B$ and again doesn’t cause the removal of $f$ .

Since we chose $s$ arbitrarily, $f \in E(G')$ , as desired.

Proof of Lemma 28 . We apply the following algorithm to transform $G$ into a threshold hypergraph:

Initially, let $T = \emptyset$ . Repeat $n$ times: Choose a vertex $v \in V \setminus T$ . Apply the domination procedure with $G_0 = G$ from $V \setminus T$ to $v$ , resulting in a hypergraphs $G_1, G_2, \ldots, G_k$ , intermediate hypergraphs $H_0, \ldots, H_{k-1}$ , and dominating sets $D_0, \ldots, D_{k-1}$ . Set $T = T \cup \{v\}$ and $G = G_k$ .

Note that the above claim implies that we make $O_k(n^{3/2})$ hypergraph moves in total.

Proof. Fix some $b \in \binom{[n]}{k-1}$ . We claim that $b$ only causes the removal of edges at most $k$ times. Indeed, after removing all edges of the form $b \cup \{s\}$ , we must add some hyperedge containing $b$ for $b$ to cause the removal of more hyperedges. Let $e$ be the first hyperedge containing $b$ added after $b$ ’s $\ell$ th removal. $e$ must have been added by some local move, say from $s$ to $v$ . Now since $e$ is the first such edge we have that $b \not \subset e \setminus \{v\} \cup \{s\}$ . So $v \in b$ . Since we make local moves to any vertex at most once and there are $k-1$ elements in $b$ , it follows that $b$ ’s low degree only causes the remove of hyperedges at most $k$ times. (Note that we are crucially using that $b$ cannot be added and removed multiple times when running the domination procedure with a vertex $v \in b$ . Indeed, if $b$ is added due to a local move to $v$ , it cannot be removed until the next iteration as local moves to $v$ never remove hyperedges containing $v$ , and after the addition of an edge $e$ containing $b$ , $b$ will no longer appear in the incidence graph induced by $V \setminus T$ with respect to $v$ .)

We now conclude that each $b \in \binom{[n]}{k-1}$ causes the removal of at most $kn^{2/3}$ edges. So in total we remove at most

\begin{equation*}\binom {n}{k-1} k n^{2/3} = o_k(n^k)\end{equation*}

hyperedges in total.

With these three claims the proof is now complete as we have shown that the algorithm presented transforms the graph into a threshold hypergraph by using $O_k(n^{3/2})$ local moves and removing $o_k(n^k)$ hyperedges.

Proof. We will prove the result for a connected graph $H$ . If the graph is not connected, we can apply the result to each of the components and take the maximum of the $k_H$ ’s over all the components.

Let $T$ be a spanning tree of $H$ . We note that clearly for any graph $G$ , $t(H,G) \leq t(T,G)$ since $T$ was obtained by removing edges from $H$ . Now using a result from Sidorenko [Reference Sidorenko15] we have that $t(T,G) \leq t(K_{1, |H|-1}, G)$ for all $G$ . By a result of Reiher and Wagner [Reference Reiher and Wagner13], we have that there exists a $k_H$ such that for $c \gt k_H$ , $\mathcal{M}_{K_{1, |H|-1}}(c)$ is achieved on the quasi-clique. But now note that for any quasi-clique $\mathcal{K}$ have that $t(H, \mathcal{K}) = t(K_{1, |H|-1}, \mathcal{K})$ , so $\mathcal{M}_H(c)$ is also attained on the quasi-clique.

Proof. We will let $G$ be a threshold graph with three parts:

\begin{equation*}\underbrace {11 \ldots 1}_{\alpha \text { 1's}} \underbrace {00 \ldots 0}_{\beta \text { 0's}} \underbrace {11 \ldots 1}_{\gamma \text { 1's}}, \end{equation*}

where we let $\alpha = \lfloor \sqrt{m} \rfloor$ , $\gamma = \lfloor m/(2n) \rfloor$ , $\beta = n - \alpha - \gamma$ . Then we have that there are at most

\begin{equation*}\frac {(\sqrt {m})^2}{2} + \frac {m}{2n}n = m\end{equation*}

edges as desired.

To analyse the number of homomorphisms, we note that we lost at most a factor of two from the floors. That is $\alpha \geq \sqrt{m}/2$ and $\gamma \geq (m/4n)$ . Clearly, we also have that $\beta \geq n - \sqrt{m} - m/(2n) \geq n/25$ .

Now let $f\; :\; V(H) \rightarrow \{0,1/2,1\}$ be an optimal fractional independence function, that is, $f(v_1), \ldots, f(v_n)$ is an optimal solution to the linear program used to define to the fractional independence number (see Definition 11). Note that such a function exists since the feasibility polytope for fractional independence is half-integral. Now, we claim that any injective function $\varphi$ that sends $f^{-1}(1/2)$ to the first block of $1$ ’s, $f^{-1}(0)$ to the second block of $1$ ’s and $f^{-1}(1)$ to the block of $0's$ is a homomorphism. This claim will complete the proof since there are at least

\begin{equation*}\left ( \frac {\sqrt {m}}{2} \right )^{|f^{-1}(1/2)|} \left (\frac {n}{25} \right )^{|f^{-1}(1)|} \left (\frac {m}{4n} \right )^{|f^{-1}(0)|} = \Omega _H(m^{|H| - \alpha ^*(H)} n^{2\alpha ^*(H) - |H|})\end{equation*}

such functions. To see that these are homomorphisms, suppose $uv \in E(H)$ . Without loss of generality assume $f(u) \leq f(v)$ . Now if $u \in f^{-1}(0)$ , then since every vertex in the final block of $1$ ’s is domininating we have that $\varphi (u) \varphi (v) \in E(G)$ . Otherwise if $f(u) = f(v) = \frac{1}{2}$ , then we have that both $\varphi (u)$ and $\varphi (v)$ are mapped to vertices in the first block of ones. Since any two vertices in this block are connected, we have $\varphi (u) \varphi (v) \in E(G)$ and this is indeed a homomorphism.

Proof of Theorem 43 . Since isolated vertices do not affect the optimising graph, we assume without loss of generality that $H$ has no isolated vertices.

By Corollary 45, we have that there exists a graph $G$ and constant $C_1$ such that

\begin{equation*}t(H,G) \geq C_1 c^{|H|-\alpha ^*(H)}.\end{equation*}

This implies that $\mathcal{M}_H(c) \geq C_1 c^{|H|-\alpha ^*(H)}$ by Lemma 10. For the sake of contradiction, assume that $H$ is optimised on the quasi-star or quasi-clique. Note that if it’s optimised on the quasi-clique then we have that for all graphs $G$

\begin{equation*}t(H,G) \leq c^{|H|/2}.\end{equation*}

Since $\alpha ^*(H) \gt |H|/2$ , we have that for $c$ sufficiently small $C_1 c^{|H|-\alpha ^*(H)} \gt c^{|H|/2}$ , a contradiction.

So we must have that the homomorphism density of $H$ is maximised on the quasi-star. Recall now that every vertex in the quasi-star either has degree $d_0$ or $d_1$ for some integers $d_0$ and $d_1$ with $d_0 \lt d_1$ . Note that in any homomorphism from $H$ to the quasi-star, the vertices in $H$ mapping to the vertices in the quasi-star of degree $d_0$ must form an independent set. Hence we have at least $|H| - \alpha (H)$ vertices are mapped to one of the at most $cn$ dominating vertices in the quasi-star of edge density $c$ . By a union bound argument, this implies that there are at most $O_H(c^{n-\alpha (H)} n^{|H|})$ homomorphisms. But now note again that for $c$ sufficiently small we have that $C_2 c^{|H|-\alpha (H)} \lt C_1 c^{|H|-\alpha ^*(H)}$ , which is a contradiction.

Thus such a graph $H$ is optimised on neither the quasi-star nor the quasi-clique.

Proof. Take $H = K_3 \sqcup K_{1,2}$ . Then $\alpha (H) = 3$ and $\alpha ^*(H) = 3.5$ . The result then follows by Theorem 43.

If we wish to take the graph to be connected, adding edges from each vertex in the clique to the vertex of degree $2$ in the star gives a graph $H$ where we still have $\alpha (H) = 3$ and $\alpha ^*(H) = 3.5$ . Moreover, such a graph is a threshold graph. We can also take $H = K_\ell \sqcup K_{1,2}$ for any $\ell \geq 3$ if we want arbitrarily large examples.