2026/08/05 by Mengyu Cao, Mei Lu, Haixiang Zhang
Mathematics · #math.CO #msc:05C15 #msc:05C35 #msc:05C80
arxiv created 2026/08/05 · arxiv updated 2026/08/06
Let H be a fixed graph with q=e(H)≥3 and containing two adjacent edges, and let ℓ≥ q 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/m2(H). Below a sufficiently small constant multiple of this scale, almost all host edges may be coloured freely; above a sufficiently large constant multiple, the exponential counting rate is governed exactly by a deterministic template-entropy optimisation on complete graphs. An exact Hall-palette inequality evaluates this rate throughout the universal range q≤ℓ≤(q-1)q/(q-2), where the dense-side base is q-1, and a robust form yields counting stability below the endpoint. For arbitrary fixed ℓ, deletion-profile bounds determine the first-order many-colour behaviour and characterise when the (q-1)-colour rate persists for every fixed number of colours. This extends the random Gallai-colouring transition from triangles to every fixed non-matching graph and provides a general mechanism for transferring dense template entropy to sparse random hosts.