betaFeedback

WorksMathematics

Impropriety and resilience of the chromatic number

Abstract

We show that, for pp bounded away from 11 and np→∞np\to\infty, the chromatic number of the binomial random graph Gn,pG_{n,p} is resilient to removal of a subgraph HH with o(nlog⁡(np))o(n \log(np)) edges. It follows that the same assertion holds with HH being a subgraph of maximum degree o(log⁡(np))o(\log(np)); and both these results are best possible up to a constant factor. We also prove corresponding results for the random rr-regular graph Gn,rG_{n,r}, when r→∞r\to\infty and r/nr/n is bounded away from 11, where HH has o(nlog⁡r)o(n\log r) edges or maximum degree o(log⁡r)o(\log r). Our results rely on a natural connection between chromatic resilience to edge removal and improper graph colouring. This work provides counterpoint to the work of Sudakov and Vu (2008) and Alon and Sudakov (2010), which treated chromatic resilience for Gn,pG_{n,p} subject to the addition, rather than removal, of edges.

Introduction

Let Gn,pG_{n,p} denote the binomial random graph with vertex set [n]={1,…,n}[n] = \{1, \ldots, n\} in which the edges are included independently at random with probability p=p(n)∈(0,1)p = p(n) \in(0,1) and let b=1/(1−p)b = 1/(1-p). The chromatic number χ(Gn,p)\chi(G_{n,p}) of Gn,pG_{n,p} is a central notion in random graph theory. The problem of determining this parameter was posed in 1960 by Erdős and Rényi [13]. Their original question (with npnp a constant) remains open, but there are very strong estimates — see [8, 9] for progress. In the case where np→∞np \to\infty and pp is bounded away from 1, it is a classic result due to Bollobás [5], Matula and Kučera [28] and Łuczak [27] that

χ(Gn,p)=(1+o(1))n2log⁡b(np)\chi(G_{n,p}) = (1 + o(1)) \frac{n}{2\log_b(np)}

asymptotically almost surely (a.a.s.), that is, with probability approaching 1 as n→∞n \to\infty. Recall that if p=o(1)p = o(1), then log⁡b=(1+o(1))p\log b = (1 + o(1))p, so the right-hand side may be written as (1+o(1))np/(2log⁡(np))(1 + o(1))np/(2\log(np)). Throughout, log⁡\log denotes the natural logarithm. For further background into the colouring of random graphs, consult [6, 19, 22].

Alon and Sudakov [2], improving upon a result of Sudakov and Vu [30], showed that for dense enough Gn,pG_{n,p}, specifically n−1/3+η≤p≤1/2n^{-1/3+\eta} \leq p \leq1/2 for any fixed η>0\eta> 0, the following result holds: a.a.s. χ(Gn,p)\chi(G_{n,p}) is resilient to the addition of any subset HH of o(n2/(log⁡b(np))2)=o((np)2/(log⁡n)2)o(n^2/(\log_b(np))^2) = o((np)^2/(\log n)^2) edges on [n][n]; that is, for any ε>0\varepsilon> 0, there exists δ>0\delta> 0 such that no matter how an adversary chooses a graph HH on [n][n] with at most δn2/(log⁡b(np))2\delta n^2/(\log_b(np))^2 edges,

χ(Gn,p∪H)≤(1+ε)χ(Gn,p) a.a.s.\chi(G_{n,p} \cup H) \leq(1+\varepsilon)\chi(G_{n,p}) \text{ a.a.s.}

This is best possible up to a constant factor, as can be seen by considering HH to be the edges of a clique on (1+ε)n/(2log⁡b(np))(1+\varepsilon)n/(2\log_b(np)) vertices. Under the same conditions for pp, they also proved a local version, for which HH has maximum degree o(n/(log⁡b(np)log⁡log⁡n))=o(np/(log⁡nlog⁡log⁡n))o(n/(\log_b(np)\log\log n)) = o(np/(\log n\log\log n)); this is best possible up to a log⁡log⁡n\log\log n factor.

Sudakov and Vu began this line of study within a broader study of resilience of graph properties to removal or addition of edges. Besides chromatic number, they analysed the resilience in Gn,pG_{n,p} of perfect matchings, Hamiltonian cycles and asymmetry, extending work in [23, 24], see also [29] for a review of developments. In the present work, we are concerned with resilience of the chromatic number to edge removal rather than addition. We settle this using a natural relation to improper graph colourings, and show the following.

Theorem 1. Let p=p(n)p = p(n) be bounded away from 1 and np→∞np \to\infty. The following hold a.a.s.

(i) χ(Gn,p)\chi(G_{n,p}) is (globally) resilient to removal of any subgraph with o(nlog⁡(np))o(n\log(np)) edges.

(ii) χ(Gn,p)\chi(G_{n,p}) is (locally) resilient to removal of any subgraph of maximum degree o(log⁡(np))o(\log(np)).

The local assertion is best possible up to a constant factor. The global assertion is best possible.

Theorem 1 can be reformulated as follows. For any ε>0\varepsilon> 0, there exists δ>0\delta> 0 such that no matter how an adversary chooses H⊆Gn,pH \subseteq G_{n,p} with at most δnlog⁡(np)\delta n\log(np) edges,

χ(Gn,p−H)≥(1−ε)χ(Gn,p) a.a.s.\chi(G_{n,p} - H) \geq(1-\varepsilon)\chi(G_{n,p}) \text{ a.a.s.}

this is the global resilience result, which implies the local one. On the other hand, for some ε,δ>0\varepsilon,\delta> 0, there exists H′⊆Gn,pH' \subseteq G_{n,p} of maximum degree at most δlog⁡(np)\delta\log(np) such that

