Quantitative Induced Density and the Log-Log Step

Induct on $r=j-\mathrm{\mid }I\mathrm{\mid }$. When $r=0$, the given map is its unique extension and the bound is $(t\mathrm{/}j{)}^0=1$.

Let $r>0$ and assume the assertion for $r-1$. Choose a missing label $v$. For every $i\in I$, [F1] bounds by $t\mathrm{/}j$ the vertices in $A_v$ with the wrong adjacency to $\varphi (i)$. The union of these forbidden sets has size at most $\mathrm{\mid }I\mathrm{\mid }t\mathrm{/}j$: assign each forbidden vertex to its first offending label, obtaining disjoint subsets of the forbidden sets. Thus at least $t-\mathrm{\mid }I\mathrm{\mid }t\mathrm{/}j\ge t\mathrm{/}j>0$ vertices are available.

Each available $w\in A_v$ gives an induced extension by $v\mapsto w$: the old map already preserves all old pairs, the new pairs have the prescribed adjacency, and disjoint blocks prevent collisions. By induction each such map has at least $(t\mathrm{/}j{)}^{r-1}$ full extensions. The families for distinct $w$ are disjoint since they differ at $v$; adding their cardinalities gives at least $(t\mathrm{/}j)(t\mathrm{/}j{)}^{r-1}=(t\mathrm{/}j{)}^r$. This proves the induction, including the empty initial map.

Suppose such a blowup exists. Its unique empty good embedding has at least $(t\mathrm{/}j{)}^j$ good full extensions by [F1] with $I=\mathrm{\varnothing }$.

Every good extension is an induced embedding, so ${\mathrm{ind}}_J(G)\ge (t\mathrm{/}j{)}^j$, contradicting the strict hypothesis. Therefore the blowup cannot exist.

Let $d(v)=\mathrm{\mid }{N}_G(v)\cap B\mathrm{\mid }$. Counting the finite relation of adjacent pairs by its $A$ fibres gives ${\sum }_{v\in A}d(v)=e_G(A,B)$, including empty sets by [F1]. If $A$ or $B$ is empty, take $A^{\mathrm{\prime }}=A$. If $c=0$, the sum of nonnegative integer degrees is zero, so every degree is zero and again take $A^{\mathrm{\prime }}=A$.

Otherwise $c\mathrm{\mid }B\mathrm{\mid }>0$. Let $D=\{v\in A:d(v)>2c\mathrm{\mid }B\mathrm{\mid }\}$. If $D$ is nonempty, $2c\mathrm{\mid }B\mathrm{\mid }\mathrm{\mid }D\mathrm{\mid }<{\sum }_{v\in D}d(v)\le c\mathrm{\mid }A\mathrm{\mid }\mathrm{\mid }B\mathrm{\mid }$, hence $\mathrm{\mid }D\mathrm{\mid }<\mathrm{\mid }A\mathrm{\mid }\mathrm{/}2$. If $D$ is empty the same required conclusion $\mathrm{\mid }D\mathrm{\mid }\le \mathrm{\mid }A\mathrm{\mid }\mathrm{/}2$ holds. Thus $A^{\mathrm{\prime }}=A\setminus D$ has at least half the vertices and every degree in it is at most $2c\mathrm{\mid }B\mathrm{\mid }$.

The family $\mathcal{C}$ of $m$-subsets of $A$ is finite and nonempty: enumerate $A$ and take its first $m$ members. Its size is $\left(\genfrac{}{}{0px}{}{N}{m}\right)>0$. Each ordered adjacency pair $(a,b)\in A\times B$ is counted in $e_G(C,B)$ precisely when $a\in C$, and hence belongs to precisely $\left(\genfrac{}{}{0px}{}{N-1}{m-1}\right)$ members. Double counting incidences $(C,\text{edge})$ by [F2] and dividing by $\left(\genfrac{}{}{0px}{}{N}{m}\right)$ gives average cross count $e_G(A,B)\left(\genfrac{}{}{0px}{}{N-1}{m-1}\right)\mathrm{/}\left(\genfrac{}{}{0px}{}{N}{m}\right)=m{e}_G(A,B)\mathrm{/}N$, where the factorial identity [F1] gives the last ratio.

The averaging principle [F3] applied to this incidence relation yields a member with cross count no greater than the average. This remains true if $B$ or the edge set is empty: every cross count is zero.

