Local special copy trichotomy

If $A=\mathrm{\varnothing }$, the second lower bound is zero. If $B=\mathrm{\varnothing }$ and $h\ge 2$, it is also zero. If $h=1$, then ${\mathrm{ind}}_H(G)=\mathrm{\mid }G\mathrm{\mid }\ge \mathrm{\mid }A\mathrm{\mid }\ge x^a\mathrm{\mid }A\mathrm{\mid }$ even when $B$ is empty. Hence assume $A,B$ nonempty and $h\ge 2$, and that the first and second alternatives both fail.

List the edges at $g$ as $g{h}_1,\dots ,g{h}_d$, and let $H_r$ retain precisely the first $r$ of them, with all other adjacencies unchanged. Count special induced embeddings of $H_r$ taking $g$ to $A$ and other labels to $B$; denote the number by ${\tau }_r$. For each $v\in A$, its nonneighbor set $B_v$ has $\mathrm{\mid }{B}_v\mathrm{\mid }\ge x\mathrm{\mid }B\mathrm{\mid }$. Failure of the first alternative gives at least $x^b\mathrm{\mid }{B}_v{\mathrm{\mid }}^{h-1}\ge x^{b+h-1}\mathrm{\mid }B{\mathrm{\mid }}^{h-1}$ embeddings of $H-g$ there. Extending by $g\mapsto v$ and summing disjoint fibres by [F2] yields ${\tau }_0\ge x^{b+h-1}M$, where $M=\mathrm{\mid }A\mathrm{\mid }\mathrm{\mid }B{\mathrm{\mid }}^{h-1}>0$.

Failure of the second alternative gives ${\tau }_d<x^{a}M\le x^{b+h-1+cd}M$, since $d\le h-1$. Thus $d>0$ and there is a first $r\in \{1,\dots ,d\}$ with ${\tau }_r<x^{b+h-1+cr}M$. Its predecessor satisfies ${\tau }_{r-1}\ge x^{b+h-1+c(r-1)}M\ge 2x^{a}M>0$, since $a-(b+h-1+c(r-1))=1+c(h-r+1)\ge 1$ and $x\le 1\mathrm{/}2$. Also ${\tau }_r<x^c{\tau }_{r-1}$.

Put $w=h_r$. For each induced embedding $\psi$ of $H-\{g,w\}$ into $B$, let $U_{\psi }\subseteq B\setminus \mathrm{im}\psi$ contain the valid images of $w$ for $H-g$. Let $V_{\psi }\subseteq A$ contain the valid images of $g$ for $H_{r-1}-w$, using this intermediate graph, not $H-w$. Let $n_{\psi }$ and $e_{\psi }$ count respectively nonedges and edges between $V_{\psi },U_{\psi }$. The only remaining pair is $gw$: a nonedge completes $H_{r-1}$ and an edge completes $H_r$. Conversely every special embedding restricts to exactly one such $\psi$. Therefore [F2] gives $\sum n_{\psi }={\tau }_{r-1}$ and $\sum e_{\psi }={\tau }_r$.

There are at most $\mathrm{\mid }B{\mathrm{\mid }}^{h-2}$ possible $\psi$ by [F1]. Discard those with $n_{\psi }<{\tau }_{r-1}\mathrm{/}(2\mathrm{\mid }B{\mathrm{\mid }}^{h-2})$. Their total is at most ${\tau }_{r-1}\mathrm{/}2$, so the retained family has total at least ${\tau }_{r-1}\mathrm{/}2>0$. If every retained $\psi$ had $e_{\psi }>2x^c{n}_{\psi }$, summing would give ${\tau }_r>x^c{\tau }_{r-1}$, impossible. Some retained $\psi$ therefore has $e_{\psi }\le 2x^c{n}_{\psi }$.

For this $\psi$, $\mathrm{\mid }{U}_{\psi }\mathrm{\mid }\mathrm{\mid }{V}_{\psi }\mathrm{\mid }\ge n_{\psi }\ge {\tau }_{r-1}\mathrm{/}(2\mathrm{\mid }B{\mathrm{\mid }}^{h-2})\ge x^a\mathrm{\mid }A\mathrm{\mid }\mathrm{\mid }B\mathrm{\mid }$. Since $\mathrm{\mid }{U}_{\psi }\mathrm{\mid }\le \mathrm{\mid }B\mathrm{\mid }$ and $\mathrm{\mid }{V}_{\psi }\mathrm{\mid }\le \mathrm{\mid }A\mathrm{\mid }$, this implies $\mathrm{\mid }{V}_{\psi }\mathrm{\mid }\ge x^a\mathrm{\mid }A\mathrm{\mid }$ and $\mathrm{\mid }{U}_{\psi }\mathrm{\mid }\ge x^a\mathrm{\mid }B\mathrm{\mid }$. Moreover $e_{\psi }\le 2x^c{n}_{\psi }\le 2x^c\mathrm{\mid }{U}_{\psi }\mathrm{\mid }\mathrm{\mid }{V}_{\psi }\mathrm{\mid }$. Set $A^{\mathrm{\prime }}=V_{\psi }$, $B^{\mathrm{\prime }}=U_{\psi }$. These satisfy the third alternative and complete the proof.