Every forest-free graph has a linear anticomplete pair or a linear-degree vertex

We prove the following quantitative claim $P(T)$ for every finite tree $T$: there are an integer $K_T\ge 1$ and a real $d_T\ge 1$ such that whenever a graph $F$ has a blockade $\mathcal{B}$ of length at least $K_T$ and width $W$, and $F$ is $W\mathrm{/}(d_T\mathrm{\mid }F\mathrm{\mid })$-coherent, it contains a $\mathcal{B}$-rainbow induced copy of $T$. For the one-vertex tree take $K_T=d_T=1$. Assume the claim for the tree $T^{\mathrm{\prime }}=T-v$ obtained by deleting a leaf $v$ from a larger tree $T$, and let $u$ be the neighbor of $v$.

Embed $T$ as an induced subtree of $T(\delta ,\eta )$ for integers $\delta \ge 2$, $\eta \ge 0$. Set $\tau ={\delta }^{\eta +1}$, $\rho =2^{-9\delta }$, $\lambda =\rho {\delta }^{-\eta -1}$, $\kappa =\lambda \mathrm{/}2$, and $r=\lceil (\mathrm{\mid }T\mathrm{\mid }-1)\mathrm{/}\kappa \rceil$. Enlarge $K_{T^{\mathrm{\prime }}}$ to a multiple $K^{\mathrm{\prime }}$ of $r$ satisfying $K^{\mathrm{\prime }}\ge 6r{\delta }^{\eta +2}$, and put $k=K^{\mathrm{\prime }}\mathrm{/}r$. Choose $K$ from [L2] for parameters $K^{\mathrm{\prime }},\tau ,\kappa$; put $M=2^K{\tau }^{\tau }$ and $d={\kappa }^{-M}\max \{d_{T^{\mathrm{\prime }}},2^{9\delta }\mathrm{/}r\}$. We claim $K_T=K$ and $d_T=\max \{1,d\}$ work.

Let $F$ and $\mathcal{B}$ satisfy the claim's hypotheses for $K,d$, write $n=\mathrm{\mid }F\mathrm{\mid }$ and $ϵ=W\mathrm{/}(dn)$, and suppose there is no rainbow $T$. By [L2], $\mathcal{B}$ has an equicardinal minor ${\mathcal{B}}^{\mathrm{\prime }}=(B_1^{\mathrm{\prime }},\dots ,B_{K^{\mathrm{\prime }}}^{\mathrm{\prime }})$ of width $w\ge {\kappa }^{M}W$, which is $\tau$-support-uniform and $(\kappa ,\tau )$-support-invariant. Since $w\ge d_{T^{\mathrm{\prime }}}ϵn$, $ϵ$-coherence implies $w\mathrm{/}(d_{T^{\mathrm{\prime }}}n)$-coherence. Apply $P(T^{\mathrm{\prime }})$ to find a rainbow copy of $T^{\mathrm{\prime }}$. Order its vertices by block index, call the resulting ordered tree $J$, write $t=\mathrm{\mid }{T}^{\mathrm{\prime }}\mathrm{\mid }$, and let the image of $u$ be its $j$th vertex.

No set $X$ lying in blocks of ${\mathcal{B}}^{\mathrm{\prime }}$ outside selected indices $i_1<\cdots <i_t$ can $\kappa$-cover $B_{i_j}^{\mathrm{\prime }}$ and $\kappa$-miss every other selected block. If such $X$ existed, contract $B_{i_j}^{\mathrm{\prime }}$ to vertices with a neighbor in $X$, each other selected block to vertices without a neighbor in $X$, and leave the remaining blocks unchanged. This has width at least $\kappa w$. Support-invariance and support-uniformity preserve a copy of $J$ on the selected support. A neighbor in $X$ of its $j$th vertex then has no neighbor among its other vertices, giving a rainbow $T$, a contradiction.

Group consecutive runs of $r$ blocks of ${\mathcal{B}}^{\mathrm{\prime }}$ into $C_h=B_{r(h-1)+1}^{\mathrm{\prime }}\cup \cdots \cup B_{rh}^{\mathrm{\prime }}$, $1\le h\le k$. This is an equicardinal blockade $\mathcal{C}$ of width $rw$. It is $\lambda =2\kappa$-concave. Indeed, if $X$ outside three selected superblocks $C_{h_1},C_{h_2},C_{h_3}$ covered the middle one and missed the two outer ones at level $2\kappa$, some constituent middle block would be $\kappa$-covered. Unless step 4.1 applied, fewer than $j-1$ constituent blocks of the left superblock or fewer than $t-j$ of the right could be $\kappa$-missed. On that side fewer than $t$ blocks have as many as $w$ nonneighbors in $X$; every other constituent block has fewer than $\kappa w$. Its total nonneighbors would be less than $tw+(r-t)\kappa w$, while $2\kappa$-missing the side requires at least $2\kappa rw$. Thus $t(1-\kappa )>\kappa r$, impossible because $r\ge t\mathrm{/}\kappa$.

The superblock blockade is also $\tau$-support-uniform and $(\kappa ,\tau )$-support-invariant. To see this, a rainbow copy of an ordered tree on the superblocks is already rainbow on constituent blocks, and support-uniformity of ${\mathcal{B}}^{\mathrm{\prime }}$ places it on any chosen constituent block of each selected superblock. If each selected superblock is contracted to at least $\kappa rw$ vertices, one constituent block retains at least $\kappa w$ vertices. Support-invariance of ${\mathcal{B}}^{\mathrm{\prime }}$ then preserves the copy on those constituents. Since $\kappa \le \rho$, this also gives $(\rho ,\tau )$-support-invariance. Moreover $k\ge 6{\delta }^{\eta +2}$ and $rw\ge r{\kappa }^{M}W\ge 2^{9\delta }ϵn$. Thus [L3] applies to $\mathcal{C}$ and gives a rainbow $T(\delta ,\eta )$, containing a rainbow induced $T$. This contradicts step 3.1 and proves $P(T)$ by induction.

Choose a tree $T$ containing $H$ as an induced subgraph: join the components of $H$ in a chain through new intermediate vertices; the case $H=\mathrm{\varnothing }$ has no nonempty $H$-free graph. Let $K_T,d_T$ satisfy $P(T)$, enlarge $d_T$ if needed so $d_T\ge 1$, and choose $0<{ϵ}_H\le (2K_T{d}_T{)}^{-1}$. Every ${ϵ}_H$-coherent graph $F$ has ${ϵ}_H\mathrm{\mid }F\mathrm{\mid }>1$: otherwise its maximum degree is zero, and two singleton anticomplete sets violate coherence. Hence $\mathrm{\mid }F\mathrm{\mid }>1\mathrm{/}{ϵ}_H\ge 2K_T{d}_T$. Partition off $K_T$ disjoint blocks, each of size at least $\mathrm{\mid }F\mathrm{\mid }\mathrm{/}(2K_T)\ge d_T{ϵ}_H\mathrm{\mid }F\mathrm{\mid }$. By $P(T)$, $F$ contains induced $T$, hence induced $H$.

If the given $H$-free $G$ had neither a vertex of degree at least ${ϵ}_H\mathrm{\mid }G\mathrm{\mid }$ nor an anticomplete pair with both sides at least ${ϵ}_H\mathrm{\mid }G\mathrm{\mid }$, it would be ${ϵ}_H$-coherent. Step 7.1 would then give an induced $H$, contrary to the hypothesis. Thus one of the two alternatives holds for the same constant ${ϵ}_H$ in every $H$-free graph.