A wide concave support-regular blockade contains a rainbow rooted tree

Let $\alpha$ and $\beta$ be the greatest heights of a $\mathcal{B}$-left-rainbow and a $\mathcal{B}$-right-rainbow rooted complete $\delta$-ary tree, respectively. The single vertex gives both a starting value, and settles the case $\eta =0$. Suppose $\eta \ge 1$ and there is no rainbow $T(\delta ,\eta )$. Then $\alpha ,\beta <\eta$; reverse the blockade if needed so that $\alpha \le \beta$. For $0\le q\le \delta$, define $Q(q)$ by joining a new root to the roots of $q$ disjoint copies of $T(\delta ,\alpha )$. Put $R(q)=Q(q)$ for $q\le \delta$; for $q=\delta +i$, $1\le i\le \delta$, use $\delta -i$ copies of $T(\delta ,\alpha )$ and $i$ copies of $T(\delta ,\beta )$ instead. Let $S(q)$, $0\le q\le \delta$, consist of $q+1$ copies of $T(\delta ,\alpha )$ with the root of the first joined to the other $q$ roots and retained as root. Let ${\gamma }_3$ be maximal such that a left-rainbow $S({\gamma }_3)$ occurs. Such a copy exists at $q=0$. Because $Q(\delta )=T(\delta ,\alpha +1)$, $R(2\delta )=T(\delta ,\beta +1)$ and $S(\delta )$ contains a rooted $T(\delta ,\alpha +1)$, none of these three extremal cases can occur.

Call a minor $(C_1,\dots ,C_k,C_K)$, with $C_i\subseteq B_i$, $({\gamma }_1,{\gamma }_2)$-anchored if some $Y\subseteq B_{k+1}\cup \cdots \cup B_{K-1}$ is anticomplete to $C_2,\dots ,C_k$, every $v\in C_1$ roots a left-rainbow $Q({\gamma }_1)$ inside $Y\cup \{v\}$, and every $v\in C_K$ roots a right-rainbow $R({\gamma }_2)$ there. The original blockade, with $k=K-1$, $Y=\mathrm{\varnothing }$ and ${\gamma }_1={\gamma }_2=0$, is anchored. Choose ${\gamma }_0={\gamma }_1+{\gamma }_2$ maximal among anchored minors of length at least $K-2{\delta }^{\eta +1}{\gamma }_0$ and width at least $W{2}^{-3{\gamma }_0}$; trim its blocks equally and call their common size $W^{\mathrm{\prime }}$. From step 1.1, ${\gamma }_1,{\gamma }_3<\delta$ and ${\gamma }_2<2\delta$. Hence ${\gamma }_0\le 3\delta -2$ and $W^{\mathrm{\prime }}\ge W{2}^{-9\delta +6}\ge 64ϵn$.

Let $s=\mathrm{\mid }S({\gamma }_3)\mathrm{\mid }$ and $t=\mathrm{\mid }T(\delta ,\beta )\mathrm{\mid }$, so $s,t\le {\delta }^{\eta +1}$, and put $h=k+1-s-t$. The anchor length bound gives $h\ge K-2{\delta }^{\eta +1}({\gamma }_0+1)\ge 2{\delta }^{\eta +1}\ge 2$ because $K\ge 6{\delta }^{\eta +2}$ and ${\gamma }_0+1\le 3\delta -1$. Put $r=\lceil W^{\mathrm{\prime }}-\rho W\rceil$; then $r\ge 63\rho W\ge 63ϵn$. Support-uniformity gives a left-rainbow $S({\gamma }_3)$ on the consecutive blocks $B_h,\dots ,B_{h+s-1}$ and a right-rainbow $T(\delta ,\beta )$ on $B_{h+s},\dots ,B_k$. Greedily pack $r$ pairwise vertex-disjoint copies $E_1,\dots ,E_r$ of the former in the corresponding $C$-blocks, and $r$ pairwise vertex-disjoint copies $F_1,\dots ,F_r$ of the latter. Indeed, if a maximal packing had $r^{\mathrm{\prime }}<r$ members, removing its vertices from each used $C$-block would leave width $W^{\mathrm{\prime }}-r^{\mathrm{\prime }}\ge \rho W$, contradicting $(\rho ,\tau )$-support-invariance of the appropriate sub-blockade of $\mathcal{B}$. The two packings use disjoint intervals of blocks.