χ(Gn,p−H′)<(1−ε)χ(Gn,p) a.a.s.;\chi(G_{n,p} - H') < (1-\varepsilon)\chi(G_{n,p}) \text{ a.a.s.};

and, for any ε>0\varepsilon> 0, there exist δ>0\delta> 0 and H′′⊆Gn,pH'' \subseteq G_{n,p} with at most εnlog⁡(np)\varepsilon n\log(np) edges such that

χ(Gn,p−H′′)<(1−δ)χ(Gn,p) a.a.s.\chi(G_{n,p} - H'') < (1-\delta)\chi(G_{n,p}) \text{ a.a.s.}

The main message to take from Theorem 1 is that decreasing χ(Gn,p)\chi(G_{n,p}) is a global task, of removing edges throughout Gn,pG_{n,p}. In contrast, the results of Alon and Sudakov say that increasing χ(Gn,p)\chi(G_{n,p}) is essentially a local task, of adding a clique, if pp does not decay too rapidly. If the chromatic resilience results for edge addition were extended to the entire range of p=p(n)p = p(n) with p→0p \to0 and np→∞np \to\infty, then, at least when np≫(log⁡(np))2log⁡log⁡nnp \gg(\log(np))^2\log\log n, they, together with Theorem 1, would imply that, locally, the chromatic number is more resilient to increase than to decrease; whereas, globally, the chromatic number is much more resilient to decrease than to increase if Gn,pG_{n,p} is very sparse and the other way around if Gn,pG_{n,p} is very dense (with the switch at around np=nnp=\sqrt{n}, up to logarithmic factors).

We also consider random regular graphs. Their study helped to initiate the broader theory of resilience [24]. Let Gn,rG_{n,r} denote the random rr-regular graph, chosen uniformly from the set Gn,r\mathcal{G}_{n,r} of all rr-regular graphs with vertex set [n][n] (assuming rnrn is even). The Kim–Vu sandwich conjecture [24] gives a useful connection between the binomial and random regular models. It asserts that, when r=ω(log⁡n)r=\omega(\log n), one may couple Gn,rG_{n,r} with two binomial random graphs Gn,p−G_{n,p_-} and Gn,p+G_{n,p_+} such that

Gn,p−⊆Gn,r⊆Gn,p+G_{n,p_-} \subseteq G_{n,r} \subseteq G_{n,p_+}

a.a.s., where p−=(1+o(1))r/np_-=(1+o(1))r/n and p+=(1+o(1))r/np_+=(1+o(1))r/n. Gao, Isaev and McKay [17] recently proved it whenever min⁡{r,n−r}≫(log⁡n)4\min\{r,n-r\}\gg(\log n)^4. Two contemporaneous works then treated the remaining regimes. Gao, Isaev and Perez-Gimenez [18] obtained related couplings that settled the remaining very dense regime and gave a weaker form of the conjecture in the remaining sparse regime, while Behague, Il’kovič and Montgomery [4] proved the conjecture in full. We use these sandwich results to prove the following.

Theorem 2. Let r=r(n)r=r(n) satisfy r→∞r\to\infty and r≤cnr\le cn for some fixed c<1c<1. The following hold a.a.s.

(i) χ(Gn,r)\chi(G_{n,r}) is (globally) resilient to removal of any subgraph with o(nlog⁡r)o(n\log r) edges.

(ii) χ(Gn,r)\chi(G_{n,r}) is (locally) resilient to removal of any subgraph of maximum degree o(log⁡r)o(\log r).

The local assertion is best possible up to a constant factor. The global assertion is best possible in the sense described after Theorem 1.

The structure of the paper is as follows. We show links between chromatic resilience and several improper colouring parameters. We use these to prove Theorem 1 in § 3 and Theorem 2 in § 4. For the regular result, we combine a direct pairing argument with the sandwich result mentioned above. We also give sharper fixed-density forms (Theorem 11 and Corollary 12) in § 5.

Impropriety and resilience

As mentioned above, we can relate the chromatic number’s (removal) resilience qualities with improper colouring parameters, one of which was already studied in the 1960s [25]. The (local) tt-improper chromatic number χt(G)\chi^{t}(G) of a graph GG is the smallest number of colours needed in a (local) tt-improper colouring — a colouring of the vertices of GG so that each subgraph induced by some colour class has maximum degree at most tt. See [31] for a survey of this type of colouring parameter, especially with respect to sparse graph classes. The global tt-improper chromatic number χ^t(G)\hat{\chi}^{t}(G) of a graph GG on nn vertices is the smallest number of colours needed in a global tt-improper colouring — a colouring of the vertices of GG so that the total number of edges in the subgraphs induced by colour classes is at most nt/2nt/2. Equivalently, the spanning subgraph of monochromatic edges has average degree at most tt. We write deg⁡‾(G)\overline{\deg}(G) for the average degree of GG. The global tt-improper chromatic number appears to have received little attention in graph theory. It was suggested at the end of a paper from 1997 [11]. An equivalent formulation in terms of chromatic edge-deletion blockers has been recently considered from a computational perspective [26].

Here and below the parameter tt is a non-negative integer for local impropriety, while it may be any non-negative real number for global impropriety.

Let us make a few remarks on the basic behaviour of these parameters. Both of them are non-increasing in tt and include the chromatic number as a special case by taking t=0t=0. Clearly χ^t(G)≤χ⌊t⌋(G)\hat{\chi}^{t}(G) \leq\chi^{\lfloor t\rfloor}(G) for every real t≥0t \geq0. Furthermore, it follows from a result of Lovász [25] that χt(G)≤⌈(Δ(G)+1)/(t+1)⌉\chi^{t}(G) \leq\left\lceil(\Delta(G)+1)/(t+1)\right\rceil for every non-negative integer tt, where Δ(G)\Delta(G) denotes the maximum degree of GG. Summarising, we have that for any graph GG and non-negative real tt

χ^t(G)≤χ⌊t⌋(G)≤min⁡{⌈Δ(G)+1⌊t⌋+1⌉,χ(G)}.(1)\hat{\chi}^{t}(G) \leq\chi^{\lfloor t\rfloor}(G) \leq\min\left\{\left\lceil\frac{\Delta(G)+1}{\lfloor t\rfloor+1}\right\rceil,\chi(G)\right\}. \tag*{(1)}

We now present two elementary correspondences between local/global resilience of the chromatic number and local/global improper colouring.

Proposition 3. Let GG be a graph, tt a non-negative integer, and kk a positive integer. The following statements are equivalent:

(i) χt(G)≤k\chi^{t}(G) \leq k.

(ii) There exists a subgraph HH of GG with Δ(H)≤t\Delta(H) \leq t such that χ(G−H)≤k\chi(G-H) \leq k.

Proposition 4. Let GG be a graph on nn vertices, tt a non-negative real number, and kk a positive integer. The following statements are equivalent:

(i) χ^t(G)≤k\hat{\chi}^{t}(G) \leq k.

(ii) There exists a subgraph HH of GG with at most nt/2nt/2 edges such that χ(G−H)≤k\chi(G-H) \leq k.

Both correspondences follow by deleting the monochromatic edges of an improper colouring and, conversely, using a proper colouring of G−HG-H.

Note that the correspondences of Propositions 3 and 4 apply to all graphs and allow us to deduce chromatic resilience results from prior work on improper chromatic numbers.

Given the above correspondences, it can be helpful to relate chromatic resilience to two other parameters that are also closely related to improper colouring, particularly for random graphs, cf. [7, 21, 14, 15]. The (local) tt-stability number αt(G)\alpha^{t}(G) of a graph GG is the number of vertices in a largest (local) tt-stable set, a subset of the vertices whose induced subgraph has maximum degree at most tt. The global tt-stability number α^t(G)\hat{\alpha}^{t}(G) of a graph GG is the number of vertices in a largest global tt-stable set, a subset of the vertices whose induced subgraph has average degree at most tt. (We called global tt-stability tt-sparsity in [15].)

Both of these parameters are non-decreasing in tt and include the stability number as a special case by taking t=0t=0. For every non-negative real tt, we have α⌊t⌋(G)≤α^t(G)\alpha^{\lfloor t\rfloor}(G) \leq\hat{\alpha}^{t}(G) and moreover

χ(G)≥χ⌊t⌋(G)≥∣V(G)∣α⌊t⌋(G)≥∣V(G)∣α^t(G).(2)\chi(G) \geq\chi^{\lfloor t\rfloor}(G) \geq\frac{|V(G)|}{\alpha^{\lfloor t\rfloor}(G)} \geq\frac{|V(G)|}{\hat{\alpha}^{t}(G)}. \tag*{(2)}

Thus we may bound χ[t](G)\chi^{[t]}(G) from below by bounding α^t(G)\hat{\alpha}^{t}(G) or α[t](G)\alpha^{[t]}(G) from above.

As we next show, we can also bound χ^t(G)\hat{\chi}^{t}(G) from below by bounding the global stability of GG from above, although the connection holds in a weaker sense than above in that we need to bound α^t′(G)\hat{\alpha}^{t'}(G) for some t′>tt' > t. (Note that in this case α^t′(G)≥α^t(G)\hat{\alpha}^{t'}(G) \ge\hat{\alpha}^{t}(G) always.)

Proposition 5. Let GG be a graph on [n][n] and ε>0\varepsilon> 0. Suppose that there exist t≥0t \ge0 and α>0\alpha> 0 such that α^2t/ε(G)<(1+ε/2)α\hat{\alpha}^{2t/\varepsilon}(G) < (1+\varepsilon/2)\alpha. Then χ^t(G)>⌊(1−ε)n/α⌋\hat{\chi}^{t}(G) > \lfloor(1-\varepsilon)n/\alpha\rfloor.

Proof. Let k=⌊(1−ε)n/α⌋k = \lfloor(1-\varepsilon)n/\alpha\rfloor. If k≤0k \le0, the result is immediate. Otherwise, suppose for a contradiction that χ^t(G)≤k\hat{\chi}^{t}(G) \le k. Consider any global tt-improper colouring PP of the graph using kk colours and let A⊆[n]A \subseteq[n] be the union of those colour classes of PP having fewer than (1+ε/2)α(1+\varepsilon/2)\alpha vertices. We then have

∣A∣≤k(1+ε/2)α≤(1−ε)(1+ε/2)n<(1−ε/2)n.|A| \le k(1+\varepsilon/2)\alpha\le(1-\varepsilon)(1+\varepsilon/2)n < (1-\varepsilon/2)n.

It follows that the number of vertices in colour classes of PP having at least (1+ε/2)α(1+\varepsilon/2)\alpha vertices is more than εn/2\varepsilon n/2. Since α^2t/ε(G)<(1+ε/2)α\hat{\alpha}^{2t/\varepsilon}(G) < (1+\varepsilon/2)\alpha, each such colour class of PP induces a subgraph of average degree greater than 2t/ε2t/\varepsilon. Summing over all these vertices, we see that the number of monochromatic edges under PP is more than (εn/2)(2t/ε)/2=nt/2(\varepsilon n/2)(2t/\varepsilon)/2 = nt/2, contradicting that PP is a global tt-improper colouring.

Proof of Theorem 1

We now apply Propositions 3 and 4 to the setting of random graphs. Given these correspondences, it suffices for the proof of our first main result to establish appropriate bounds on the local and global tt-improper chromatic numbers.

Lemma 6. Suppose p=p(n)p = p(n) is bounded away from 1 and ε>0\varepsilon> 0. There exist constants d0d_0 and τ>0\tau> 0 such that, if np≥d0np \ge d_0 and 0≤t≤τlog⁡(np)0 \le t \le\tau\log(np), then χ^t(Gn,p)≥n/(2(1+ε)log⁡b(np))\hat{\chi}^{t}(G_{n,p}) \ge n/(2(1+\varepsilon)\log_b(np)) a.a.s.

Lemma 7. Suppose p=p(n)p = p(n) is bounded away from 1, np→∞np \to\infty and ε>0\varepsilon> 0. If t=t(n)t = t(n) is a positive integer, then χt(Gn,p)≤(1+ε)np/t+np/(log⁡(np))2\chi^{t}(G_{n,p}) \le(1+\varepsilon)np/t + np/(\log(np))^2 a.a.s.

With these lemmas in hand, let us see how to prove the main theorem.

Proof of Theorem 1. We first prove global resilience — from this, the local assertion follows since χ^t(Gn,p)≤χt(Gn,p)\hat{\chi}^{t}(G_{n,p}) \le\chi^{t}(G_{n,p}). Let t=t(n)=o(log⁡(np))t = t(n) = o(\log(np)). Proposition 4 and Lemma 6 give, a.a.s. and simultaneously for every subgraph HH with at most nt/2nt/2 edges,

χ(Gn,p−H)≥(1+o(1))n2log⁡b(np).\chi(G_{n,p}-H) \ge(1+o(1))\frac{n}{2\log_b(np)}.

Together with the usual upper bound on χ(Gn,p)\chi(G_{n,p}), this proves the first two assertions.

We next prove that the local assertion is best possible up to a constant factor. Take

t=⌈4plog⁡b(np)⌉.t = \lceil4p\log_b(np)\rceil.

Uniformly for pp bounded away from 1, we have t=Θ(log⁡(np))t = \Theta(\log(np)). Moreover,

np(log⁡(np))2=o(nlog⁡b(np)).\frac{np}{(\log(np))^2} = o\left(\frac{n}{\log_b(np)}\right).

Lemma 7, with ε=1/4\varepsilon= 1/4, therefore gives

χt(Gn,p)<n3log⁡b(np)\chi^t(G_{n,p}) < \frac{n}{3\log_b(np)}

for all sufficiently large npnp. The required subgraph now follows from Proposition 3.

It remains to prove that the global assertion is best possible. Fix 0<ε<1/20 < \varepsilon< 1/2 and set δ=ε/3\delta= \varepsilon/3. We use the standard a.a.s. estimates

χ(Gn,p)=(1+o(1))n2log⁡b(np),α(Gn,p)=(1+o(1))2log⁡b(np)\chi(G_{n,p}) = (1 + o(1))\frac{n}{2\log_b(np)}, \qquad\alpha(G_{n,p}) = (1 + o(1))2\log_b(np)

simultaneously; see, for example, [6, 19]. We shall also use the following density property.

If ξ=(np)−1/4\xi= (np)^{-1/4}, then a Chernoff bound followed by a union bound over the at most 2n2^n sets shows that, for any fixed 0<a1<a2≤10 < a_1 < a_2 \le1, a.a.s. simultaneously for every S⊆[n]S \subseteq[n] with a1n≤∣S∣≤a2na_1n \le|S| \le a_2n,

e(S,[n]∖S)+e(S)=(1+O(ξ))p(∣S∣(n−∣S∣)+(∣S∣2)).e(S,[n]\setminus S) + e(S) = (1 + O(\xi))p\left(|S|(n-|S|) + \binom{|S|}{2}\right).

Indeed, the exponent in the Chernoff bound has order ξ2n2p=nnp\xi^2n^2p = n\sqrt{np}.

Fix an optimal proper colouring with q=χ(Gn,p)q = \chi(G_{n,p}) colours, take s=⌊δq⌋s = \lfloor\delta q\rfloor, and let UU be the union of the ss largest colour classes. Writing the sizes of the colour classes in non-increasing order as c1,…,cqc_1,\ldots,c_q, we have

∣U∣=∑i=1sci≥sq∑i=1qci=snq=(δ+o(1))n.|U| = \sum_{i=1}^{s} c_i \ge\frac{s}{q}\sum_{i=1}^{q}c_i = \frac{sn}{q} = (\delta+ o(1))n.

On the other hand, each colour class has size at most α(Gn,p)\alpha(G_{n,p}), and hence

∣U∣≤sα(Gn,p)=(δ+o(1))n.|U| \le s\alpha(G_{n,p}) = (\delta+ o(1))n.

Consequently, ∣U∣=(δ+o(1))n|U| = (\delta+ o(1))n. Retain the other q−sq-s colour classes and order the vertices of UU. Recolour them in this order, each time choosing a retained colour that minimises the number of neighbours already given that colour. Every resulting monochromatic edge within UU is then counted when its later endpoint is recoloured. The total number of monochromatic edges is consequently at most

e(U,[n]∖U)+e(U)q−s=(1+o(1))2δ−δ21−δnplog⁡b(np)≤εnlog⁡(np),\begin{aligned} \frac{e(U,[n]\setminus U) + e(U)}{q-s} = (1 + o(1))\frac{2\delta-\delta^2}{1-\delta}np\log_b(np) \\ &\le\varepsilon n\log(np), \end{aligned}

where we used p/log⁡b≤1p/\log b \le1. Removing these monochromatic edges leaves a graph coloured with (1−δ+o(1))χ(Gn,p)(1-\delta+o(1))\chi(G_{n,p}) colours, which is smaller than (1−δ/2)χ(Gn,p)(1-\delta/2)\chi(G_{n,p}) for all sufficiently large nn. This proves the assertion.

Before giving the proofs of Lemmas 6 and 7, we introduce some notation and a lemma from the theory of large deviations. For further background, consult [12]. Given p∈(0,1)p \in(0,1), let

Λ∗(x)={xlog⁡xp+(1−x)log⁡1−x1−pfor x∈[0,1],∞otherwise(3)\Lambda^*(x) = \begin{cases} x \log\dfrac{x}{p} + (1-x) \log\dfrac{1-x}{1-p} & \text{for } x \in[0,1], \\ \infty& \text{otherwise} \end{cases} \tag*{(3)}

(where Λ∗(0)=log⁡b\Lambda^*(0)=\log b and Λ∗(1)=−log⁡p\Lambda^*(1)=-\log p). This is the Fenchel-Legendre transform of the logarithmic moment generating function associated with the Bernoulli distribution with probability pp (cf. [12 Exercise 2.2.23(b)]). It is easy to see that Λ∗(x)\Lambda^*(x) has a global minimum of 00 at x=px=p, is strictly decreasing on [0,p)[0,p) and strictly increasing on (p,1](p,1]. Let Bin⁡(⋅,⋅)\operatorname{Bin}(\cdot,\cdot) denote the binomial distribution. We use the following estimate from [21 Lemma 4].

Lemma 8. There is a constant δ>0\delta> 0 such that the following holds. Let p∈(0,1)p \in(0,1), let NN be a positive integer, and let X∈Bin⁡(N,p)X \in\operatorname{Bin}(N,p). Then, for each integer 1≤r≤N−11 \le r \le N-1 such that r≤Npr \le Np,

δ⋅max⁡{r−1/2,(N−r)−1/2}⋅exp⁡(−NΛ∗(r/N))≤P(X≤r)≤exp⁡(−NΛ∗(r/N)).\delta\cdot\max\left\{r^{-1/2},(N-r)^{-1/2}\right\}\cdot\exp\left(-N\Lambda^*(r/N)\right) \le\mathbb{P}(X \le r) \le\exp\left(-N\Lambda^*(r/N)\right).

Lemma 9. For every c0,ζ>0c_0,\zeta> 0, there is some a0>0a_0 > 0 such that, for 0<p≤1−c00 < p \le1-c_0 and 0≤a≤a00 \le a \le a_0,

Λ∗(ap)≥(1−ζ)log⁡b.\Lambda^*(ap) \ge(1-\zeta)\log b.

Proof. We first consider pp close to zero. Uniformly for aa in any fixed interval [0,A][0,A], with alog⁡aa\log a interpreted as zero when a=0a=0, we have

Λ∗(ap)=aplog⁡a+(1−ap)log⁡1−ap1−p\Lambda^*(ap)=ap\log a+(1-ap)\log\frac{1-ap}{1-p}
=p(1−a+alog⁡a)+O(p2).=p(1-a+a\log a)+O(p^2).

Since log⁡b=p+O(p2)\log b=p+O(p^2) and 1−a+alog⁡a→11-a+a\log a\to1 as a→0a\to0, the required inequality follows for all sufficiently small pp and aa.

For pp in a compact interval bounded away from zero, the assertion follows from uniform continuity at a=0a=0, since Λ∗(0)=log⁡b\Lambda^*(0)=\log b. Combining the two ranges gives a choice of a0a_0 that is uniform over 0<p≤1−c00<p\le1-c_0. □\square

Before continuing, we remark that an alternative way to establish Lemma 6 is to apply Lemma 8 to obtain an upper bound on the global tt-stability number of Gn,pG_{n,p} and then apply Proposition 5; however, this gives a smaller admissible value of τ\tau. The method we demonstrate here is sharp (with respect to τ\tau) for fixed pp, as we show in § 5.

Proof of Lemma 6. Choose ζ>0\zeta> 0 so that (1+ε)(1−ζ)>1(1+\varepsilon)(1-\zeta)>1. Let k=2(1+ε)log⁡b(np)k=2(1+\varepsilon)\log_b(np) and j=⌊n/k⌋j=\lfloor n/k\rfloor. Consider any colouring of [n][n] using at most jj colours, and let MM be the number of pairs of vertices contained in its colour classes. By convexity,

M≥12(n2j−n)≥n(k−1)2.(4)M \ge\frac{1}{2}\left(\frac{n^2}{j}-n\right)\ge\frac{n(k-1)}{2}. \tag*{(4)}

Let N0=⌊n(k−1)/2⌋N_0=\lfloor n(k-1)/2\rfloor and T=⌊nt/2⌋T=\lfloor nt/2\rfloor. For t≤τlog⁡(np)t\leq\tau\log(np), we have

TpN0≤(1+o(1))τ2(1+ε)log⁡bp.\frac{T}{pN_0}\leq(1+o(1))\frac{\tau}{2(1+\varepsilon)}\frac{\log b}{p}.

Since log⁡b/p\log b/p is bounded uniformly for pp bounded away from 1, we may choose τ\tau so that, for all sufficiently large nn, we have T≤pN0<N0T\leq pN_0<N_0 and Lemma 9 yields

Λ∗(TN0)≥(1−ζ)log⁡b.\Lambda^*\left(\frac{T}{N_0}\right)\geq(1-\zeta)\log b.

The number of monochromatic edges in the colouring stochastically dominates Bin⁡(N0,p)\operatorname{Bin}(N_0,p). For T≥1T\geq1, Lemma 8 therefore gives

P(the colouring is globally t-improper)≤exp⁡(−N0Λ∗(TN0)).\mathbb{P}\left(\text{the colouring is globally }t\text{-improper}\right)\leq\exp\left(-N_0\Lambda^*\left(\frac{T}{N_0}\right)\right).

If T=0T=0, the colouring is globally tt-improper only if none of its MM candidate monochromatic pairs forms an edge. Since M≥N0M\geq N_0, the probability of this event is at most

(1−p)N0=exp⁡(−N0Λ∗(0)),(1-p)^{N_0}=\exp(-N_0\Lambda^*(0)),

so the same estimate remains valid.

Moreover,

j≤nlog⁡b2(1+ε)log⁡(np),j\leq\frac{n\log b}{2(1+\varepsilon)\log(np)},

and hence log⁡j≤log⁡(np)−log⁡log⁡(np)+O(1)\log j\leq\log(np)-\log\log(np)+O(1). A union bound over the at most jnj^n labelled colourings now gives a probability at most

exp⁡(−((1+ε)(1−ζ)−1+o(1))nlog⁡(np)−nlog⁡log⁡(np)+O(n))=o(1).\exp\left(-\bigl((1+\varepsilon)(1-\zeta)-1+o(1)\bigr)n\log(np)-n\log\log(np)+O(n)\right)=o(1).

Thus a.a.s. there is no global tt-improper colouring using at most jj colours, as required. □\square

Proof of Lemma 7. Let η=min⁡{ε,1}/100\eta=\min\{\varepsilon,1\}/100. Choose CC sufficiently large. If np≥Clog⁡nnp\geq C\log n, a Chernoff bound and a union bound over the vertices give Δ(Gn,p)≤(1+η)np\Delta(G_{n,p})\leq(1+\eta)np a.a.s. The result then follows directly from (1) for all sufficiently large nn.

It remains to consider np<Clog⁡nnp<C\log n. Let

W={v:deg⁡(v)≥(1+4η)np},W=\{v:\deg(v)\geq(1+4\eta)np\},
k=⌈ηnp⌉,W′={v∈W:deg⁡Gn,p[W](v)≥k}.k=\lceil\eta np\rceil,\qquad W'=\{v\in W:\deg_{G_{n,p}[W]}(v)\geq k\}.

We shall show that the graph induced by W′W' has degeneracy less than

q=⌊np4(log⁡(np))2⌋.q=\left\lfloor\frac{np}{4(\log(np))^2}\right\rfloor.

We first bound the size of W′W'. If v∈W′v\in W', it has some set U⊆N(v)∩WU\subseteq N(v)\cap W of size kk. Condition on the edges from vv to UU, and for each u∈Uu\in U let

Xu=e({u},[n]∖({v}∪U)).X_u=e(\{u\},[n]\setminus(\{v\}\cup U)).

The edge indicators defining the variables XuX_u, u∈Uu \in U, are disjoint, and hence these variables are independent. Since u∈Wu \in W, we must have Xu≥(1+2η)npX_u \ge(1+2\eta)np for all sufficiently large npnp. It follows from a Chernoff bound, cf. [19 Theorem 2.1], that for some constants $c,c' > 0,

P(v∈W′)≤(n−1k)pkexp⁡(−cη2npk)≤exp⁡(−c′(np)2).\mathbb{P}(v \in W') \le\binom{n-1}{k}p^k\exp(-c\eta^2npk) \le\exp(-c'(np)^2).

Let w0=nexp⁡(−c′(np)2/2)w_0=n\exp(-c'(np)^2/2). If w0≥1w_0 \ge1, then Markov’s inequality gives ∣W′∣≤w0|W'| \le w_0 a.a.s.; if w0<1w_0 < 1, then P(W′≠∅)≤E∣W′∣=o(1)\mathbb{P}(W' \ne\varnothing) \le\mathbb{E}|W'|=o(1). Thus we may assume that ∣W′∣≤w0|W'| \le w_0.

We next rule out all dense subsets of this size simultaneously. For q+1≤s≤w0q+1 \le s \le w_0, let m=⌈qs/2⌉m=\lceil qs/2\rceil. Since log⁡(n/s)≥c′(np)2/2\log(n/s) \ge c'(np)^2/2, a union bound gives

P(some S, ∣S∣=s, has e(S)≥m)≤(ns)((s2)m)pm≤(ens)s(espq)qs/2≤exp⁡(−qs3log⁡ns).\mathbb{P}(\text{some }S,\ |S|=s,\ \text{has }e(S)\ge m) \le\binom{n}{s}\binom{\binom{s}{2}}{m}p^m \le\left(\frac{en}{s}\right)^s\left(\frac{esp}{q}\right)^{qs/2} \le\exp\left(-\frac{qs}{3}\log\frac{n}{s}\right).

for all sufficiently large npnp. Summing this estimate over ss gives o(1)o(1). Every graph of minimum degree at least qq contains at least q+1q+1 vertices and at least qs/2qs/2 edges, so Gn,p[W′]G_{n,p}[W'] has degeneracy at most q−1q-1 a.a.s.

Finally, use disjoint sets of colours on [n]∖W[n]\setminus W, W∖W′W\setminus W' and W′W'. By (1) and the degeneracy bound,

χt(Gn,p)≤⌈(1+4η)np+1t+1⌉+⌈kt+1⌉+q≤(1+6η)npt+2+q≤(1+ε)npt+np(log⁡(np))2,\begin{aligned} \chi^t(G_{n,p}) \le\left\lceil\frac{(1+4\eta)np+1}{t+1}\right\rceil+\left\lceil\frac{k}{t+1}\right\rceil+q \\ &\le(1+6\eta)\frac{np}{t}+2+q\le(1+\varepsilon)\frac{np}{t}+\frac{np}{(\log(np))^2}, \end{aligned}

as required.

Proof of Theorem 2

The results of Frieze and Łuczak [16] and Cooper, Frieze, Reed and Riordan [10] give the ordinary chromatic and stability number estimates needed below when rr is at most a constant multiple of log⁡n\log n. Recently, Behague, Il’kovič and Montgomery [4] proved the Kim–Vu sandwich conjecture in full. Their quantitative result transfers the corresponding binomial estimates above that range. Thus, whenever r→∞r\to\infty and r≤cnr\le cn for some fixed c<1c<1, we may use

χ(Gn,r)=(1+o(1))n2log⁡br,α(Gn,r)=(1+o(1))2log⁡br(5)\chi(G_{n,r})=(1+o(1))\frac{n}{2\log_b r},\qquad\alpha(G_{n,r})=(1+o(1))2\log_b r \tag*{(5)}

a.a.s., where b=n/(n−r)b=n/(n-r).

Recall (2). For the lower range, we shall need the following upper bound on the global tt-stability number.

Lemma 10. Fix C,ε>0C,\varepsilon>0. Suppose r=r(n)r=r(n) is a positive integer, rnrn is even, r→∞r\to\infty and r≤Clog⁡nr\le C\log n. There is some τ>0\tau>0 such that, if 0≤t≤τlog⁡r0\le t\le\tau\log r, then

α^ t(Gn,r)<(1+ε)2log⁡br\widehat{\alpha}^{\,t}(G_{n,r})<(1+\varepsilon)2\log_b r

a.a.s., where b=n/(n−r)b=n/(n-r).

Let us first see how this lemma is used to prove Theorem 2.

Proof of Theorem 2. Fix ρ>0\rho> 0, and let t=t(n)=o(log⁡r)t = t(n) = o(\log r). Choose η>0\eta> 0 sufficiently small in terms of ρ\rho and the constant cc in the theorem. By [4 Theorem 1.1], there is some C=C(η)C = C(\eta) such that, whenever r≥Clog⁡nr \ge C \log n, there are probabilities p−≤p+p_{-} \le p_{+} and a coupling for which

Gn,p−⊆Gn,r⊆Gn,p+(6)G_{n,p_{-}} \subseteq G_{n,r} \subseteq G_{n,p_{+}} \tag*{(6)}

a.a.s., where

(1−η)rn≤p−≤p+≤(1+η)rn.(1-\eta)\frac{r}{n} \le p_{-} \le p_{+} \le(1+\eta)\frac{r}{n}.

We choose η\eta small enough that (1+η)c<1(1+\eta)c < 1.

Suppose first that r<Clog⁡nr < C \log n. Apply Lemma 10 with ε=ρ/6\varepsilon= \rho/6 and with the parameter tt in that lemma equal to 6t/ρ6t/\rho. Since t=o(log⁡r)t = o(\log r), this gives

χ^6t/ρ(Gn,r)<(1+ρ/6)2log⁡br\widehat{\chi}^{6t/\rho}(G_{n,r}) < (1+\rho/6)2\log_b r

a.a.s. Proposition 5, applied with ε=ρ/3\varepsilon= \rho/3 and α=2log⁡br\alpha= 2\log_b r, now yields

χ^t(Gn,r)≥⌈(1−ρ/3)n2log⁡br⌉.\widehat{\chi}^{t}(G_{n,r}) \ge\left\lceil\frac{(1-\rho/3)n}{2\log_b r}\right\rceil.

We next suppose that r≥Clog⁡nr \ge C \log n. The parameters χt\chi^t and χ^t\widehat{\chi}^t are non-decreasing under the addition of edges, so (5) and Lemma 6 give the required lower bound from Gn,p−G_{n,p_{-}}. For completeness, if b±=1/(1−p±)b_{\pm} = 1/(1-p_{\pm}), then uniformly for r≤cnr \le cn,

n2log⁡b±(np±)=(1+Oc(η)+o(1))n2log⁡br.\frac{n}{2\log_{b_{\pm}}(np_{\pm})} = \left(1+O_c(\eta)+o(1)\right)\frac{n}{2\log_b r}.

The ordinary upper bound follows in the same way from χ(Gn,r)≤χ(Gn,p+)\chi(G_{n,r}) \le\chi(G_{n,p_{+}}). Since ρ\rho was arbitrary, Propositions 3 and 4 prove both resilience assertions.

It remains to prove the two sharpness statements. By (1) and (4), with t=⌈8log⁡r⌉t = \lceil8\log r\rceil,

χt(Gn,r)χ(Gn,r)≤(1+o(1))r4nlog⁡b≤14+o(1).\frac{\chi^t(G_{n,r})}{\chi(G_{n,r})} \le(1+o(1))\frac{r}{4n\log b} \le\frac{1}{4}+o(1).

This proves the local assertion by Proposition 3.

For the global assertion, fix an optimal proper colouring with q=χ(Gn,r)q = \chi(G_{n,r}) colours, discard s=⌊δq⌋s = \lfloor\delta q\rfloor colour classes, and let UU be their union. Recolour the vertices of UU sequentially with the remaining q−sq-s colours, each time minimising the number of already coloured neighbours receiving the chosen colour. By regularity and (4), the number of resulting monochromatic edges is at most

r∣U∣q−s≤(1+o(1))δ1−δrα(Gn,r)=(1+o(1))2δ1−δr/n−log⁡(1−r/n)nlog⁡r≤(1+o(1))2δ1−δnlog⁡r.\begin{aligned} \frac{r|U|}{q-s} \le(1+o(1))\frac{\delta}{1-\delta}r\alpha(G_{n,r}) \\ &= (1+o(1))\frac{2\delta}{1-\delta}\frac{r/n}{-\log(1-r/n)}n\log r \\ &\le(1+o(1))\frac{2\delta}{1-\delta}n\log r. \end{aligned}

Given ε>0\varepsilon> 0, choose δ>0\delta> 0 so that 2δ/(1−δ)<ε2\delta/(1-\delta) < \varepsilon. Then, a.a.s., the number of monochromatic edges is at most εnlog⁡r\varepsilon n\log r. Removing these edges leaves a graph coloured with (1−δ+o(1))q(1-\delta+o(1))q colours, fewer than (1−δ/2)q(1-\delta/2)q for all sufficiently large nn, as required.

We next prove Lemma 10. Part of this result appears in a non-refereed proceedings contribution by Bollobás and Clark [7]. Since that work is not easily accessible, we include a full proof.

Proof of Lemma 10. Let k=⌈2(1+ε)log⁡br⌉k = \lceil2(1+\varepsilon)\log_b r\rceil. It is enough to show that a.a.s. there is no global tt-stable set of exactly kk vertices. Indeed, if a set TT of K≥kK \ge k vertices spans at most tK/2tK/2 edges, then a uniform random kk-subset SS of TT satisfies

Ee(S)=e(T)k(k−1)K(K−1)≤tk2.\mathbb{E}e(S)=e(T)\frac{k(k-1)}{K(K-1)}\le\frac{tk}{2}.

Thus some such SS is globally tt-stable.

We use the pairing model. A pairing is a perfect matching of N=rnN=rn points partitioned into nn cells of rr points each, and it induces the usual random regular multigraph. Fix kk cells, write M=rkM=rk, and let ZZ denote the number of pairs having both points in these cells. Writing Ps=P(Z=s)P_s=\mathbb{P}(Z=s), a direct count gives, for

max⁡{0,M−N/2}≤s≤⌊M/2⌋,\max\{0,M-N/2\}\le s\le\lfloor M/2\rfloor,
Ps=(M2s)(2s−1)!!(N−M)!(N−2M+2s)!(N−2M+2s−1)!!(N−1)!!.P_s=\binom{M}{2s}(2s-1)!!\frac{(N-M)!}{(N-2M+2s)!}\frac{(N-2M+2s-1)!!}{(N-1)!!}.

We have Ps=0P_s=0 outside this range. Here and below we use (−1)!!=1(-1)!!=1, corresponding to the unique pairing of the empty set. Cancelling consecutive terms, we obtain

Ps+1Ps=(M−2s)(M−2s−1)2(s+1)(N−2M+2s+2).(7)\frac{P_{s+1}}{P_s}=\frac{(M-2s)(M-2s-1)}{2(s+1)(N-2M+2s+2)}. \tag*{(7)}

Since log⁡b≥r/n\log b\ge r/n, we have

MN=kn≤2(1+ε)log⁡rr+1n=o(1).\frac{M}{N}=\frac{k}{n}\le\frac{2(1+\varepsilon)\log r}{r}+\frac{1}{n}=o(1).

In particular, M<N/2M<N/2 for all sufficiently large nn. Let

λ=M22(N−2M).\lambda=\frac{M^2}{2(N-2M)}.

Iterating (6) gives Ps≤P0λs/s!P_s\le P_0\lambda^s/s!. Exposing in turn the partners of the MM points also gives

P0=∏h=0M−1N−M−hN−2h−1=∏h=0M−1(1−M−h−1N−2h−1)≤exp⁡(−M(M−1)2N).\begin{aligned} P_0=\prod_{h=0}^{M-1}\frac{N-M-h}{N-2h-1} \\ &=\prod_{h=0}^{M-1}\left(1-\frac{M-h-1}{N-2h-1}\right)\le\exp\left(-\frac{M(M-1)}{2N}\right). \end{aligned}

Let q=⌊tk/2⌋q=\lfloor tk/2\rfloor. Since M<N/2M<N/2, the support of ZZ is {0,…,⌊M/2⌋}\{0,\ldots,\lfloor M/2\rfloor\}. Moreover,

qM/2≤tr=o(1),\frac{q}{M/2}\le\frac{t}{r}=o(1),

so qq lies in this support for all sufficiently large nn. Uniformly for r→∞r \to\infty and r≤Clog⁡nr \le C\log n,

k=(1+o(1))2(1+ε)nlog⁡rrk=(1+o(1))\frac{2(1+\varepsilon)n\log r}{r}

and hence

qλ≤t(N−2M)rM≤tnrk≤(1+o(1))t2(1+ε)log⁡r≤(1+o(1))τ2(1+ε).\frac{q}{\lambda}\le\frac{t(N-2M)}{rM}\le\frac{tn}{rk}\le(1+o(1))\frac{t}{2(1+\varepsilon)\log r}\le(1+o(1))\frac{\tau}{2(1+\varepsilon)}.

Thus we may choose τ\tau so that q≥1q\ge1 implies q≤λq\le\lambda. We use the bound on P0P_0 directly for q=0q=0; otherwise,

P(Z≤q)≤P0(q+1)λqq!≤P0(q+1)(eλq)q.\mathbb{P}(Z\le q)\le P_0(q+1)\frac{\lambda^q}{q!}\le P_0(q+1)\left(\frac{e\lambda}{q}\right)^q.

Let YY count the kk-sets of cells that contain at most qq internal pairs. For a simple pairing, the cells are the vertices of the resulting graph, and the internal pairs are exactly the edges induced by the corresponding vertex set. Consequently, YY counts precisely the global tt-stable kk-sets. Let A=n(log⁡r)2/rA=n(\log r)^2/r. Uniformly for r→∞r\to\infty and r≤Clog⁡nr\le C\log n, we have

log⁡b=(1+o(1))rn,\log b=(1+o(1))\frac{r}{n},
log⁡(nk)≤2(1+ε)nlog⁡rr(log⁡r−log⁡log⁡r+O(1)),\log\binom{n}{k}\le\frac{2(1+\varepsilon)n\log r}{r}(\log r-\log\log r+O(1)),
M(M−1)2N=(2(1+ε)2+o(1))n(log⁡r)2r.\frac{M(M-1)}{2N}=(2(1+\varepsilon)^2+o(1))\frac{n(\log r)^2}{r}.

Suppose first that q≥1q\ge1. Then q=⌊tk/2⌋≥tk/4q=\lfloor tk/2\rfloor\ge tk/4, and hence

q≤(1+ε+o(1))tnlog⁡rr,q\le(1+\varepsilon+o(1))\frac{tn\log r}{r},
λq≤2M2(N−2M)tk≤Cεlog⁡rt.\frac{\lambda}{q}\le\frac{2M^2}{(N-2M)tk}\le C_\varepsilon\frac{\log r}{t}.

Using log⁡(q+1)≤q\log(q+1)\le q and enlarging CεC_\varepsilon if necessary, we obtain

log⁡(q+1)+qlog⁡(eλ/q)≤qlog⁡(e2λ/q)≤(1+ε+o(1))tlog⁡rlog⁡Cεlog⁡rtA.\begin{aligned} \log(q+1)+q\log(e\lambda/q)\le q\log(e^2\lambda/q) \\ &\le(1+\varepsilon+o(1))\frac{t}{\log r}\log\frac{C_\varepsilon\log r}{t}A. \end{aligned}

Together with EY≤(nk)P(Z≤q)\mathbb{E}Y\le\binom{n}{k}\mathbb{P}(Z\le q), the estimates above give

log⁡EY≤(−2ε(1+ε)+(1+ε+o(1))tlog⁡rlog⁡Cεlog⁡rt+o(1))A.\log\mathbb{E}Y\le\left(-2\varepsilon(1+\varepsilon)+(1+\varepsilon+o(1))\frac{t}{\log r}\log\frac{C_\varepsilon\log r}{t}+o(1)\right)A.

For q=0q=0, the direct bound P(Z≤q)=P0\mathbb{P}(Z\le q)=P_0 instead gives

log⁡EY≤(−2ε(1+ε)+o(1))A.\log\mathbb{E}Y\le\left(-2\varepsilon(1+\varepsilon)+o(1)\right)A.

For 0<t≤τlog⁡r0 < t \le\tau\log r, the term (t/log⁡r)log⁡(Cεlog⁡r/t)(t/\log r)\log(C_{\varepsilon}\log r/t) tends to zero uniformly as τ↓0\tau\downarrow0. Since −2ε(1+ε)<0-2\varepsilon(1+\varepsilon) < 0, we may choose τ>0\tau> 0, depending only on CC and the fixed ε\varepsilon, so that, for some cε>0c_{\varepsilon} > 0, both cases give

EY≤exp⁡(−cεA).\mathbb{E}Y \le\exp(-c_{\varepsilon}A).

Finally, let SS be the event that the pairing is simple. By Cooper, Frieze, Reed and Riordan [10 Lemma 2.2],

P(S)≥exp⁡(−2r2)\mathbb{P}(S) \ge\exp(-2r^2)

provided 100≤r≤n/1000100 \le r \le n/1000. Since r→∞r \to\infty and r≤Clog⁡nr \le C\log n, these inequalities hold for all sufficiently large nn. Moreover,

Ar2=n(log⁡r)2r3≥nC3(log⁡n)3⟶∞.\frac{A}{r^2}=\frac{n(\log r)^2}{r^3}\ge\frac{n}{C^3(\log n)^3}\longrightarrow\infty.

By Markov’s inequality,

P(Y>0∣S)≤P(Y>0)P(S)≤EYP(S)≤exp⁡(−cεA+2r2)=o(1).\mathbb{P}(Y > 0 \mid S) \le\frac{\mathbb{P}(Y > 0)}{\mathbb{P}(S)} \le\frac{\mathbb{E}Y}{\mathbb{P}(S)} \le\exp(-c_{\varepsilon}A+2r^2)=o(1).

Taking t=τlog⁡rt=\tau\log r, write qτ=⌊τklog⁡r/2⌋q_{\tau}=\lfloor\tau k\log r/2\rfloor, and let YτY_{\tau} count the kk-sets of cells that contain at most qτq_{\tau} internal pairs. The preceding bound gives

P(Yτ>0∣S)=o(1).\mathbb{P}(Y_{\tau}>0\mid S)=o(1).

If Yτ=0Y_{\tau}=0, then no kk-set is globally tt-stable for any real 0≤t≤τlog⁡r0\le t\le\tau\log r. Indeed, such a set would satisfy

e(S)≤tk/2≤τklog⁡r/2,e(S)\le tk/2\le\tau k\log r/2,

and hence, since e(S)e(S) is an integer, e(S)≤qτe(S)\le q_{\tau}, contrary to Yτ=0Y_{\tau}=0. Every simple rr-regular graph arises from exactly (r!)n(r!)^n pairings, so the pairing conditioned on SS induces the uniform random graph Gn,rG_{n,r}, and the result follows. ◼

Further resilience

One might wonder how resilient χ(Gn,p)\chi(G_{n,p}) is to reduction by a specified non-trivial constant factor. That is, given γ∈(0,1]\gamma\in(0,1], what degree or density conditions on H⊆Gn,pH\subseteq G_{n,p} ensure that

χ(Gn,p−H)≥(1+o(1))γχ(Gn,p)a.a.s.?\chi(G_{n,p}-H)\ge(1+o(1))\gamma\chi(G_{n,p})\quad\text{a.a.s.?}

For fixed γ∈(0,1)\gamma\in(0,1), the arguments for Theorem 1 give the correct orders log⁡(np)\log(np) for Δ(H)\Delta(H) and nlog⁡(np)n\log(np) for e(H)e(H), but do not settle the sharp constants.

Our main result in earlier work [21], together with a direct first moment argument for global impropriety, answers this question when pp is fixed. Write b=1/(1−p)b=1/(1-p). We first define the constant that occurs in the answer. With Λ∗\Lambda^* as in (3), for p∈(0,1)p \in(0,1) and τ≥0\tau\ge0, let κp(τ)>τ/p\kappa_p(\tau) > \tau/p be the unique value such that

κ2Λ∗(τκ){<1if τ/p<κ<κp(τ)=1if κ=κp(τ)>1if κ>κp(τ)\frac{\kappa}{2}\Lambda^*\left(\frac{\tau}{\kappa}\right) \begin{cases} < 1 & \text{if } \tau/p < \kappa< \kappa_p(\tau) \\ = 1 & \text{if } \kappa= \kappa_p(\tau) \\ > 1 & \text{if } \kappa> \kappa_p(\tau) \end{cases}

The function κp\kappa_p is continuous and strictly increasing, with κp(0)=2/log⁡b\kappa_p(0) = 2/\log b. We define τ=τ(p,γ)\tau= \tau(p,\gamma) by

κp(0)κp(τ)=γ.(8)\frac{\kappa_p(0)}{\kappa_p(\tau)} = \gamma. \tag*{(8)}

Theorem 11. Fix p∈(0,1)p \in(0,1) and γ∈(0,1]\gamma\in(0,1], and let τ=τ(p,γ)\tau= \tau(p,\gamma) be given by (7). For every ε>0\varepsilon> 0, there is some δ>0\delta> 0 such that the following hold a.a.s.

(i) Every subgraph H⊆Gn,pH \subseteq G_{n,p} with at most (τ/2+δ)nlog⁡(np)(\tau/2+\delta)n\log(np) edges satisfies

χ(Gn,p−H)≥(1−ε)γχ(Gn,p).\chi(G_{n,p}-H) \ge(1-\varepsilon)\gamma\chi(G_{n,p}).

(ii) The same assertion holds for every H⊆Gn,pH \subseteq G_{n,p} with Δ(H)≤(τ+δ)log⁡(np)\Delta(H) \le(\tau+\delta)\log(np).

Conversely, for every η>0\eta> 0 there is some ε0>0\varepsilon_0 > 0 such that a.a.s. there are subgraphs H1,H2⊆Gn,pH_1,H_2 \subseteq G_{n,p} satisfying

e(H1)≤(τ/2+η)nlog⁡(np),Δ(H2)≤(τ+η)log⁡(np),e(H_1) \le(\tau/2+\eta)n\log(np), \qquad\Delta(H_2) \le(\tau+\eta)\log(np),

and χ(Gn,p−Hi)<(1−ε0)γχ(Gn,p)\chi(G_{n,p}-H_i) < (1-\varepsilon_0)\gamma\chi(G_{n,p}) for $i=1,2.

Proof. We first state the improper colouring estimates that we need. We proved in [21 Theorem 2] that, for every integer sequence tnt_n with tn/log⁡n→τt_n/\log n \to\tau,

χtn(Gn,p)∼nκp(τ)log⁡n\chi^{t_n}(G_{n,p}) \sim\frac{n}{\kappa_p(\tau)\log n}

a.a.s. We claim that, for every real sequence unu_n with un/log⁡n→τu_n/\log n \to\tau,

χ^un(Gn,p)∼nκp(τ)log⁡n(9)\widehat{\chi}^{u_n}(G_{n,p}) \sim\frac{n}{\kappa_p(\tau)\log n} \tag*{(9)}

a.a.s. The upper bound follows from

χ^un(Gn,p)≤χ⌊un⌋(Gn,p),\widehat{\chi}^{u_n}(G_{n,p}) \le\chi^{\lfloor u_n\rfloor}(G_{n,p}),

since every ⌊un⌋\lfloor u_n\rfloor-improper colouring has at most n⌊un⌋/2n\lfloor u_n\rfloor/2 monochromatic edges. For the lower bound, fix κ>κp(τ)\kappa> \kappa_p(\tau) and let j=⌊n/(κlog⁡n)⌋j = \lfloor n/(\kappa\log n)\rfloor. Consider a labelled colouring with at most jj colours. By the convexity argument in the proof of Lemma 6, the number of candidate monochromatic pairs is at least n(κlog⁡n−1)/2n(\kappa\log n-1)/2. Let N0=⌊n(κlog⁡n−1)/2⌋N_0 = \lfloor n(\kappa\log n-1)/2\rfloor and T=⌊nun/2⌋T = \lfloor nu_n/2\rfloor. Since T/N0→τ/κ<pT/N_0 \to\tau/\kappa< p, we have T≤pN0<N0T \le pN_0 < N_0 for all sufficiently large n. Applying Lemma 8, and using (1−p)N0=exp⁡(−N0Λ∗(0))(1-p)^{N_0}=\exp(-N_0\Lambda^*(0)) for T=0T=0, we find that the expected number of globally unu_n-improper colourings with at most jj colours is at most

exp⁡([1−κ2Λ∗(τκ)+o(1)]nlog⁡n).\exp\left(\left[1-\frac{\kappa}{2}\Lambda^*\left(\frac{\tau}{\kappa}\right)+o(1)\right]n\log n\right).

This tends to zero exponentially in nlog⁡nn\log n by the definition of κp(τ)\kappa_p(\tau). Letting κ\kappa decrease to κp(τ)\kappa_p(\tau) proves the lower bound in (9).

By continuity of κp\kappa_p and (8), we may choose δ>0\delta>0 so that both

κp(0)κp(τ+δ)>(1−ε/2)γandκp(0)κp(τ+2δ)>(1−ε/2)γ.\frac{\kappa_p(0)}{\kappa_p(\tau+\delta)}>(1-\varepsilon/2)\gamma \quad\text{and}\quad \frac{\kappa_p(0)}{\kappa_p(\tau+2\delta)}>(1-\varepsilon/2)\gamma.

Let

tn=⌊(τ+δ)log⁡(np)⌋,un=(τ+2δ)log⁡(np).t_n=\lfloor(\tau+\delta)\log(np)\rfloor,\qquad u_n=(\tau+2\delta)\log(np).

Since pp is fixed, replacing log⁡n\log n by log⁡(np)\log(np) changes only a lower-order term. The two improper colouring estimates above give

χ^tn(Gn,p)χ(Gn,p)=(1+o(1))κp(0)κp(τ+δ),\frac{\widehat{\chi}^{t_n}(G_{n,p})}{\chi(G_{n,p})}=(1+o(1))\frac{\kappa_p(0)}{\kappa_p(\tau+\delta)},
χ^un(Gn,p)χ(Gn,p)=(1+o(1))κp(0)κp(τ+2δ).\frac{\widehat{\chi}^{u_n}(G_{n,p})}{\chi(G_{n,p})}=(1+o(1))\frac{\kappa_p(0)}{\kappa_p(\tau+2\delta)}.

Propositions 3 and 4 now give the second and first assertions, respectively; for the first, note that nun/2=(τ/2+δ)nlog⁡(np)nu_n/2=(\tau/2+\delta)n\log(np).

Finally, κp\kappa_p is strictly increasing. Hence there is some ε0>0\varepsilon_0>0 such that

κp(0)κp(τ+η),κp(0)κp(τ+2η)<(1−ε0)γ.\frac{\kappa_p(0)}{\kappa_p(\tau+\eta)},\quad \frac{\kappa_p(0)}{\kappa_p(\tau+2\eta)}<(1-\varepsilon_0)\gamma.

Deleting the monochromatic edges of the corresponding improper colourings proves both sharpness assertions.

The same argument also gives the corresponding assertion for random regular graphs of fixed positive density.

Corollary 12. Fix p∈(0,1)p\in(0,1) and γ∈(0,1]\gamma\in(0,1], and let τ=τ(p,γ)\tau=\tau(p,\gamma) be as above. Suppose r/n→pr/n\to p and rnrn is even. For every ε>0\varepsilon>0, there is some δ>0\delta>0 such that the following hold a.a.s.

  1. Every subgraph H⊆Gn,rH\subseteq G_{n,r} with at most (τ/2+δ)nlog⁡r(\tau/2+\delta)n\log r edges satisfies

χ(Gn,r−H)≥(1−ε)γχ(Gn,r).\chi(G_{n,r}-H)\ge(1-\varepsilon)\gamma\chi(G_{n,r}).
  1. The same assertion holds for every H⊆Gn,rH\subseteq G_{n,r} with Δ(H)≤(τ+δ)log⁡r\Delta(H)\le(\tau+\delta)\log r.

Conversely, for every η>0\eta>0 there is some ε0>0\varepsilon_0>0 such that a.a.s. there are subgraphs H1,H2⊆Gn,rH_1,H_2\subseteq G_{n,r} satisfying

e(H1)≤(τ/2+η)nlog⁡r,Δ(H2)≤(τ+η)log⁡r,e(H_1)\le(\tau/2+\eta)n\log r,\qquad\Delta(H_2)\le(\tau+\eta)\log r,

and

χ(Gn,r−Hi)<(1−ε0)γχ(Gn,r)for i=1,2.\chi(G_{n,r}-H_i)<(1-\varepsilon_0)\gamma\chi(G_{n,r})\quad\text{for }i=1,2.

Proof. We first transfer the two improper colouring estimates used above. The root κp(τ)\kappa_p(\tau) is jointly continuous in pp and τ\tau: on a compact parameter set the unique root of the defining equation can neither approach the boundary κ=τ/p\kappa=\tau/p nor tend to infinity, and the assertion follows by taking convergent subsequences.

Fix s≥0s\ge0 and ξ>0\xi>0. By this continuity, choose δ0>0\delta_0>0 with 0<p−δ0<p+δ0<10<p-\delta_0<p+\delta_0<1 so that

∣κp−δ0(s)−κp(s)∣, ∣κp+δ0(s)−κp(s)∣<ξ.\left|\kappa_{p-\delta_0}(s)-\kappa_p(s)\right|,\ \left|\kappa_{p+\delta_0}(s)-\kappa_p(s)\right|<\xi.

Choose 0<η<10<\eta<1 so that ηp<δ0/3\eta p<\delta_0/3. Then [4 Theorem 1.1], applied with η\eta, supplies probabilities p−≤p+p_-\le p_+. Since r/n→pr/n\to p, these probabilities satisfy

p−δ0<p−≤p+<p+δ0p-\delta_0<p_-\le p_+<p+\delta_0

for all sufficiently large nn. Extending their sandwich coupling by standard monotone couplings gives

Gn,p−δ0⊆Gn,r⊆Gn,p+δ0G_{n,p-\delta_0}\subseteq G_{n,r}\subseteq G_{n,p+\delta_0}

a.a.s. Since χt\chi^t and χ^t\hat{\chi}^t are non-decreasing under the addition of edges, their values for Gn,rG_{n,r} lie between the corresponding values for the two binomial graphs. Let tnt_n be any integer sequence with tn/log⁡r→st_n/\log r\to s, and let unu_n be any real sequence with un/log⁡r→su_n/\log r\to s. Since ξ>0\xi>0 was arbitrary, the fixed-probability estimates and the choice of δ0\delta_0 give

χtn(Gn,r), χ^un(Gn,r)∼nκp(s)log⁡r.\chi^{t_n}(G_{n,r}),\ \hat{\chi}^{u_n}(G_{n,r})\sim\frac{n}{\kappa_p(s)\log r}.

The proof of Theorem 11, with log⁡r\log r in place of log⁡(np)\log(np), now applies without change. □

For the full range p→0p\to0 and np→∞np\to\infty, a corresponding exact asymptotic formula would follow from matching upper bounds for the local tt-improper chromatic number, as conjectured in [20 Conjecture 4.16] and [21]. These would also give the required global upper bounds, since χ^t≤χt\hat{\chi}^t\le\chi^t.

The asymptotic agreement between the local and global parameters for fixed pp need not persist as p→1p\to1. Fix 3/4<a<13/4<a<1 and write G=Gn,1−n−aG=G_{n,1-n^{-a}}. We show that a.a.s.

χ^1(G)≤(310+o(1))n,χ1(G)=(13+o(1))n.\hat{\chi}^1(G)\le\left(\frac{3}{10}+o(1)\right)n,\qquad\chi^1(G)=\left(\frac{1}{3}+o(1)\right)n.

Consider G‾\overline{G}, which is distributed as Gn,n−aG_{n,n^{-a}}. The expected number of four-cycles in G‾\overline{G} is O(n4−4a)=o(n)O(n^{4-4a})=o(n). Thus the set BB of vertices lying in these cycles has order o(n)o(n) a.a.s. Every graph on four vertices with maximum degree at most 1 has a complement containing a four-cycle, so each class of any 1-improper colouring contains at most three vertices outside BB. Hence χ1(G)≥(n−∣B∣)/3\chi^1(G)\ge(n-|B|)/3.

For the upper bounds, let ℓ=⌈n(3+a)/4⌉=o(n)\ell=\lceil n^{(3+a)/4}\rceil=o(n). The probability that some two disjoint sets of ℓ\ell vertices have no edge between them in G‾\overline{G} is at most

4n(1−n−a)ℓ2≤exp⁡(2nlog⁡2−n−aℓ2)=o(1),4^n(1-n^{-a})^{\ell^2}\le\exp(2n\log2-n^{-a}\ell^2)=o(1),

since n−aℓ2≥n(3−a)/2≫nn^{-a}\ell^2 \ge n^{(3-a)/2} \gg n. Thus a.a.s. G‾\overline{G} has an edge between every two disjoint ℓ\ell-vertex sets. For s∈{3,4}s \in\{3,4\}, divide any prescribed vertex set of order Θ(n)\Theta(n) into ss equal parts, setting aside fewer than ss vertices. Choose a maximal matching in G‾\overline{G} between each consecutive pair of parts; each matching leaves fewer than ℓ\ell vertices unmatched on each side. All but at most (s−1)ℓ(s-1)\ell vertices of the first part start a path following the matchings through all ss parts. We therefore obtain vertex-disjoint paths on ss vertices covering all but o(n)o(n) vertices of the chosen set. These paths need not be induced.

Applying this construction with s=3s=3 to V(G)V(G) gives triples inducing at most one edge each in GG. Using the triples and unused singletons as colour classes yields χ(G)≤n/3+o(n)\chi(G) \le n/3+o(n). For the global bound, choose disjoint sets V3,V4V_3,V_4 of orders 3⌊n/5⌋3\lfloor n/5\rfloor and 4⌊n/10⌋4\lfloor n/10\rfloor, respectively. The construction gives m3=⌊n/5⌋−o(n)m_3=\lfloor n/5\rfloor-o(n) triples in V3V_3 and m4=⌊n/10⌋−o(n)m_4=\lfloor n/10\rfloor-o(n) quadruples in V4V_4. Each triple induces at most one edge in GG, and each quadruple at most three. We use these triples and quadruples as colour classes, and give each unused vertex a distinct new colour. This uses n−2m3−3m4=3n/10+o(n)n-2m_3-3m_4=3n/10+o(n) colours. The number of monochromatic edges is at most

m3+3m4≤⌊n/5⌋+3⌊n/10⌋≤n/2,m_3+3m_4 \le\lfloor n/5\rfloor+3\lfloor n/10\rfloor\le n/2,

as required for global 1-impropriety.

Concluding remarks

We have determined the order of chromatic resilience subject to removal of edges in the binomial random graph Gn,pG_{n,p} when np→∞np\to\infty and pp is bounded away from 1, and in the random regular graph Gn,rG_{n,r} when r→∞r\to\infty and r/nr/n is bounded away from 1. At fixed positive density, we determined in § 5 the sharp constants in the bounds on e(H)e(H) and Δ(H)\Delta(H) for a prescribed constant-factor reduction in the chromatic number. Here HH is the subgraph whose edges we remove. The corresponding sharp constants in the sparse regime remain open.

As a by-product of our investigation, we have initiated the probabilistic study of the global tt-improper chromatic number, a natural parameter that may merit study in other settings for chromatic graph theory.

The bounded-average-degree case, in which p=d/np=d/n for fixed d>0d>0 or rr is fixed, leads to a quantitative refinement of the ordinary colourability problem. Fix an integer k≥3k\ge3, and consider Gn,d/nG_{n,d/n}. We ask how many edges we must delete to make this graph kk-colourable, and how this minimum grows with dd. For a graph GG on [n][n], let

del⁡k(G):=min⁡{e(F):F⊆G, χ(G−F)≤k}.\operatorname{del}_k(G) := \min\{e(F): F \subseteq G,\ \chi(G-F) \le k\}.

Equivalently, del⁡k(G)\operatorname{del}_k(G) is the minimum number of monochromatic edges over all kk-colourings of GG. Proposition 4 gives

χ^t(G)≤k⟺del⁡k(G)≤nt2.\widehat{\chi}^{t}(G) \le k \quad\Longleftrightarrow\quad\operatorname{del}_k(G) \le\frac{nt}{2}.

The following consequence of a result of Bayati, Gamarnik and Tetali [3 Theorem 1 and Corollary 1] gives the limiting deletion count.

Proposition 13. Fix an integer k≥3k \ge3. There is a deterministic, continuous, non-decreasing and 1/21/2-Lipschitz function ψk:(0,∞)→[0,∞)\psi_k : (0,\infty) \to[0,\infty) such that

del⁡k(Gn,d/n)=(ψk(d)+o(1))na.a.s.\operatorname{del}_k(G_{n,d/n}) = (\psi_k(d) + o(1))n \quad\text{a.a.s.}

for every fixed d>0d > 0. Moreover, del⁡k(Gn,dn/n)/n=ψk(d)+o(1)\operatorname{del}_k(G_{n,d_n/n})/n = \psi_k(d) + o(1) a.a.s. for every sequence dn→d>0d_n \to d > 0. Both limits also hold in expectation.

There is a constant dk∗>0d_k^* > 0 such that ψk(d)=0\psi_k(d) = 0 for 0<d≤dk∗0 < d \le d_k^* and ψk(d)>0\psi_k(d) > 0 for d>dk∗d > d_k^*.

Proof. Bayati, Gamarnik and Tetali [3 Theorem 1] prove that, for a uniform random graph GG on [n][n] with ⌊dn/2⌋\lfloor dn/2 \rfloor edges, the maximum number of properly coloured edges in a kk-colouring, divided by nn, converges to a deterministic limit. Subtracting this maximum from the edge count gives the limit for del⁡k(G)/n\operatorname{del}_k(G)/n in that model. The binomial graph is uniform conditional on its edge count, which is dn/2+o(n)dn/2 + o(n) a.a.s., so we may couple the two graphs to differ by o(n)o(n) edges. Adding or deleting one edge changes del⁡k\operatorname{del}_k by at most one, proving the binomial limit. Monotone coupling at two values of dd also gives the stated monotonicity and Lipschitz bound.

The same coupling argument applies to every sequence dn→d>0d_n \to d > 0. Both limits also hold in expectation, since del⁡k(G)≤e(G)\operatorname{del}_k(G) \le e(G) and the second moments of e(G)/ne(G)/n remain bounded. The assertion concerning dk∗d_k^* follows from [3 Corollary 1] and continuity of ψk\psi_k. ∎

The value ψk(d)\psi_k(d) is the limiting minimum number of edge deletions per vertex needed for kk-colourability. Thus, for fixed 0<d≤dk∗0 < d \le d_k^*, o(n)o(n) deletions suffice a.a.s.; for fixed d>dk∗d > d_k^*, the minimum is Θ(n)\Theta(n) a.a.s.

Corollary 14. Fix an integer k≥3k \ge3. For every fixed t>0t > 0, there is a unique bk(t)>dk∗b_k(t) > d_k^* satisfying 2ψk(bk(t))=t2\psi_k(b_k(t)) = t. For fixed 0<d<bk(t)0 < d < b_k(t), we have χ^t(Gn,d/n)≤k\widehat{\chi}^{t}(G_{n,d/n}) \le k a.a.s., whereas for fixed d>bk(t)d > b_k(t), we have χ^t(Gn,d/n)>k\widehat{\chi}^{t}(G_{n,d/n}) > k a.a.s. Moreover, bk(t)↓dk∗b_k(t) \downarrow d_k^* as t↓0t \downarrow0.

Proof. For 0<d1<d20 < d_1 < d_2, choose a kk-colouring of Gn,d2/nG_{n,d_2/n} that minimises the number of monochromatic edges. Retain each edge independently with probability d1/d2d_1/d_2. The retained graph has distribution Gn,d1/nG_{n,d_1/n}, and its minimum deletion count is at most the number of surviving monochromatic edges. Taking expectations and passing to the limit gives

ψk(d1)d1≤ψk(d2)d2.\frac{\psi_k(d_1)}{d_1} \le\frac{\psi_k(d_2)}{d_2}.

Hence ψk\psi_k is strictly increasing on (dk∗,∞)(d_k^*,\infty) and tends to infinity. Together with continuity and ψk(dk∗)=0\psi_k(d_k^*) = 0, this gives the existence and uniqueness of bk(t)b_k(t) and its stated limit. Propositions 4 and 13 give the two colourability assertions.

Thus bk(t)b_k(t) is the limiting average-degree threshold for global tt-improper kk-colourability. The scaling limit gives no conclusion at d=bk(t)d = b_k(t).

The function ψk\psi_k combines the questions for different values of t>0t > 0 into a single quantitative refinement of the Erdős–Rényi colourability problem [13]. Its relation to ordinary kk-colourability requires care: ψk(d)=0\psi_k(d)=0 means that o(n)o(n) deletions suffice, whereas ordinary kk-colourability requires no deletions.

Achlioptas and Friedgut [1 Theorem 1.1] proved that ordinary kk-colourability has a sharp threshold at a sequence of average degrees dk(n)d_k(n). Thus, for every fixed 0<η<10<\eta<1,

χ(Gn,(dk(n)−η)/n)≤kandχ(Gn,(dk(n)+η)/n)>k\chi\left(G_{n,(d_k(n)-\eta)/n}\right)\le k \quad\text{and}\quad\chi\left(G_{n,(d_k(n)+\eta)/n}\right)>k

a.a.s. We need not assume that dk(n)d_k(n) converges, although this is conjectured to be the case. The elementary first-moment bound gives dk(n)≤2klog⁡k+o(1)d_k(n)\le2k\log k+o(1), so this sequence is bounded; sharper bounds for large kk appear in [9 Theorem 1.1] and [8].

Bayati, Gamarnik and Tetali [3 Conjecture 1] conjectured exponential decay of the colourability probability above this threshold. The question that § 5 suggests is whether, at every fixed positive distance above the threshold, linearly many edge deletions are necessary for kk-colourability. The following proposition relates these assertions to convergence of the threshold to dk∗d_k^*; we use the simple-graph binomial formulation of the exponential-decay conjecture.

Proposition 15. Fix an integer k≥3k\ge3, and let dk(n)d_k(n) and dk∗d_k^* be as above. The following statements are equivalent:

(i) dk(n)→dk∗d_k(n)\to d_k^*.

(ii) For every fixed ϵ>0\epsilon>0, there exists δ=δ(k,ϵ)>0\delta=\delta(k,\epsilon)>0 such that

del⁡k(Gn,(dk(n)+ϵ)/n)≥δna.a.s.\operatorname{del}_k\left(G_{n,(d_k(n)+\epsilon)/n}\right)\ge\delta n\quad\text{a.a.s.}

(iii) For every fixed ϵ>0\epsilon>0, there exists γ=γ(k,ϵ)>0\gamma=\gamma(k,\epsilon)>0 such that

P(χ(Gn,(dk(n)+ϵ)/n)≤k)≤e−γn\mathbb{P}\left(\chi\left(G_{n,(d_k(n)+\epsilon)/n}\right)\le k\right)\le e^{-\gamma n}

for all sufficiently large nn.

Proof. For the equivalence of (ii) and (iii), we transfer the resilience and exponential-decay assertions between the binomial and fixed-edge-count models by monotone coupling and Chernoff bounds, using a smaller positive margin in the source model and incurring an exponentially small coupling error.

Assume (iii), and fix ϵ>0\epsilon>0. Take a uniform random graph GG on [n][n] with m=⌊(dk(n)+ϵ)n/2⌋=O(n)m=\lfloor(d_k(n)+\epsilon)n/2\rfloor=O(n) edges. Deleting the edges at any fixed ⌊δn⌋\lfloor\delta n\rfloor positions in a uniform random ordering leaves a uniform random graph with m−⌊δn⌋m-\lfloor\delta n\rfloor edges. For fixed 0<δ<ϵ/40<\delta<\epsilon/4, its average degree exceeds dk(n)+ϵ/2d_k(n)+\epsilon/2 for all sufficiently large nn. Exponential decay at a smaller fixed positive margin and a union bound therefore give, for some γ>0\gamma>0 independent of δ\delta,

P(del⁡k(G)≤⌊δn⌋)≤(m⌊δn⌋)e−γn=exp⁡((O(δlog⁡(1/δ))−γ)n)=o(1),\begin{aligned} \mathbb{P}\left(\operatorname{del}_k(G)\le\lfloor\delta n\rfloor\right)\le\binom{m}{\lfloor\delta n\rfloor}e^{-\gamma n} \\ &=\exp\left((O(\delta\log(1/\delta))-\gamma)n\right)=o(1), \end{aligned}

provided δ\delta is sufficiently small. For the converse, if del⁡k(G)≥δn\operatorname{del}_k(G)\ge\delta n a.a.s., then its expectation is at least (δ+o(1))n(\delta+o(1))n. The bounded-differences inequality applied to del⁡k(G)\operatorname{del}_k(G) in the fixed-edge-count model gives an exponentially small bound on P(del⁡k(G)=0)\mathbb{P}(\operatorname{del}_k(G)=0). Bayati, Gamarnik and Tetali use this deletion argument and their scaling theorem to deduce threshold convergence from the conjecture.

To deduce (i) from (ii), consider any subsequence along which dk(n)→Ld_k(n) \to L. The sharp-threshold result gives ψk(d)=0\psi_k(d) = 0 for d<Ld < L, whereas the resilience assertion and Proposition 13 give ψk(d)>0\psi_k(d) > 0 for d>Ld > L. Hence L=dk∗L = d_k^*, and boundedness of dk(n)d_k(n) proves convergence. Conversely, if dk(n)→dk∗d_k(n) \to d_k^*, applying Proposition 13 with dn=dk(n)+εd_n = d_k(n) + \varepsilon gives the resilience assertion with any 0<δ<ψk(dk∗+ε)0 < \delta< \psi_k(d_k^* + \varepsilon).

Beyond identifying the transition, we ask how quickly the minimum deletion count grows above it. This question does not require the exponential-decay conjecture. The 1/21/2-Lipschitz property gives ψk(dk∗+ε)≤ε/2\psi_k(d_k^* + \varepsilon) \le\varepsilon/2. Does a matching linear lower bound hold, or equivalently, is

ψk(dk∗+ε)=Θ(ε)as ε↓0?\psi_k(d_k^* + \varepsilon) = \Theta(\varepsilon) \quad\text{as } \varepsilon\downarrow0?

Open access statement

For the purpose of open access, a CC BY public copyright license is applied to any Author Accepted Manuscript (AAM) arising from this submission.

Declaration on the use of generative AI

We began this project in 2012 and revisited it intermittently thereafter. The present paper retains the principal questions, results and mathematical ideas of the original manuscript and incorporates subsequent progress on sandwich couplings in its treatment of random regular graphs.

In preparing the present version, the first author used a commercially available, closed-weight generative AI system to improve the exposition, check notation and citations, clarify technical details, and develop and check elementary deductions concerning the concluding remarks and the case p→1p \to1. It was not used to develop the main results or their proof strategies.

References

  1. [1]D. Achlioptas and E. Friedgut. A sharp threshold for k-colorability. Random Structures Algorithms, 14(1):63–70, 1999.
  2. [2]N. Alon and B. Sudakov. Increasing the chromatic number of a random graph. J. Comb., 1(3-4):345–356, 2010.arxiv.org/abs/1002.1748
  3. [3]M. Bayati, D. Gamarnik, and P. Tetali. Combinatorial approach to the interpolation method and scaling limits in sparse random graphs. Ann. Probab., 41(6):4080–4115, 2013.
  4. [4]N. Behague, D. Il’kovič, and R. Montgomery. A proof of the Kim–Vu sandwich conjecture, 2025. arXiv:2510.20765v2.arxiv.org/abs/2510.20765
  5. [5]B. Bollobás. The chromatic number of random graphs. Combinatorica, 8(1):49–55, 1988.DOI
  6. [6]B. Bollobás. Random Graphs, volume 73 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2nd edition, 2001.
  7. [7]B. Bollobás and L. Clark. Generalized chromatic numbers of random regular graphs. In Graph theory, combinatorics, and algorithms, Vol. 1, 2 (Kalamazoo, MI, 1992), Wiley-Intersci. Publ., pages 209–219. Wiley, New York, 1995.DOI
  8. [8]A. Coja-Oghlan. Upper-bounding the k-colorability threshold by counting covers. Electron. J. Combin., 20(3):Paper 32, 28, 2013.
  9. [9]A. Coja-Oghlan and D. Vilenchik. The chromatic number of random graphs for most average degrees. Int. Math. Res. Not. IMRN, 2016(19):5801–5859, 2016.
  10. [10]C. Cooper, A. Frieze, B. Reed, and O. Riordan. Random regular graphs of non-constant degree: independence and chromatic number. Combin. Probab. Comput., 11(4):323–341, 2002.DOI
  11. [11]L. Cowen, W. Goddard, and C. E. Jesurum. Defective coloring revisited. J. Graph Theory, 24(3):205–219, 1997.doi.org/10.1002/(sici)1097-0118(199703)24:3<205::aid-jgt2>3.0.co;2-t
  12. [12]A. Dembo and O. Zeitouni. Large Deviations Techniques and Applications, volume 38 of Applications of Mathematics (New York). Springer-Verlag, New York, 2nd edition, 1998.
  13. [13]P. Erdős and A. Rényi. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl., 5:17–61, 1960.
  14. [14]N. Fontoulakis, R. J. Kang, and C. McDiarmid. The t-stability number of a random graph. Electron. J. Combin., 17(1):Research Paper 59, 29 pp, 2010.
  15. [15]N. Fontoulakis, R. J. Kang, and C. McDiarmid. Largest sparse subgraphs of random graphs. European J. Combin., 35:232–244, 2014.
  16. [16]A. M. Frieze and T. Łuczak. On the independence and chromatic numbers of random regular graphs. J. Combin. Theory Ser. B, 54(1):123–132, 1992.DOI
  17. [17]P. Gao, M. Isaev, and B. D. McKay. Kim–Vu’s sandwich conjecture is true for d ≫ log⁴ n, 2025. arXiv:2011.09449v5.
  18. [18]P. Gao, M. Isaev, and X. Perez-Gimenez. Sandwiching between random regular graphs and Erdős–Rényi graphs: configuration model and unions of perfect matchings, 2025. arXiv:2510.21472.arxiv.org/abs/2510.21472
  19. [19]S. Janson, T. Łuczak, and A. Rucinski. Random Graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000.
  20. [20]R. J. Kang. Improper Colourings of Graphs. PhD thesis, University of Oxford, 2008. http://ora.ouls.ox.ac.uk/objects/uuid:a93d8303-0eeb-4d01-9b77-364113b81a63.DOI
  21. [21]R. J. Kang and C. McDiarmid. The t-improper chromatic number of random graphs. Combin. Probab. Comput., 19(1):87–98, 2010.
  22. [22]R. J. Kang and C. McDiarmid. Colouring random graphs. In L. W. Beineke and R. J. Wilson, editors, Topics in Chromatic Graph Theory, volume 156 of Encyclopaedia of Mathematics and its Applications, pages 199–229. Cambridge University Press, 2015.DOI
  23. [23]J. H. Kim, B. Sudakov, and V. H. Vu. On the asymmetry of random regular graphs and random graphs. Random Structures Algorithms, 21(3-4):216–224, 2002. Random structures and algorithms (Poznan, 2001).DOI
  24. [24]J. H. Kim and V. H. Vu. Sandwiching random graphs: universality between random graph models. Adv. Math., 188(2):444–469, 2004.DOI
  25. [25]L. Lovász. On decompositions of graphs. Studia Sci. Math. Hungar., 1:237–238, 1966.
  26. [26]F. Lucke and F. Mann. Reducing graph parameters by contractions and deletions. Algorithmica, 86:825–851, 2024.arxiv.org/abs/2210.10503
  27. [27]T. Luczak. The chromatic number of random graphs. Combinatorica, 11(1):45–54, 1991.DOI
  28. [28]D. Matula and L. Kučera. An expose-and-merge algorithm and the chromatic number of a random graph. In Random Graphs ’87 (Poznań, 1987), pages 175–187. Wiley, Chichester, 1990.
  29. [29]B. Sudakov. Robustness of graph properties. In Surveys in combinatorics 2017, volume 440 of London Math. Soc. Lecture Note Ser., pages 372–408. Cambridge Univ. Press, Cambridge, 2017.arxiv.org/abs/1610.00117
  30. [30]B. Sudakov and V. H. Vu. Local resilience of graphs. Random Structures Algorithms, 33(4):409–433, 2008.arxiv.org/abs/0706.4104
  31. [31]D. R. Wood. Defective and clustered graph colouring. Electron. J. Combin., pages Paper No. DS23, 71 pp., 2018.arxiv.org/abs/1803.07694

Paper details

vlnc:W_tjb69mes
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

a commercially available, closed-weight generative AI system

View statement
Looking for related papers…
Contents