For $m\ge 2$, an internal edge is in $\left(\genfrac{}{}{0px}{}{N-2}{m-2}\right)$ members of $\mathcal{C}$. Repeating the incidence count [F2], its average internal count is $e(G[A])\left(\genfrac{}{}{0px}{}{N-2}{m-2}\right)\mathrm{/}\left(\genfrac{}{}{0px}{}{N}{m}\right)=e(G[A])m(m-1)\mathrm{/}(N(N-1))$ by [F1]. A member no greater than this average exists by [F3]; division by $\left(\genfrac{}{}{0px}{}{m}{2}\right)>0$ gives the assertion.

If $m=1$, choose any vertex of the nonempty $A$; its induced graph has zero edges. For $m=N$, the only choice is $C=A$ and the bounds are equalities. In the complement the same count gives $e(\bar{G}[C])\le e(\bar{G}[A])\left(\genfrac{}{}{0px}{}{m}{2}\right)\mathrm{/}\left(\genfrac{}{}{0px}{}{N}{2}\right)$, equivalently an internal density at least that of $G[A]$ when $m\ge 2$.

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.

If $h=1$, take $\beta =\gamma =1$; the count is $n\ge xn$. For $h\ge 2$, first prove the assertion when $1\mathrm{/}x$ is an integer. Enlarge $\alpha$ to a positive integer at least $h(h+1)$, using [F1]; proving the smaller copy threshold for this enlarged exponent implies the original first alternative. Set $r_h=0$, $r_i=\alpha +2h+1+(h+1)r_{i+1}$ for $i<h$, ${\beta }_0=r_1+3$, and ${\gamma }_0=2r_1+h{\beta }_0$. These are positive integers, $r_i\ge 1$ for $i<h$, and $r_1\ge k{r}_k$ for $1\le k<h$: iterating $r_i\ge (h+1)r_{i+1}$ gives $r_1\ge (h+1{)}^{k-1}{r}_k\ge k{r}_k$.

If $x^{{\beta }_0}n\le 1$, choose a vertex $v$. Of its neighbors and nonneighbors outside $v$, one has size at least $(n-1)\mathrm{/}2\ge n\mathrm{/}(2h)$. That set is anticomplete to $A=\{v\}$ in one of the two graphs, proving the third alternative. Hence assume $x^{{\beta }_0}n>1$ and all three alternatives fail for ${\beta }_0,{\gamma }_0$.

Let $t=\lfloor x^{{\beta }_0-1}n\rfloor$. The argument exceeds $1\mathrm{/}x\ge 2$, so [F1] gives $t\ge x^{{\beta }_0-1}n\mathrm{/}2\ge x^{{\beta }_0}n>1$. Put $t_i=x^{-r_i}t$, $q_i=x^{r_i}\mathrm{/}h$; the reciprocal-integer assumption makes every $t_i$ an integer, and $t_1\le x^{2}n<n$. Since $2r_1\mathrm{/}h\ge 1$, we have ${\gamma }_0\mathrm{/}h\ge {\beta }_0+1$, whence $t\ge x^{{\beta }_0}n\ge h{x}^{{\gamma }_0\mathrm{/}h}n$. Failure of the count alternative and [F2] exclude a $(t_h,q_h)=(t,1\mathrm{/}h)$-blowup of $H$.

A one-label subgraph of $H$ has a $(t_1,q_1)$-blowup by taking any $t_1$ vertices. Among finitely many vertex subsets of $H$ admitting the specified blowup, take one of greatest size, say $J$ of size $1\le k<h$, with blocks $A_j$. Choose $w\in V(H)\setminus V(J)$ and let $L={\bigcup }_j{A}_j$. Outside $L$, let $M_j$ contain vertices with at most $x\mathrm{\mid }{A}_j\mathrm{\mid }$ neighbors if $wj$ is an edge of $H$, or at most $x\mathrm{\mid }{A}_j\mathrm{\mid }$ nonneighbors otherwise. If $\mathrm{\mid }{M}_j\mathrm{\mid }\ge n\mathrm{/}(2h)$, then $A_j,M_j$ give the third alternative. Thus every $\mathrm{\mid }{M}_j\mathrm{\mid }<n\mathrm{/}(2h)$. Also $\mathrm{\mid }L\mathrm{\mid }=k{t}_k\le h{x}^{2}n\le n\mathrm{/}(2h)$. Consequently $Z=V(G)\setminus (L\cup {\bigcup }_j{M}_j)$ has size at least $n\mathrm{/}2$.