For $D\subseteq C_1\cup C_K$, let $a(D)$ count the indices $i\in [r]$ for which $D$ meets $E_i\cup F_i$, and let $b(D)$ count those for which it meets a nonroot vertex. Choose $D$ inclusion-maximal subject to $a(D)\le r\mathrm{/}2$ and $b(D)\ge a(D)\mathrm{/}4$. At least $r\mathrm{/}2\ge ϵn$ roots of the $E_i$ have no neighbor in $D$, so coherence implies $\mathrm{\mid }D\mathrm{\mid }<ϵn$. The untouched roots in $B_h$ and $B_k$ also show that $D$ $\lambda$-misses both blocks. Concavity therefore says that $D$ does not $\lambda$-cover any of $B_{h+1},\dots ,B_{k-1}$. Every internal meeting of an $E_i\cup F_i$ uses a nonroot vertex in those interior blocks, so $b(D)\le \lambda (s+t-2)W$. Since $s+t\le 2{\delta }^{\eta +1}$, $\lambda \le \rho {\delta }^{-\eta -1}$, and $r\ge 63\rho W$, we get $a(D)\le 4b(D)\le 8\rho W\le 8r\mathrm{/}63\le r\mathrm{/}2-ϵn$.

Let $Z\subseteq (C_1\cup C_K)\setminus D$ be the vertices meeting at least one $E_i\cup F_i$, and let $C\subseteq [r]$ be the indices whose $E_i\cup F_i$ is anticomplete to $D$. Since $r\ge ϵn$, coherence bounds the vertices of $C_1\cup C_K$ missing every $E_i\cup F_i$ by $<ϵn$; hence $\mathrm{\mid }Z\mathrm{\mid }>2W^{\mathrm{\prime }}-2ϵn$. Every $v\in Z$ meets at least one pair indexed by $C$: otherwise adjoining it to $D$ leaves $a$ unchanged and cannot decrease $b$, contrary to maximality. If $v\in Z$, the number of $i\in C$ it meets internally is less than one quarter of the number it meets at all. Otherwise $D\cup \{v\}$ would satisfy the two defining inequalities of $D$: its new $a$ is at most $a(D)+ϵn\le r\mathrm{/}2$ (one vertex has fewer than $ϵn$ neighbors among the disjoint rooted trees), and its new $b$ would be at least a quarter of its new $a$. More directly, maximality says $b(D\cup \{v\})<a(D\cup \{v\})\mathrm{/}4$; subtract $b(D)\ge a(D)\mathrm{/}4$.

Order the indices of $C$ uniformly at random. For each $v\in Z$, the first pair it meets among $C$ is met properly (at one or both roots but at no nonroot vertex) with probability $>3\mathrm{/}4$ by step 5.1. On each side $C_1,C_K$, the probability that fewer than half its vertices of $Z$ are proper-first is $<1\mathrm{/}2$: otherwise the expected number of proper-first vertices on that side would be at most three quarters of its size. Thus one order makes both sides at least half proper-first. Relabel all pairs so that the chosen order of $C$ occupies the initial segment $1,\dots ,\mathrm{\mid }C\mathrm{\mid }$, with every pair outside $C$ placed afterward, and call the set of proper-first vertices $X$. Then $\mathrm{\mid }X\cap C_1\mathrm{\mid }\ge \mathrm{\mid }Z\cap C_1\mathrm{\mid }\mathrm{/}2$ and likewise at $C_K$; moreover each side has at least $W^{\mathrm{\prime }}\mathrm{/}2-ϵn$ vertices in $X$. Each $v\in X$ has a first proper meeting index, its happiness, and one of four types $(1,E),(1,F),(K,E),(K,F)$ according to its side and which root it meets.

