Qid maximal blowup trichotomy

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$.