Stronger colored-tree embedding conjecture for pseudorandom graph families

Let $\Delta\geq2$. An $(n,D,\lambda)$-graph is a graph with the corresponding order, degree and spectral parameters, and a $[t]$-colored tree is a tree whose edges receive colors in $[t]=\{1,\ldots,t\}$. For a family $\mathcal{G}=\{G_1,\ldots,G_t\}$, write $V(\mathcal{G})$ for its common vertex set and $\Delta_r(\mathcal{T})$ for the maximum degree in color $r$. Stronger colored-tree embedding conjecture. There is a constant $C_\Delta$ such that, for every $t\in\mathbb{N}$ and every family $\mathcal{G}=\{G_1,\ldots,G_t\}$ of $(n,D,\lambda)$-graphs on the same vertex set $V(\mathcal{G})$, every $S\subseteq V(\mathcal{G})$ satisfying

$$|S|\geq C_\Delta^{o(\log n)}\frac{n\lambda}{D}$$

contains every $[t]$-colored tree $\mathcal{T}$ with at most $|S|-100\left(\frac{n\lambda}{D}\right)^2|S|^{-1}$ vertices and

$$\Delta_r(\mathcal{T})\leq\Delta\qquad\text{for each }r\in[t].$$

This would strengthen the available colored-tree embedding result and, as stated in the paper, would imply the almost optimal distance-tree conjecture.