As $\mathrm{\mid }X\mathrm{\mid }>W^{\mathrm{\prime }}-ϵn\ge 63W^{\mathrm{\prime }}\mathrm{/}64$, one side has at least $W^{\mathrm{\prime }}\mathrm{/}4$ vertices of $X$. Choose the first index $m$ at which either side has at least $W^{\mathrm{\prime }}\mathrm{/}4$ vertices of happiness at most $m$. At that side select a set $U$ of at least $W^{\mathrm{\prime }}\mathrm{/}8$ such vertices all having one of the two types there. Let $Y^{\mathrm{\prime }}$ be the union of vertices of $E_i,F_i$ over $i\le m$. On each endpoint side fewer than $W^{\mathrm{\prime }}\mathrm{/}4$ vertices of $X$ have happiness before $m$, and at most $2ϵn$ have happiness exactly $m$ because each of the two roots has degree $<ϵn$. Thus each side has at least $W^{\mathrm{\prime }}\mathrm{/}4-3ϵn>\lambda W$ vertices of $X$ anticomplete to $Y^{\mathrm{\prime }}$. Every $B_j\cap Y^{\mathrm{\prime }}$, $h\le j\le k$, therefore $\lambda$-misses both $B_1$ and $B_K$. By concavity it cannot $\lambda$-cover any $B_i$ with $2\le i<h$. Consequently each $C_i$ in this latter range has at most $(s+t)\lambda W\le 2\rho W\le W^{\mathrm{\prime }}\mathrm{/}32$ vertices meeting $Y^{\mathrm{\prime }}$, and has more than $W^{\mathrm{\prime }}\mathrm{/}8$ vertices anticomplete to $Y^{\mathrm{\prime }}$.

We now enlarge the anchor with $Y^{\mathrm{\prime }}$. In every case choose $\lceil W^{\mathrm{\prime }}\mathrm{/}8\rceil$ vertices from $U$ on its active endpoint, from the opposite endpoint anticomplete to $Y^{\mathrm{\prime }}$, and from each $C_i$ with $2\le i<h$ anticomplete to $Y^{\mathrm{\prime }}$. The preceding bounds permit these choices; $Y$ was already anticomplete to the intermediate blocks. The new minor has indices $1,\dots ,h-1,K$, length $h\ge K-2{\delta }^{\eta +1}({\gamma }_0+1)$, and width at least $W^{\mathrm{\prime }}\mathrm{/}8\ge W{2}^{-3({\gamma }_0+1)}$.

If $U$ has type $(1,E)$, each $v\in U$ joins properly to the root of an $S({\gamma }_3)$ in $Y^{\mathrm{\prime }}$, which contains a rooted $T(\delta ,\alpha )$; adjoining this to the anchored $Q({\gamma }_1)$ at $v$ supplies a left-rainbow $Q({\gamma }_1+1)$. The same works for type $(1,F)$ because $\beta \ge \alpha$ and $F_i=T(\delta ,\beta )$ contains a rooted $T(\delta ,\alpha )$. Type $(K,F)$ supplies a right-rainbow $R({\gamma }_2+1)$: before ${\gamma }_2=\delta$ it adds an $\alpha$-branch, afterward a $\beta$-branch. Type $(K,E)$ with ${\gamma }_2<\delta$ likewise adds an $\alpha$-branch. Each contradicts maximality of ${\gamma }_0$ using the new anchored minor from step 8.1.

In the only remaining case, $U$ has type $(K,E)$ and ${\gamma }_2\ge \delta$. Pick $v\in U$ and the $E_i=S({\gamma }_3)$ it meets properly. The anchored $R({\gamma }_2)$ rooted at $v$ contains a rooted $T(\delta ,\alpha )$; join that branch at $v$ to the root of $E_i$. The sets $Y$ and $Y^{\mathrm{\prime }}$ are anticomplete, the meeting is proper, and all used blocks are distinct. This yields a left-rainbow $S({\gamma }_3+1)$, contrary to maximality of ${\gamma }_3$. Every case contradicts the assumption in step 1.1, so a rainbow $T(\delta ,\eta )$ exists.