Write $R=r_{k+1}$, $\mathrm{\Delta }=r_k-R$, and $s=x^{\mathrm{\Delta }}$. Then $t_{k+1}=s{t}_k$, $q_{k+1}=q_k\mathrm{/}s$, and $a_{\ast }=\alpha +(R+2)h=\mathrm{\Delta }-1$. Fix $j\in V(J)$ and $Y\subseteq Z$ of size at least $\mathrm{\mid }Z\mathrm{\mid }{s}^{k-1}$. If $wj$ is a nonedge, apply [F3] to $H,g,G,Y,A_j$ with its parameters $b=\alpha$, $c=R+1$. Its nonneighbor hypothesis holds by the definition of $Z$. If $wj$ is an edge, apply it to $\bar{H},g,\bar{G},Y,A_j$. Complementing both graphs preserves every induced embedding and the count of $H-g$; thus the same first two contradictions below apply in this case too.

The first outcome of [F3] would give a set of size at least $x{t}_k=x^{1-r_k}t\ge t\ge x^{{\beta }_0}n$ with the forbidden few-copy property. For the second, $\mathrm{\mid }Y\mathrm{\mid }\ge n{x}^{(k-1)\mathrm{\Delta }}\mathrm{/}2\ge n{x}^{r_1}$: indeed $(k-1)\mathrm{\Delta }+1\le k{r}_k\le r_1$ and $1\mathrm{/}2\ge x$. Also $\mathrm{\mid }{A}_j\mathrm{\mid }\ge x^{{\beta }_0}n$ and $a_{\ast }\le r_k$. Therefore its lower count is at least $x^{r_k+r_1+{\beta }_0(h-1)}{n}^h\ge x^{{\gamma }_0}{n}^h$. Both outcomes are excluded. The third gives $E\subseteq A_j$, $D\subseteq Y$ of relative sizes at least $x^{\mathrm{\Delta }-1}=s\mathrm{/}x$, with cross density at most $2x^{R+1}$ in the graph chosen in the previous step.

Because $\mathrm{\mid }E\mathrm{\mid }\ge (s\mathrm{/}x)t_k=t_{k+1}\mathrm{/}x\ge 2t_{k+1}$, [F4] chooses $C\subseteq E$ of exactly $2t_{k+1}$ vertices without increasing its cross density to $D$. Apply [F5] to $D,C$ to get $X\subseteq D$ of size at least $\mathrm{\mid }D\mathrm{\mid }\mathrm{/}2\ge s\mathrm{\mid }Y\mathrm{\mid }$, with degrees into $C$ at most $4x^{R+1}\mathrm{\mid }C\mathrm{\mid }\le (q_{k+1}\mathrm{/}2)\mathrm{\mid }C\mathrm{\mid }$. This is the required one-block processing step.

Process the $k$ labels in any fixed order, starting with $Y=Z$ and replacing $Y$ by $X$ at each step. Before the last step its size is at least $\mathrm{\mid }Z\mathrm{\mid }{s}^{k-1}$, so the preceding construction applies every time. Degree bounds into previously chosen $C_j$ survive restriction of their source set. The final $X$ has size at least $n{s}^k\mathrm{/}2\ge n{x}^{{\beta }_0-1-R}\ge t_{k+1}$: use $k\mathrm{\Delta }+1+R\le k{r}_k+1\le r_1+1<{\beta }_0-1$ and $1\mathrm{/}2\ge x$. Take $D_w\subseteq X$ of size $t_{k+1}$.

For each $j$, the bound from $D_w$ into $C_j$ implies cross density at most $q_{k+1}\mathrm{/}2$. Applying [F5] to $C_j,D_w$ supplies at least $\mathrm{\mid }{C}_j\mathrm{\mid }\mathrm{/}2=t_{k+1}$ vertices with degree into $D_w$ at most $q_{k+1}\mathrm{\mid }{D}_w\mathrm{\mid }$; take exactly that many as $D_j$. The reverse degree bound into $D_j$ follows from the old bound into $C_j$: it is at most $(q_{k+1}\mathrm{/}2)2t_{k+1}=q_{k+1}\mathrm{\mid }{D}_j\mathrm{\mid }$. For two old labels, restricting the target from $A_j$ to $D_j$ changes the bound by a factor at most $1\mathrm{/}s$, giving $q_k\mathrm{/}s=q_{k+1}$ in both directions. Thus these disjoint sets form a $(t_{k+1},q_{k+1})$-blowup on $J\cup \{w\}$, contrary to maximality. This proves the reciprocal-integer case.

