Tame colouring profiles — smoothness/tail conditions making second-moment analysis of random-graph colourings tractable

Statement

Setting. Fix $p\in(0,1)$, let $G_{n,p}$ (or the edge-count analogue $G_{n,m}$, $m=\lfloor pN\rfloor$, $N=\binom n2$) be the random graph, and consider colourings $\Pi=(V_1,\dots,V_k)$ of $G$: ordered partitions of the vertex set into independent sets. A colouring profile $\mathbf k=(k_u)_{1\le u\le n}$ records, for each size $u$, the number $k_u$ of colour classes of that size (Def. 2.1 of the source). For a profile $\mathbf k$ let $X_{\mathbf k}$ count colourings of $G$ with that exact profile, and $\bar X_{\mathbf k}=X_{\mathbf k}/\prod_u k_u!$ the *unordered* count. The goal of the whole machinery is: prove $X_{\mathbf k}>0$ whp for some well-chosen profile $\mathbf k$ (i.e. a colouring with that shape exists), using the second moment / Paley–Zygmund method $\Pr(Z>0)\ge \mathbb E[Z]^2/\mathbb E[Z^2]$ applied to (a restriction of) $X_{\mathbf k}$.

Definition (tame colouring profile, Def. 2.3). Fix $0<p<1$, $m=\lfloor pN\rfloor$, let $a=a(n)=\alpha_0(n)-O(1)$ with $a\le \alpha$ (here $\alpha=\alpha(n)$ is the graph's independence number and $\alpha_0$ its first-moment approximation, $\alpha_0 = 2\log_b n - 2\log_b\log_b n + 2\log_b(e/2)+1$, $b=1/(1-p)$), and let $\mathbf k=\mathbf k(n)$ be a sequence of complete $a$-bounded $k$-colouring profiles (every colour class has size $\le a$). Then $\mathbf k$ is tame if there is a constant $c\in(0,1)$ and an increasing function $\gamma:\mathbb N_0\to\mathbb R$ with $\gamma(x)\to\infty$ as $x\to\infty$, such that, writing $\kappa_u = uk_u/n$ (fraction of vertices in colour classes of size $u$):

a) Tail/smoothness condition: $\kappa_u < b^{-(\alpha-u)\gamma(\alpha-u)}$ for all $1\le u\le a$ and $n$ large enough — i.e. the profile's mass decays *super-geometrically fast* as class size $u$ moves away from $\alpha$ (equivalently: no fat tail of unusually small colour classes);

b) Non-degeneracy condition: $\ln\mathbb E_m[\bar X_{\mathbf k}] \gg -n^{1-c}$ — the expected number of colourings with this profile is not exponentially-too-small (in a mild sense; the main theorem below needs the sharper $\ln\mathbb E_m[\bar X_{\mathbf k}]\gg\ln n$).

The authors note explicitly that condition (a) is a *convenient sufficient* condition chosen to make the second-moment computation tractable, and conjecture the result should hold under the strictly weaker "true" second-moment-type condition that $\sum_u (a-u)^2\kappa_u = O(1)$ (a bounded-variance condition on class-size deviation from $a$) — tameness is a clean, checkable suflicient strengthening of that.

