Entropy Transference for Rainbow-$H$-Free Colourings of Random Graphs

Abstract

Let $H$ be a fixed graph with $e(H)\ge 3$ that contains two adjacent edges, and let $\ell \ge e(H)$ be fixed. We establish an entropy-transference principle for rainbow-$H$-free edge-colourings of the binomial random graph at the natural scale $p=n^{-1/m_2(H)}$. Writing $R_{H,\ell }(G)$ for the number of such colourings and $\lambda (H,\ell )$ for the rainbow entropy--Turán density on complete graphs, we show that, with high probability, the per-edge logarithmic counting rate can be made arbitrarily close to $\log \ell$ below a sufficiently small constant multiple of this scale, and arbitrarily close to $\lambda (H,\ell )$ above a sufficiently large constant multiple. Thus the dense-side counting rate on a sparse random host is governed exactly by a deterministic entropy--Turán parameter on complete graphs. We further investigate this parameter, obtaining partial exact evaluations, corresponding counting-stability results, and its first-order asymptotic behaviour as the number of colours tends to infinity. This extends the random Gallai-colouring transition from triangles to every fixed non-matching graph containing at least three edges, and provides a general mechanism for transferring complete-graph template entropy to sparse random hosts.