For arbitrary allowed $x$, put $N=-\lfloor -1\mathrm{/}x\rfloor$ and $y=1\mathrm{/}N$. By [F1], $1\mathrm{/}x\le N<1\mathrm{/}x+1$, so $x\mathrm{/}(1+x)<y\le x$ and in particular $x^2\le y\le x$. Apply the proved case at $y$ and take final $\beta =2{\beta }_0$, $\gamma =2{\gamma }_0$. Then $y^{{\beta }_0}\ge x^{\beta }$, $y^{{\gamma }_0}\ge x^{\gamma }$, $y^{\alpha }\le x^{\alpha }$, and $y$-sparsity implies $x$-sparsity. Each of the three alternatives therefore implies its required counterpart at $x$, including the original unenlarged $\alpha$.

Induct on $h=\mathrm{\mid }H\mathrm{\mid }$. If $h=1$, take $k_1=k_2=1$; the premise $n<xn$ is impossible. For $h\ge 2$, fix $g\in V(H)$ and let $k_1^{\mathrm{\prime }},k_2^{\mathrm{\prime }}$ be the constants for $H-g$. Apply [F1] with $\alpha =k_1^{\mathrm{\prime }}$ to obtain $\beta ,\gamma$. Set $d_0={\log }_2(2h)>0$, $k_1=\gamma +2d_{0}h$, and $k_2=k_2^{\mathrm{\prime }}+\beta +2d_0$.

If $x^{k_2}n<1$, take $-\lfloor -2{\log }_2(1\mathrm{/}x)\rfloor$ empty blocks. By [F3] this integer is at least the required length, and the width is $0=\lfloor x^{k_2}n\rfloor$. All degree conditions hold by [F2]. Hence assume $x^{k_2}n\ge 1$.

Consider nonempty restricted sequences $(B_1,\dots ,B_k)$ whose first $k-1$ blocks have size at least $x^{k_2}n$ and whose last block has size at least $(2h{)}^{1-k}n$. The one-block sequence $V(G)$ qualifies. All these sequences have length at most $n$, so a maximum length is attained in a finite nonempty family. Fix such a sequence. If $k-1\ge 2{\log }_2(1\mathrm{/}x)$, its first $k-1$ blocks prove the restricted assertion. Otherwise [F4] gives $\mathrm{\mid }{B}_k\mathrm{\mid }\ge 2^{(1-k)d_0}n>x^{2d_0}n\ge x^{2d_0-k_2}>1$. Thus $\mathrm{\mid }{B}_k\mathrm{\mid }\ge 2$.

Apply [F1] inside $G[B_k]$ at $x$ with $\alpha =k_1^{\mathrm{\prime }}$. Its count outcome would give ${\mathrm{ind}}_H(G)\ge {\mathrm{ind}}_H(G[B_k])\ge x^{\gamma }\mathrm{\mid }{B}_k{\mathrm{\mid }}^h>x^{\gamma +2d_{0}h}{n}^h=x^{k_1}{n}^h$, contrary to the premise; the first inequality holds by inclusion of the embedding sets. Its sparse-pair outcome would replace $B_k$ by $A,B$ with $\mathrm{\mid }A\mathrm{\mid }\ge x^{\beta }\mathrm{\mid }{B}_k\mathrm{\mid }>x^{\beta +2d_0}n\ge x^{k_2}n$ and $\mathrm{\mid }B\mathrm{\mid }\ge \mathrm{\mid }{B}_k\mathrm{\mid }\mathrm{/}(2h)\ge (2h{)}^{-k}n$. Earlier degree conditions persist because their target blocks are unchanged and their later vertices are restricted. The new pair meets the last condition, contradicting maximum length.

Therefore [F1] supplies $A\subseteq B_k$ with $\mathrm{\mid }A\mathrm{\mid }\ge x^{\beta }\mathrm{\mid }{B}_k\mathrm{\mid }>x^{\beta +2d_0}n$ and ${\mathrm{ind}}_{H-g}(G[A])<x^{k_1^{\mathrm{\prime }}}\mathrm{\mid }A{\mathrm{\mid }}^{h-1}$. Here $A$ is nonempty and $x\le 1\mathrm{/}(8h)\le 1\mathrm{/}(8(h-1))$, so induction applies. It gives length at least $2{\log }_2(1\mathrm{/}x)$ and width at least $\lfloor x^{k_2^{\mathrm{\prime }}}\mathrm{\mid }A\mathrm{\mid }\rfloor \ge \lfloor x^{k_2^{\mathrm{\prime }}+\beta +2d_0}n\rfloor =\lfloor x^{k_2}n\rfloor$. Floor monotonicity follows from [F3]: if $u\le v$ and $\lfloor u\rfloor >\lfloor v\rfloor$, then $u\ge \lfloor v\rfloor +1>v$. This completes the restricted-sequence induction.