In this paper
AbstractIntroductionImpropriety and resilienceProof of Theorem 1Proof of Theorem 2Further resilienceConcluding remarksOpen access statementDeclaration on the use of generative AIReferencesWorksMathematics
Impropriety and resilience of the chromatic number
Abstract
We show that, for bounded away from and , the chromatic number of the binomial random graph is resilient to removal of a subgraph with edges. It follows that the same assertion holds with being a subgraph of maximum degree ; and both these results are best possible up to a constant factor. We also prove corresponding results for the random -regular graph , when and is bounded away from , where has edges or maximum degree . 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 subject to the addition, rather than removal, of edges.
Introduction
Let denote the binomial random graph with vertex set in which the edges are included independently at random with probability and let . The chromatic number of 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 a constant) remains open, but there are very strong estimates — see [8, 9] for progress. In the case where and is bounded away from 1, it is a classic result due to Bollobás [5], Matula and Kučera [28] and Łuczak [27] that
asymptotically almost surely (a.a.s.), that is, with probability approaching 1 as . Recall that if , then , so the right-hand side may be written as . Throughout, 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 , specifically for any fixed , the following result holds: a.a.s. is resilient to the addition of any subset of edges on ; that is, for any , there exists such that no matter how an adversary chooses a graph on with at most edges,
This is best possible up to a constant factor, as can be seen by considering to be the edges of a clique on vertices. Under the same conditions for , they also proved a local version, for which has maximum degree ; this is best possible up to a 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 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 be bounded away from 1 and . The following hold a.a.s.
(i) is (globally) resilient to removal of any subgraph with edges.
(ii) is (locally) resilient to removal of any subgraph of maximum degree .
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 , there exists such that no matter how an adversary chooses with at most edges,
this is the global resilience result, which implies the local one. On the other hand, for some , there exists of maximum degree at most such that
and, for any , there exist and with at most edges such that
The main message to take from Theorem 1 is that decreasing is a global task, of removing edges throughout . In contrast, the results of Alon and Sudakov say that increasing is essentially a local task, of adding a clique, if does not decay too rapidly. If the chromatic resilience results for edge addition were extended to the entire range of with and , then, at least when , 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 is very sparse and the other way around if is very dense (with the switch at around , up to logarithmic factors).
We also consider random regular graphs. Their study helped to initiate the broader theory of resilience [24]. Let denote the random -regular graph, chosen uniformly from the set of all -regular graphs with vertex set (assuming is even). The Kim–Vu sandwich conjecture [24] gives a useful connection between the binomial and random regular models. It asserts that, when , one may couple with two binomial random graphs and such that
a.a.s., where and . Gao, Isaev and McKay [17] recently proved it whenever . 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 satisfy and for some fixed . The following hold a.a.s.
(i) is (globally) resilient to removal of any subgraph with edges.
(ii) is (locally) resilient to removal of any subgraph of maximum degree .
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) -improper chromatic number of a graph is the smallest number of colours needed in a (local) -improper colouring — a colouring of the vertices of so that each subgraph induced by some colour class has maximum degree at most . See [31] for a survey of this type of colouring parameter, especially with respect to sparse graph classes. The global -improper chromatic number of a graph on vertices is the smallest number of colours needed in a global -improper colouring — a colouring of the vertices of so that the total number of edges in the subgraphs induced by colour classes is at most . Equivalently, the spanning subgraph of monochromatic edges has average degree at most . We write for the average degree of . The global -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 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 and include the chromatic number as a special case by taking . Clearly for every real . Furthermore, it follows from a result of Lovász [25] that for every non-negative integer , where denotes the maximum degree of . Summarising, we have that for any graph and non-negative real
We now present two elementary correspondences between local/global resilience of the chromatic number and local/global improper colouring.
Proposition 3. Let be a graph, a non-negative integer, and a positive integer. The following statements are equivalent:
(i) .
(ii) There exists a subgraph of with such that .
Proposition 4. Let be a graph on vertices, a non-negative real number, and a positive integer. The following statements are equivalent:
(i) .
(ii) There exists a subgraph of with at most edges such that .
Both correspondences follow by deleting the monochromatic edges of an improper colouring and, conversely, using a proper colouring of .
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) -stability number of a graph is the number of vertices in a largest (local) -stable set, a subset of the vertices whose induced subgraph has maximum degree at most . The global -stability number of a graph is the number of vertices in a largest global -stable set, a subset of the vertices whose induced subgraph has average degree at most . (We called global -stability -sparsity in [15].)
Both of these parameters are non-decreasing in and include the stability number as a special case by taking . For every non-negative real , we have and moreover
Thus we may bound from below by bounding or from above.
As we next show, we can also bound from below by bounding the global stability of from above, although the connection holds in a weaker sense than above in that we need to bound for some . (Note that in this case always.)
Proposition 5. Let be a graph on and . Suppose that there exist and such that . Then .
Proof. Let . If , the result is immediate. Otherwise, suppose for a contradiction that . Consider any global -improper colouring of the graph using colours and let be the union of those colour classes of having fewer than vertices. We then have
It follows that the number of vertices in colour classes of having at least vertices is more than . Since , each such colour class of induces a subgraph of average degree greater than . Summing over all these vertices, we see that the number of monochromatic edges under is more than , contradicting that is a global -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 -improper chromatic numbers.
Lemma 6. Suppose is bounded away from 1 and . There exist constants and such that, if and , then a.a.s.
Lemma 7. Suppose is bounded away from 1, and . If is a positive integer, then 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 . Let . Proposition 4 and Lemma 6 give, a.a.s. and simultaneously for every subgraph with at most edges,
Together with the usual upper bound on , this proves the first two assertions.
We next prove that the local assertion is best possible up to a constant factor. Take
Uniformly for bounded away from 1, we have . Moreover,
Lemma 7, with , therefore gives
for all sufficiently large . The required subgraph now follows from Proposition 3.
It remains to prove that the global assertion is best possible. Fix and set . We use the standard a.a.s. estimates
simultaneously; see, for example, [6, 19]. We shall also use the following density property.
If , then a Chernoff bound followed by a union bound over the at most sets shows that, for any fixed , a.a.s. simultaneously for every with ,
Indeed, the exponent in the Chernoff bound has order .
Fix an optimal proper colouring with colours, take , and let be the union of the largest colour classes. Writing the sizes of the colour classes in non-increasing order as , we have
On the other hand, each colour class has size at most , and hence
Consequently, . Retain the other colour classes and order the vertices of . 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 is then counted when its later endpoint is recoloured. The total number of monochromatic edges is consequently at most
where we used . Removing these monochromatic edges leaves a graph coloured with colours, which is smaller than for all sufficiently large . 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 , let
(where and ). This is the Fenchel-Legendre transform of the logarithmic moment generating function associated with the Bernoulli distribution with probability (cf. [12 Exercise 2.2.23(b)]). It is easy to see that has a global minimum of at , is strictly decreasing on and strictly increasing on . Let denote the binomial distribution. We use the following estimate from [21 Lemma 4].
Lemma 8. There is a constant such that the following holds. Let , let be a positive integer, and let . Then, for each integer such that ,
Lemma 9. For every , there is some such that, for and ,
Proof. We first consider close to zero. Uniformly for in any fixed interval , with interpreted as zero when , we have
Since and as , the required inequality follows for all sufficiently small and .
For in a compact interval bounded away from zero, the assertion follows from uniform continuity at , since . Combining the two ranges gives a choice of that is uniform over .
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 -stability number of and then apply Proposition 5; however, this gives a smaller admissible value of . The method we demonstrate here is sharp (with respect to ) for fixed , as we show in § 5.
Proof of Lemma 6. Choose so that . Let and . Consider any colouring of using at most colours, and let be the number of pairs of vertices contained in its colour classes. By convexity,
Let and . For , we have
Since is bounded uniformly for bounded away from 1, we may choose so that, for all sufficiently large , we have and Lemma 9 yields
The number of monochromatic edges in the colouring stochastically dominates . For , Lemma 8 therefore gives
If , the colouring is globally -improper only if none of its candidate monochromatic pairs forms an edge. Since , the probability of this event is at most
so the same estimate remains valid.
Moreover,
and hence . A union bound over the at most labelled colourings now gives a probability at most
Thus a.a.s. there is no global -improper colouring using at most colours, as required.
Proof of Lemma 7. Let . Choose sufficiently large. If , a Chernoff bound and a union bound over the vertices give a.a.s. The result then follows directly from (1) for all sufficiently large .
It remains to consider . Let
We shall show that the graph induced by has degeneracy less than
We first bound the size of . If , it has some set of size . Condition on the edges from to , and for each let
The edge indicators defining the variables , , are disjoint, and hence these variables are independent. Since , we must have for all sufficiently large . It follows from a Chernoff bound, cf. [19 Theorem 2.1], that for some constants $c,c' > 0,
Let . If , then Markov’s inequality gives a.a.s.; if , then . Thus we may assume that .
We next rule out all dense subsets of this size simultaneously. For , let . Since , a union bound gives
for all sufficiently large . Summing this estimate over gives . Every graph of minimum degree at least contains at least vertices and at least edges, so has degeneracy at most a.a.s.
Finally, use disjoint sets of colours on , and . By (1) and the degeneracy bound,
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 is at most a constant multiple of . 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 and for some fixed , we may use
a.a.s., where .
Recall (2). For the lower range, we shall need the following upper bound on the global -stability number.
Lemma 10. Fix . Suppose is a positive integer, is even, and . There is some such that, if , then
a.a.s., where .
Let us first see how this lemma is used to prove Theorem 2.
Proof of Theorem 2. Fix , and let . Choose sufficiently small in terms of and the constant in the theorem. By [4 Theorem 1.1], there is some such that, whenever , there are probabilities and a coupling for which
a.a.s., where
We choose small enough that .
Suppose first that . Apply Lemma 10 with and with the parameter in that lemma equal to . Since , this gives
a.a.s. Proposition 5, applied with and , now yields
We next suppose that . The parameters and are non-decreasing under the addition of edges, so (5) and Lemma 6 give the required lower bound from . For completeness, if , then uniformly for ,
The ordinary upper bound follows in the same way from . Since was arbitrary, Propositions 3 and 4 prove both resilience assertions.
It remains to prove the two sharpness statements. By (1) and (4), with ,
This proves the local assertion by Proposition 3.
For the global assertion, fix an optimal proper colouring with colours, discard colour classes, and let be their union. Recolour the vertices of sequentially with the remaining 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
Given , choose so that . Then, a.a.s., the number of monochromatic edges is at most . Removing these edges leaves a graph coloured with colours, fewer than for all sufficiently large , 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 . It is enough to show that a.a.s. there is no global -stable set of exactly vertices. Indeed, if a set of vertices spans at most edges, then a uniform random -subset of satisfies
Thus some such is globally -stable.
We use the pairing model. A pairing is a perfect matching of points partitioned into cells of points each, and it induces the usual random regular multigraph. Fix cells, write , and let denote the number of pairs having both points in these cells. Writing , a direct count gives, for
We have outside this range. Here and below we use , corresponding to the unique pairing of the empty set. Cancelling consecutive terms, we obtain
Since , we have
In particular, for all sufficiently large . Let
Iterating (6) gives . Exposing in turn the partners of the points also gives
Let . Since , the support of is . Moreover,
so lies in this support for all sufficiently large . Uniformly for and ,
and hence
Thus we may choose so that implies . We use the bound on directly for ; otherwise,
Let count the -sets of cells that contain at most 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, counts precisely the global -stable -sets. Let . Uniformly for and , we have
Suppose first that . Then , and hence
Using and enlarging if necessary, we obtain
Together with , the estimates above give
For , the direct bound instead gives
For , the term tends to zero uniformly as . Since , we may choose , depending only on and the fixed , so that, for some , both cases give
Finally, let be the event that the pairing is simple. By Cooper, Frieze, Reed and Riordan [10 Lemma 2.2],
provided . Since and , these inequalities hold for all sufficiently large . Moreover,
By Markov’s inequality,
Taking , write , and let count the -sets of cells that contain at most internal pairs. The preceding bound gives
If , then no -set is globally -stable for any real . Indeed, such a set would satisfy
and hence, since is an integer, , contrary to . Every simple -regular graph arises from exactly pairings, so the pairing conditioned on induces the uniform random graph , and the result follows. ◼
Further resilience
One might wonder how resilient is to reduction by a specified non-trivial constant factor. That is, given , what degree or density conditions on ensure that
For fixed , the arguments for Theorem 1 give the correct orders for and for , 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 is fixed. Write . We first define the constant that occurs in the answer. With as in (3), for and , let be the unique value such that
The function is continuous and strictly increasing, with . We define by
Theorem 11. Fix and , and let be given by (7). For every , there is some such that the following hold a.a.s.
(i) Every subgraph with at most edges satisfies
(ii) The same assertion holds for every with .
Conversely, for every there is some such that a.a.s. there are subgraphs satisfying
and 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 with ,
a.a.s. We claim that, for every real sequence with ,
a.a.s. The upper bound follows from
since every -improper colouring has at most monochromatic edges. For the lower bound, fix and let . Consider a labelled colouring with at most colours. By the convexity argument in the proof of Lemma 6, the number of candidate monochromatic pairs is at least . Let and . Since , we have for all sufficiently large n. Applying Lemma 8, and using for , we find that the expected number of globally -improper colourings with at most colours is at most
This tends to zero exponentially in by the definition of . Letting decrease to proves the lower bound in (9).
By continuity of and (8), we may choose so that both
Let
Since is fixed, replacing by changes only a lower-order term. The two improper colouring estimates above give
Propositions 3 and 4 now give the second and first assertions, respectively; for the first, note that .
Finally, is strictly increasing. Hence there is some such that
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 and , and let be as above. Suppose and is even. For every , there is some such that the following hold a.a.s.
Every subgraph with at most edges satisfies
The same assertion holds for every with .
Conversely, for every there is some such that a.a.s. there are subgraphs satisfying
and
Proof. We first transfer the two improper colouring estimates used above. The root is jointly continuous in and : on a compact parameter set the unique root of the defining equation can neither approach the boundary nor tend to infinity, and the assertion follows by taking convergent subsequences.
Fix and . By this continuity, choose with so that
Choose so that . Then [4 Theorem 1.1], applied with , supplies probabilities . Since , these probabilities satisfy
for all sufficiently large . Extending their sandwich coupling by standard monotone couplings gives
a.a.s. Since and are non-decreasing under the addition of edges, their values for lie between the corresponding values for the two binomial graphs. Let be any integer sequence with , and let be any real sequence with . Since was arbitrary, the fixed-probability estimates and the choice of give
The proof of Theorem 11, with in place of , now applies without change. □
For the full range and , a corresponding exact asymptotic formula would follow from matching upper bounds for the local -improper chromatic number, as conjectured in [20 Conjecture 4.16] and [21]. These would also give the required global upper bounds, since .
The asymptotic agreement between the local and global parameters for fixed need not persist as . Fix and write . We show that a.a.s.
Consider , which is distributed as . The expected number of four-cycles in is . Thus the set of vertices lying in these cycles has order 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 . Hence .
For the upper bounds, let . The probability that some two disjoint sets of vertices have no edge between them in is at most
since . Thus a.a.s. has an edge between every two disjoint -vertex sets. For , divide any prescribed vertex set of order into equal parts, setting aside fewer than vertices. Choose a maximal matching in between each consecutive pair of parts; each matching leaves fewer than vertices unmatched on each side. All but at most vertices of the first part start a path following the matchings through all parts. We therefore obtain vertex-disjoint paths on vertices covering all but vertices of the chosen set. These paths need not be induced.
Applying this construction with to gives triples inducing at most one edge each in . Using the triples and unused singletons as colour classes yields . For the global bound, choose disjoint sets of orders and , respectively. The construction gives triples in and quadruples in . Each triple induces at most one edge in , 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 colours. The number of monochromatic edges is at most
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 when and is bounded away from 1, and in the random regular graph when and is bounded away from 1. At fixed positive density, we determined in § 5 the sharp constants in the bounds on and for a prescribed constant-factor reduction in the chromatic number. Here 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 -improper chromatic number, a natural parameter that may merit study in other settings for chromatic graph theory.
The bounded-average-degree case, in which for fixed or is fixed, leads to a quantitative refinement of the ordinary colourability problem. Fix an integer , and consider . We ask how many edges we must delete to make this graph -colourable, and how this minimum grows with . For a graph on , let
Equivalently, is the minimum number of monochromatic edges over all -colourings of . Proposition 4 gives
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 . There is a deterministic, continuous, non-decreasing and -Lipschitz function such that
for every fixed . Moreover, a.a.s. for every sequence . Both limits also hold in expectation.
There is a constant such that for and for .
Proof. Bayati, Gamarnik and Tetali [3 Theorem 1] prove that, for a uniform random graph on with edges, the maximum number of properly coloured edges in a -colouring, divided by , converges to a deterministic limit. Subtracting this maximum from the edge count gives the limit for in that model. The binomial graph is uniform conditional on its edge count, which is a.a.s., so we may couple the two graphs to differ by edges. Adding or deleting one edge changes by at most one, proving the binomial limit. Monotone coupling at two values of also gives the stated monotonicity and Lipschitz bound.
The same coupling argument applies to every sequence . Both limits also hold in expectation, since and the second moments of remain bounded. The assertion concerning follows from [3 Corollary 1] and continuity of . ∎
The value is the limiting minimum number of edge deletions per vertex needed for -colourability. Thus, for fixed , deletions suffice a.a.s.; for fixed , the minimum is a.a.s.
Corollary 14. Fix an integer . For every fixed , there is a unique satisfying . For fixed , we have a.a.s., whereas for fixed , we have a.a.s. Moreover, as .
Proof. For , choose a -colouring of that minimises the number of monochromatic edges. Retain each edge independently with probability . The retained graph has distribution , and its minimum deletion count is at most the number of surviving monochromatic edges. Taking expectations and passing to the limit gives
Hence is strictly increasing on and tends to infinity. Together with continuity and , this gives the existence and uniqueness of and its stated limit. Propositions 4 and 13 give the two colourability assertions.
Thus is the limiting average-degree threshold for global -improper -colourability. The scaling limit gives no conclusion at .
The function combines the questions for different values of into a single quantitative refinement of the Erdős–Rényi colourability problem [13]. Its relation to ordinary -colourability requires care: means that deletions suffice, whereas ordinary -colourability requires no deletions.
Achlioptas and Friedgut [1 Theorem 1.1] proved that ordinary -colourability has a sharp threshold at a sequence of average degrees . Thus, for every fixed ,
a.a.s. We need not assume that converges, although this is conjectured to be the case. The elementary first-moment bound gives , so this sequence is bounded; sharper bounds for large 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 -colourability. The following proposition relates these assertions to convergence of the threshold to ; we use the simple-graph binomial formulation of the exponential-decay conjecture.
Proposition 15. Fix an integer , and let and be as above. The following statements are equivalent:
(i) .
(ii) For every fixed , there exists such that
(iii) For every fixed , there exists such that
for all sufficiently large .
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 . Take a uniform random graph on with edges. Deleting the edges at any fixed positions in a uniform random ordering leaves a uniform random graph with edges. For fixed , its average degree exceeds for all sufficiently large . Exponential decay at a smaller fixed positive margin and a union bound therefore give, for some independent of ,
provided is sufficiently small. For the converse, if a.a.s., then its expectation is at least . The bounded-differences inequality applied to in the fixed-edge-count model gives an exponentially small bound on . 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 . The sharp-threshold result gives for , whereas the resilience assertion and Proposition 13 give for . Hence , and boundedness of proves convergence. Conversely, if , applying Proposition 13 with gives the resilience assertion with any .
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 -Lipschitz property gives . Does a matching linear lower bound hold, or equivalently, is
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 . It was not used to develop the main results or their proof strategies.
References
- [1]D. Achlioptas and E. Friedgut. A sharp threshold for k-colorability. Random Structures Algorithms, 14(1):63–70, 1999.
- [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]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]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]B. Bollobás. The chromatic number of random graphs. Combinatorica, 8(1):49–55, 1988.DOI
- [6]B. Bollobás. Random Graphs, volume 73 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2nd edition, 2001.
- [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]A. Coja-Oghlan. Upper-bounding the k-colorability threshold by counting covers. Electron. J. Combin., 20(3):Paper 32, 28, 2013.
- [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]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]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]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]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]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]N. Fontoulakis, R. J. Kang, and C. McDiarmid. Largest sparse subgraphs of random graphs. European J. Combin., 35:232–244, 2014.
- [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]P. Gao, M. Isaev, and B. D. McKay. Kim–Vu’s sandwich conjecture is true for d ≫ log⁴ n, 2025. arXiv:2011.09449v5.
- [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]S. Janson, T. Łuczak, and A. Rucinski. Random Graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000.
- [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]R. J. Kang and C. McDiarmid. The t-improper chromatic number of random graphs. Combin. Probab. Comput., 19(1):87–98, 2010.
- [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]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]J. H. Kim and V. H. Vu. Sandwiching random graphs: universality between random graph models. Adv. Math., 188(2):444–469, 2004.DOI
- [25]L. Lovász. On decompositions of graphs. Studia Sci. Math. Hungar., 1:237–238, 1966.
- [26]F. Lucke and F. Mann. Reducing graph parameters by contractions and deletions. Algorithmica, 86:825–851, 2024.arxiv.org/abs/2210.10503
- [27]T. Luczak. The chromatic number of random graphs. Combinatorica, 11(1):45–54, 1991.DOI
- [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]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]B. Sudakov and V. H. Vu. Local resilience of graphs. Random Structures Algorithms, 33(4):409–433, 2008.arxiv.org/abs/0706.4104
- [31]D. R. Wood. Defective and clustered graph colouring. Electron. J. Combin., pages Paper No. DS23, 71 pp., 2018.arxiv.org/abs/1803.07694