Main theorem (Thm 2.5, the general second-moment result). Let $\varepsilon>0$ be fixed, $a=a(n)=\alpha_0-O(1)$ with $\mu_a := \mathbb E_p[\#\{a\text{-sets}\}] \ge n^{1+\varepsilon}$ (many independent sets of size $a$ exist in expectation). Let $\mathbf k$ be a tame $a$-bounded profile with $\ln\mathbb E_m[\bar X_{\mathbf k}]\gg\ln n$, and suppose additionally that partial sub-profiles are not too rare (a technical lower bound (2.4) on $\mathbb E_p[\bar X_{\boldsymbol\lambda}]$ for all $\boldsymbol\lambda\le\boldsymbol\kappa$ with bounded-away-from-$\{0,1\}$ mass). Then $$ \Pr_m(X_{\mathbf k}>0) \gtrsim \exp\!\Big(-\frac{k_a^2}{\mu_a} - O(M_1)\Big),\qquad M_1=\frac{k_a^4\ln^2 n}{n\mu_a^2}. $$ In particular if additionally $\mu_a\gg n^2/\ln^2 n$ then whp $G_{n,m}$ has a colouring with profile $\mathbf k$ (Thm 2.6).

Facts

- The obstruction tameness is designed to remove. Taking the second moment of the *raw* colouring-count $X_{\mathbf k}$ directly is intractable because two colourings with the same profile can overlap in many structurally different ways, and this correlation structure is impossible to control in general. Tameness (fast-decaying tail on small colour classes) plus a further restriction of the random variable (see Technique below) is exactly what tames this correlation structure enough for a Paley–Zygmund argument to close. - Source paper: Annika Heckel & Konstantinos Panagiotou, *"Colouring random graphs: Tame colourings"*, arXiv:2306.07253 (v3, Sep 2024). Introduces the term "tame" for this purpose. - Application 1 — two-point concentration of the $t$-bounded chromatic number (Thm 1.1). For $p=1/2$, $a=\alpha(n)-2$, there is $k=k(n)$ with $\chi_a(G_{n,m})\in\{k,k+1\}$ whp, where $\chi_a$ is the minimum number of colours in an $a$-bounded colouring (no colour class larger than $a$). This is proved by exhibiting a tame near-optimal $a$-bounded profile $\mathbf k^*$ (via the "optimal profile" analysis of §7) and applying Thm 2.5/2.6 to it. - Application 2 — interval bound for the plain chromatic number (Thm 1.2). For $a=a(n)$ with $n^{1.1}<\mu_a<n^{2.9}$ (equivalently $a\in\{\alpha-1,\alpha-2\}$), whp $\chi_a(G_{n,1/2}) = \mathbf k_a + O(n^{0.99})$, where $\mathbf k_a$ is the $a$-bounded first-moment threshold. This sharpens the explicit bounds on $\chi(G_{n,1/2})$ and (combined with Heckel–Riordan 2023, arXiv:2103.14014) completes the proof that $\chi(G_{n,1/2})$ is not whp concentrated on any sequence of intervals of length $\sqrt n\ln\ln n/\ln^3 n$ — nearly matching Alon's classical upper bound $\sqrt n/\ln n$ (Alon, in Alon–Spencer, *The Probabilistic Method*), and resolving (up to a power of $\ln n$) a question Erdős posed in the appendix of the first edition of that book and that Bollobás popularised ("How sharp is the concentration of the chromatic number?", *Combin. Probab. Comput.* 2004). - Application 3 — two-point concentration of the equitable chromatic number (Thm 1.3). For fixed constant $0<p<1-1/e$, whp the equitable chromatic number $\chi_=(G_{n,m})\in\{k,k+1\}$ for some $k=k(n)$. - The "Zigzag Conjecture." Bollobás, Morris, Riordan, Smith and the authors conjecture the concentration-interval length of $\chi(G_{n,1/2})$ "zigzags" between $n^{1/4+o(1)}$ and $n^{1/2+o(1)}$; Theorem 1.1 (two-point concentration once colour classes of size $\alpha,\alpha-1$ are fixed) is stated as direct evidence justifying the conjecture's main structural hypothesis — that only the two largest independent-set sizes $\alpha,\alpha-1$ can be sources of non-concentration. - Historical chain this sits in: Erdős–Rényi 1960 (question posed) → Grimmett–McDiarmid 1975 ($\Theta(n/\ln n)$ order) → Bollobás 1987 (asymptotic value, via first martingale/second-moment-flavoured tools) → Shamir–Spencer 1987 (concentration interval $O(\sqrt n)$ via Azuma–Hoeffding) → Alon–Krivelevich 1997 (two-value concentration for sparse $p$) → Achlioptas–Naor 2005 (explicit two-value concentration for $p=d/n$, the first paper to push a delicate second-moment-of-colouring-count computation this far) → Coja-Oghlan–Panagiotou–Steger 2008 (three explicit values) → Heckel 2021 (arXiv:1906.11808, first non-concentration result) → Heckel–Riordan 2023 (arXiv:2103.14014, sharper non-concentration, "How does the chromatic number of a random graph vary?") → Heckel–Panagiotou 2023/2024 (this paper). - The critical constant $x_0\approx 0.02905$. The lower bound $\mu_a\ge n^{1.1}$ in Thm 1.2 (and $\mu_a\ge n^{1.05}$ in the technical Lemma 7.20) is not an artefact: the authors show the optimal $a$-bounded profile genuinely changes character when $\mu_a \lesssim n^{1+x_0-\varepsilon}$ — below this threshold the optimal profile contains an *unrealisable* sub-profile (expected number of partial colourings with exactly $k_a^*$ disjoint $a$-sets is $\exp(-\Theta(n))$), so condition (2.4)/tameness genuinely fails and the method breaks down, not just the proof.

Technique

When it applies. Whenever one wants to show a random graph (or similarly, a random hypergraph / random set system under a product measure) has a combinatorial structure of a prescribed *shape* — here, a colouring with prescribed colour-class-size profile — and a first-moment (expectation) computation shows the expected count is large, but a naive second-moment computation on the full count is intractable because of uncontrolled overlap structure between two random instances of that shape.

Why it works — the two-step mechanism

1. Restrict to a "well-separated" sub-count $Z_{\mathbf k}\le X_{\mathbf k}$ first (§4.1 of the source). Rather than taking the second moment of $X_{\mathbf k}$ directly, define $Z_{\mathbf k}=\sum_{\pi\text{ of profile }\mathbf k}\mathbb 1_{A_\pi\cap B_\pi\cap C_\pi\cap D_\pi}$, where $A_\pi$ = "$\pi$ is a valid colouring" and $B_\pi,C_\pi,D_\pi$ are combinatorial *dissimilarity* events ruling out partitions $\pi$ that could overlap another same-profile partition $\pi'$ in a structurally messy way (e.g. an independent set spread across many parts of $\pi$ in an irregular pattern, or "almost-full" overlaps between different-sized classes). The key structural fact proved (Fact 6.2) is that for a relevant pair $(\pi,\pi')$ satisfying these events, every colour class of $\pi$ is *either* exactly identical to a class of $\pi'$, *or* "scrambled" (spread almost-uniformly across many classes of $\pi'$), with only $O(\ln^3 n)$ exceptional parts in between. This dichotomy is what makes the correlation between the events "$\pi$ is a colouring" and "$\pi'$ is a colouring" analytically tractable: after removing identical shared classes, the residual overlap behaves close to independent, because it is *forced* to be either near-zero (spread thin) or governed by explicit combinatorial identities. 2. The tameness tail condition controls the (still large) sum over overlap patterns. Even after restricting to $Z_{\mathbf k}$, bounding $\mathbb E[Z_{\mathbf k}^2]/\mathbb E[Z_{\mathbf k}]^2$ requires summing contributions over every possible "overlap sequence" (how many colour classes of size $u$ vs. $v$ overlap in a block of size $x$, for all $u,v,x$) between two partitions of profile $\mathbf k$ (Definition 6.6–6.8, McKay's theorem on 0–1 matrices with prescribed margins, §6.2.2). This sum is only summable/boundable because tameness's fast-decaying tail condition (a) forces $k_u$, hence the number of "small" colour classes far from size $\alpha$, to vanish super-geometrically — so the dominant contribution to the second moment comes entirely from the *largest*-class overlaps (size $\approx a$), which are exactly the terms producing the $k_a^2/\mu_a$ main term in the theorem; everything else is absorbed into lower-order error terms $M_1, M_2$. 3. Paley–Zygmund closes the argument: since $Z_{\mathbf k}>0\Rightarrow X_{\mathbf k}>0$, and $\mathbb E[Z_{\mathbf k}]\sim\mathbb E[X_{\mathbf k}]$ (Prop. 4.3 — restricting to $Z_{\mathbf k}$ costs essentially nothing in expectation, again because tameness makes the "bad" events rare), a bound on $\mathbb E[Z_{\mathbf k}^2]/\mathbb E[Z_{\mathbf k}]^2$ of the shape $\exp(k_a^2/\mu_a + o(\cdot))$ directly gives $\Pr(X_{\mathbf k}>0)\gtrsim\exp(-k_a^2/\mu_a - o(\cdot))$ via $\Pr(Z>0)\ge \mathbb E[Z]^2/\mathbb E[Z^2]$.

How to use this to prove something (recipe, generalisable beyond colourings)

1. Identify the target combinatorial structure and parametrise its possible "shapes" (here: colouring profiles $\mathbf k$, i.e. size-distribution of parts). 2. Compute (or bound) the first moment $\mathbb E[X_{\mathbf k}]$ for each shape (Lemma 2.2's exact formula $\mathbb E_p[X_{\mathbf k}]=P_{\mathbf k}q^{f_{\mathbf k}}$ is the colouring-specific instance) and find/approximate the shape $\mathbf k^*$ maximising it (§7, "optimal profiles" — a constrained-optimisation / large-deviations computation). 3. Check whether $\mathbf k^*$ (or a nearby integer profile, Lemma 7.17–7.19) satisfies a tameness-type tail condition: does the shape's "mass" decay fast enough away from its dominant scale that pairwise-overlap sums in the second moment stay summable? If yes, this is usually inherited "for free" from the shape of the maximiser (Lemma 7.20 shows the optimal $(\alpha-1)/(\alpha-2)$-bounded colouring profile satisfies $\kappa_u\approx b^{-(a-u)^2/2}$, comfortably tame). 4. Restrict the count to a "well-separated" sub-variable analogous to $Z_{\mathbf k}$ if the raw second moment is intractable — define dissimilarity events that force any two same-shape instances to either coincide on a piece or be nearly independent elsewhere. 5. Bound the second moment of the restricted variable by summing over discretised "overlap types" between instances, using the tail condition to truncate/bound this sum; apply Paley–Zygmund.

Recombination hooks. This is a template for *any* "first moment is large, does the structure actually exist whp?" question where instances of the target shape can overlap combinatorially: hypergraph colourings/covers, perfect matchings/factors with prescribed part-size profiles, partial Steiner systems, etc. The tameness idea — a checkable super-geometric tail condition on how far the profile's mass sits from its dominant scale — is a reusable sufficient condition for "the second-moment sum over overlap patterns is dominated by the top scale and hence summable," playing an analogous domesticating role to the spread-family condition in sunflower/threshold arguments (see R-spread set families (ALWZ/Rao's central reduction device)) or to smoothness conditions in the entropy method (see Entropy method — Shannon-entropy / coding-theoretic proof technique (Rao, Tao)): all three are "sufficient regularity conditions that convert an intractable worst-case correlation sum into a tractable, dominant-term-only sum."

Related

- Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — the Paley–Zygmund/second-moment framework this whole technique instantiates; tameness is the domesticating condition that makes it computable for colouring counts specifically. - R-spread set families (ALWZ/Rao's central reduction device) — an analogous "sufficient regularity/tail condition" device (Talagrand/ALWZ/Rao) that converts a hard extremal-family problem into a tractable pseudorandom case; same high-level role (dichotomy + regularity condition) as tameness's dissimilarity-restriction + tail-decay pairing. - Entropy method — Shannon-entropy / coding-theoretic proof technique (Rao, Tao) — a different domesticating toolkit (chain rule/subadditivity) for counting problems; worth comparing proof architectures since both convert "hard correlation structure" into "sum of simple local terms." - Erdős #625 — does χ(G)−ζ(G)→∞ for random G(n,1/2)? — Erdős's $\{100,\$1000\}$ problem on $\chi(G_{n,1/2})-\zeta(G_{n,1/2})\to\infty$, part of the same open cluster of questions (concentration/structure of $\chi(G_{n,p})$) that Heckel's non-concentration work (arXiv:1906.11808, arXiv:2103.14014) and this tame-colourings paper both address; not solved by this technique, but the same author/toolset is active on both.