REVIEW 4 minor
Entropy Transference for Rainbow-$H$-Free Colourings of Random Graphs
T0 review · 0 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read This paper proves a transference principle: the exponential number of rainbow-H-free edge-colourings of G(n,p) is governed by a deterministic template-entropy optimisation above the threshold p=n^{-1/m2(H)}, and the rate equals…
desk verdict A complete and correct proof of the rainbow-H-free counting transition for every fixed non-matching H; the deterministic-entropy separation does real work. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the H-admissible palette template on K_n: an assignment of a nonempty colour set to each edge such that the q edge-palettes on every copy of H have no system of distinct representatives. Its entropy is Ent(P)=Σ_e log|P(e)|, and λ(H,ℓ) is the limiting maximal normalised entropy. The key local identity is the Hall-palette inequality: for q nonempty palettes with no SDR, the product of their sizes is at most max_{2≤s≤q} (s-1)^s $ℓ^{{q-s}}$, and this is at most (q-1)^q exactly when ℓ ≤ (q-1)^{q/(q-2)}, with equality forcing all q palettes to be a common (q-1)-set below the endpoint. Sparse regularity together with a uniform embedding lemma transfers this deterministic entropy bound from reduced templates to G(n,p), while a first-moment argument handles the sparse side.
What would settle it
For H=K_4 and ℓ=6, which lies inside the claimed Hall range, one could search over all palette assignments on K_n that give no system of distinct representatives on any K_4 and check whether any assignment for small n has average log-palette size exceeding log 5. If such an assignment exists, Corollary 1.5 would fail; the paper predicts none does. Alternatively, one could compute R_{H,ℓ}(G(n,p)) numerically for moderate n and p above the threshold and compare the empirical exponent with λ(H,ℓ).
Extended reading notes
Core claim
The central claim is a two-sided exponential description of R_{H,ℓ}(G(n,p)), the number of rainbow-H-free ℓ-colourings. For every fixed ℓ≥e(H) and every δ>0, with high probability R_{H,ℓ}(G(n,p)) ≥ $ℓ^{{(1-δ)e(G)}}$ when p ≤ a $n^{{-1/m2(H)}}$, and exp((λ(H,ℓ)-δ)e(G)) ≤ R_{H,ℓ}(G(n,p)) ≤ exp((λ(H,ℓ)+δ)e(G)) when p ≥ A $n^{{-1/m2(H)}}$. Here λ(H,ℓ) is the limiting maximum average logarithmic palette size over all H-admissible templates on complete graphs, that is, palette assignments in which the edges of every copy of H admit no system of distinct representatives. The paper evaluates this rate throughout the range q ≤ ℓ ≤ (q-1)^{q/(q-2)} as λ(H,ℓ) = log(q-1), where q=e(H), and proves a counting-stability version below the endpoint: colourings that stay far from using only q-1 colours have exponentially smaller count.
Load-bearing premise
The dense upper bound relies on a quoted sparse-embedding lemma asserting that, once p is a large constant multiple of $n^{{-1/m2(H)}}$, any collection of regular cluster pairs of positive density arranged like H must contain a transversal copy of H; if that lemma fails for the small density parameter α<1/(3ℓ) or for the partition bound M used in the proof, the upper estimate does not follow.
Editorial extensions
If this is right
- For every fixed non-matching H and every colour count ℓ with e(H) ≤ ℓ ≤ (e(H)-1)^{e(H)/(e(H)-2)}, the dense-side exponential rate of rainbow-H-free colourings of G(n,p) is (e(H)-1)^{e(G)}.
- For H=K_3 and ℓ=3 the theorem recovers the exponential form of the previously known triangle transition.
- If H-e is bipartite for some edge e, then for every fixed ℓ the dense-side rate is log(q-1) per edge, no matter how many colours are allowed.
- For large colour sets, the first-order behaviour is governed by edge-deletion profiles: λ(H,ℓ)/log ℓ tends to the Turán density of the family of one-edge deletions of H.
- Below the Hall endpoint the colourings are counting-stable: any colouring that requires more than ε e(G) recolourings to reduce to q-1 colours occurs with exponentially smaller count.
Reading between the lines
- Editorial inference: if the transference principle is correct, then any future exact evaluation of λ(H,ℓ) for a particular H automatically gives the sparse random counting rate, so the random problem is fully reduced to a deterministic dense optimisation.
- Editorial inference: the paper leaves open whether deletion-profile templates exhaust all obstructions to optimality of the constant (q-1)-palette; a natural testable extension is to compute λ(H,ℓ) for specific pairs such as H=K_4 and ℓ between 7 and 11 to see where the constant-palette rate first fails.
- Editorial inference: the counting-stability theorem suggests a typical-structure description of random rainbow-H-free colourings above the threshold: almost all such colourings either use q-1 colours almost everywhere or pay an exponential entropy penalty, which could support sampling or decomposition algorithms.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies, for a fixed graph H with q=e(H)≥3 that is not a matching, and a fixed integer ℓ≥q, the exponential number R_{H,ℓ}(G(n,p)) of ℓ-edge-colourings of the binomial random graph with no rainbow copy of H. Theorem 1.4 states that below p≤a n^{-1/m_2(H)} the base ℓ survives on almost all edges, while above p≥A n^{-1/m_2(H)} the exponential rate is governed by a deterministic template-entropy constant λ(H,ℓ) up to δ in the exponent. Corollary 1.5 evaluates λ(H,ℓ)=log(q−1) throughout q≤ℓ≤(q−1)^{q/(q−2)}; Theorem 1.6 gives a counting-stability version strictly below the endpoint; Theorem 1.7 gives deletion-profile bounds and characterizes when the (q−1)-colour rate persists for every fixed ℓ. The proofs combine multicolour sparse regularity, the KŁR embedding theorem, Chernoff-type concentration, a local Hall-palette inequality, and a reduced-template entropy dichotomy.
Significance. If the results are correct, this is a substantial and timely contribution to the enumerative anti-Ramsey theory of random graphs. The paper extends the Gallai-colouring transition from triangles to every fixed non-matching graph and, more importantly, separates the random transference from the underlying dense palette optimisation: the deterministic rate λ(H,ℓ) is defined independently of any fitted parameter or hidden normalization, and the sparse and dense bounds are proved by standard, reproducible ingredients. The exact evaluation of λ(H,ℓ)=log(q−1) in a universal Hall range, the robust counting stability below the endpoint, and the deletion-profile bounds for large colour sets give a coherent and fairly complete picture. The only genuinely external input, Lemma 2.2, is stated explicitly and applied in a standard KŁR regime; I found no circular step or unsupported parameter dependence in the manuscript.
minor comments (4)
- [§3.1] In the proof of Proposition 3.2, the text says 'Theorems 2.4 and 2.5 give local entropy at most q log(q−1)'; these should be Lemma 2.4 and Proposition 2.5, respectively.
- [§4] Throughout §4, the statements of Lemma 2.1, Lemma 2.2, Lemma 2.3, Proposition 3.1, and Lemma 4.1 are cited as 'Theorem 2.1', 'Theorem 2.2', 'Theorem 2.3', 'Theorem 3.1', and 'Theorem 4.1'; please harmonize the cross-referencing with the actual labels.
- [§4.2] The sentence after Eq. (4.6) says 'Combining this theorem with Theorem 3.3 ... proves Theorem 1.5'; this should refer to Corollary 3.3 and Corollary 1.5, respectively.
- [§5.3] The displayed boundary values '25, 27, 14 4/3 ≈ 33.742' are typeset ambiguously; please write the exponent explicitly (for example 14^{4/3}) and state which deletion profile yields each boundary value.
Circularity Check
No significant circularity: the derivation is self-contained and the external inputs are standardly applied.
full rationale
The paper's central derivation chain is not circular. The deterministic entropy rate λ(H,ℓ) is defined independently as the limiting maximum template entropy over H-admissible palettes, and the random dense upper bound reduces the counting problem to this quantity via sparse regularity and the external KŁR-type embedding lemma (Lemma 2.2), without assuming the conclusion. The lower bound samples from an extremal template using concentration of a sum of independent random contributions, again independent of the upper-bound argument. The exact Hall-range evaluation λ(H,ℓ)=log(q−1) follows from the local Hall-palette inequality and a double-counting argument, not from any fitted parameter or self-citation. No parameter is fitted to a subset of data and then renamed as a prediction; the only external theorem used as a black box, Conlon–Gowers–Samotij–Schacht, is cited with its own machine-independent proof and applied in its standard regime. The paper contains no self-citation of the target result and no uniqueness claim imported from the authors' prior work. The deletion-profile and clique comparisons are explicitly framed as separate deterministic structural questions. I therefore find no circular step warranting a nonzero score.
Assumptions & free parameters
assumptions (7)
- standard math Uniform KŁR embedding theorem as stated in Lemma 2.2, over all choices of h disjoint sets and ε-regular subgraphs of density at least α.
- standard math Sparse regularity lemma for multiple subgraphs of an upper-uniform host (Kohayakawa; Gerke-Steger).
- standard math Erdős-Stone-Simonovits theorem for finite families.
- standard math Hall's theorem.
- standard math Chernoff and union-bound concentration for G(n,p).
- domain assumption H is fixed, non-matching, with q=e(H)≥3 and two adjacent edges; ℓ≥q is fixed.
- domain assumption The host is the binomial random graph G(n,p) with p in the sparse or dense regimes around n^{-1/m2(H)}.
Cite this review
Pith. "Pith review of Entropy Transference for Rainbow-$H$-Free Colourings of Random Graphs." pith.science (2026). https://pith.science/paper/PLKH2GVO
@misc{pith2026260804845,
author = {Pith},
title = {Pith review of: Entropy Transference for Rainbow-$H$-Free Colourings of Random Graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/PLKH2GVO}},
note = {Machine review of arXiv:2608.04845}
}
abstract
Let $H$ be a fixed graph with $e(H)\ge3$ 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\'an 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\'an 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.
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.