Exact-palette rainbow embeddings in uniformly coloured pseudorandom graphs

Abstract

We study rainbow spanning configurations in bijumbled graphs whose edges are coloured independently and uniformly from a prescribed palette. For $n$-vertex $(p,\beta)$-bijumbled graphs with minimum degree at least a fixed positive multiple of $pn$, we obtain rainbow perfect matchings and Hamilton cycles with a sufficient palette surplus of order $(\log n)/p$, assuming $pn=\omega(\log n)$ and $\beta\le cpn$ for a sufficiently small constant $c$. For each prescribed spanning tree of fixed maximum degree $\Delta\ge2$, a surplus of order $L_{n,\Delta}(\log n)/p$ suffices under $\beta\le cpn/L_{n,\Delta}$, where $L_{n,\Delta}=\Delta^{5\sqrt{\log n}}$. The palette surplus is sublinear under these hypotheses. These results use a McDiarmid-type coupling and retain the discrepancy scales of the relevant deterministic embedding theorems. We also prove exact-palette results, using precisely as many colours as the number of edges of the target configuration. After independent edge percolation at rate $\rho$, it is shown that a rainbow perfect matching or Hamilton cycle exists asymptotically almost surely when $\rho pn \ge C(\log n)^2$ and $\beta\le\gamma pn$ for appropriate constants $C$ and $\gamma$. We obtain corresponding results for each prescribed bounded-degree spanning tree and for clique factors under appropriate stronger hypotheses. The exact-palette proofs construct spread measures from uncoloured containment estimates and apply the rainbow threshold theorem of Han and Yuan.