Cliques and Chromatic Number in Multiregime Random Graphs

Abstract

In this paper, we study cliques and chromatic number in the random subgraph G_n of the complete graph K_n on n vertices, where each edge is independently open with a probability p_n. Associating G_n with the probability measure ℙ_n, we say that the sequence {ℙ_n} is multiregime if the edge probability sequence {p_n} is not convergent. Using a recursive method we obtain uniform bounds on the maximum clique size and chromatic number for such multiregime random graphs.

1 Introduction

The study of cliques and chromatic numbers in random subgraphs of the complete graph K_n on n vertices is of importance from both theoretical and application perspectives. For the case where every edge of K_n is independently open with probability p_n with limnp_n ∈{0, p,1} for some 0 < p < 1, bounds on cliques and chromatic numbers have been obtained using a combination of second moment method and martingale inequalities (see Alon and Spencer (2003) & Bollobás (2001)) and references therein). For the intermediate regime where p_n = p is a constant, Shamir and Spencer (1987) studied the concentration of the chromatic number around its mean using martingale techniques. Sharp bounds for the chromatic number was then derived in Bollobás (1988) by exploring a maximal disjoint set of cliques. Alex Scott (2008) uses a combinatorial argument to sharpen the interval of concentration of the chromatic number to within an interval of length n log n and Panagiotou and Steger (2009) use a counting argument to obtain sharp lower bounds on the chromatic number.

For the sparse regime where p_n → 0 as n →∞, Frieze (1990) uses martingales to investigate the independence number of homogenous random graphs and Luczak (1991) studies the chromatic number using a more delicate second moment method. Alon and Krivelevich (1997) use k −choosable graphs to study two point concentration of the chromatic number when the edge probability p_n = n^{− 1/2−δ} for δ > 0. More recently, Achlioptas and Naor (2005) use an analytic approach combining sharp threshold results with second moment methods to obtain the two possible values of the chromatic number when p_n = d n and d > 0 is a constant.

In this paper, we consider random graphs where the edge probability {p_n} is not necessarily convergent and use a recursive method to obtain bounds for the clique numbers and consequently the chromatic numbers. In the rest of this subsection, we briefly describe the random graph model under consideration and state our main results (Theorems 1 and 2) regarding the cliques and chromatic number.

1.1 Clique Number

For n ≥ 2, let K_n be the labelled complete graph with vertex set {1, 2, … , n} and for 1 ≤ i < j ≤ n, let e(i, j) be the edge between the vertices i and j. Let {X(i, j)}_1≤i<j≤n be independent Bernoulli random variables with

$$\mathbb{P}_{n}(X(i,j) = 1) = 1 -\mathbb{P}_{n}(X(i,j) = 0) = p_{n}.$$

We say that edge e(i, j) is open if X(i, j) = 1 and closed otherwise. The resulting random graph G = G(n, p_n) is an Erdős-Rényi (ER) random graph, defined on the probability space (Ω,, ℙ_n). We say that the sequence of probability measures {ℙ_n} is multiregime if {p_n} is not convergent. For notational simplicity we henceforth drop the subscript from the probability measure ℙ_n and denote it simply as ℙ.

A subset U ⊆ {1, … , n} is said to be an open clique of G if for all u, v ∈ U, the edge e(u, v) is open. The clique number

$$\omega(G) := \max\{\#U : U \subseteq \{1,2,\ldots,n\}\text{ is an open clique}\}$$

is the size of the largest open clique in G, where #U denotes the cardinality of a set U. To estimate ω(G), we let

$$ W_{n} := \frac{\log{n}}{\log\left( \frac{1}{p_{n}}\right)} $$

(1.1)

and define

$$ \alpha_{1} := \limsup_{n} \frac{\log\left( \frac{1}{p_{n}}\right)}{\log{n}} \text{ and } \alpha_{2} := \limsup_{n} \frac{\log\left( \frac{1}{1-p_{n}}\right)}{\log{n}}. $$

(1.2)

Theorem 1.

Suppose α₁ < 2 and α₂ < 1. There are positive constants η and γ such that

$$ \eta < 1-\alpha_{2} \text{ and } 2(\alpha_{2} + \eta-\gamma) > \max(\alpha_{1},2\alpha_{2}). $$

(1.3)

For all 𝜖 > 0 and η, γ satisfying (1.3), there is a positive integer N ≥ 1 so that

$$ \begin{array}{@{}rcl@{}} &&\mathbb{P}\left( (1-\eta-\alpha_{2})W_{n} \leq \omega(G(n,p_{n})) \leq (2+2\epsilon) W_{n} +1 \right)\\ && \geq 1-3\exp\left( -n^{\theta_{clq}}\right) - \exp\left( -\epsilon(2+2\epsilon)W_{n}\log{n}\right) \end{array} $$

(1.4)

$$ \begin{array}{@{}rcl@{}} && \geq 1- 4n^{-\frac{2\epsilon}{\alpha_{1}+\epsilon}} \end{array} $$

(1.5)

for all n ≥ N, where

$$ \theta_{clq} := 2(\alpha_{2} + \eta-\gamma) - \max(\alpha_{1},\alpha_{2}) > 0. $$

(1.6)

In words, the clique number ω(G) is of the order of W_n with high probability, i.e., with probability converging to one as n →∞.

We briefly outline the proof of Theorem 1. To obtain the lower bound in Eq. 1.4, we let 1 − t_L(n) denote the probability of finding a clique of size L in the random graph G. We first obtain a recursive estimate roughly of the form (see Eq. 2.12 of Lemma 6 for a more precise formulation)

$$ t_{L}(n) \leq t_{L-1}(\beta n) + e^{-\theta n^{2}} $$

(1.7)

where β = β_n ∈ (0,1) and θ = θ_n > 0. Using the recursion (1.7) we then find an explicit upper bound of the form $t_{L}(n) \leq e^{-A_{1}} + 2e^{-A_{2}}$ where A₁ = A₁(L, n, p_n) and A₂ = A₂(L, n, p_n) (see Lemma 7 for explicit expressions for A₁ and A₂). Choosing L = (1 − η − α₂)W_n, we then show that both A₁ and A₂ are at least $n^{\theta _{clq}}$ (see proof of Theorem 1 in Section 3).

For the upper bound in Eq. 1.4, we use a union bound and estimate the probability that there exists an open clique of size L for L = (2 + 2𝜖)W_n + 1, to be at most exp (−𝜖(2 + 2𝜖)W_n logn). Combining with the lower bound estimates described in the previous paragraph, we then get Eq. 1.4. To obtain Eq. 1.5 from Eq. 1.4, we use the fact that $p_{n} \geq \frac {1}{n^{\alpha _{1}+\epsilon }}$ for all n large (see Eq. 1.2) and so W_n = log n log(1 p_n) ≥ 1 α₁+𝜖 for all n large. This implies that

$$\epsilon(2+2\epsilon)W_{n}\log{n} \geq \frac{2\epsilon}{\alpha_{1}+\epsilon} \log{n}$$

and so

$$\max\left( \exp\left( -n^{\theta_{clq}}\right), \exp\left( -\epsilon(2+2\epsilon)W_{n}\log{n}\right) \right) \leq n^{-\frac{2\epsilon}{\alpha_{1}+\epsilon}}$$

for all n large. This obtains Eq. 1.5.

1.2 Chromatic Number

Let G = G(n, p_n) be the random graph obtained in the previous subsection. The chromatic number χ(G) is defined as follows. A k −colouring of G is a map h : {1, 2, … , n} → {1, 2, … , k}; i.e., each vertex in G is assigned one of k colours. The k −colouring h is said to be proper if h(v₁) ≠ h(v₂) for v₁, v₂ that are endvertices of an open edge; i.e., no two endvertices of an open edge have the same colour. Using a distinct colour for each of the n vertices of G, we obtain a proper n −colouring. Define

$$ \chi(G) = \min\{k : 1 \leq k \leq n \text { and } G \text{ has a proper }k-\text{colouring}\} $$

to be the chromatic number of G.

Letting α₁, α₂ be as in Eq. 1.2 and W_n be as in Eq. 1.1, we have the following result regarding the chromatic number of G.

Theorem 2.

Suppose {p_n} is such that α₁ < 1, α₂ < 1 2 and 1 − α₂ > max(α₁, α₂). There are positive constants η, γ and c such that

$$ \max(\eta,c) < 1-\alpha_{2}, \alpha_{2} < c(\alpha_{2} + \eta) <1, 2c(\alpha_{2} +\eta - \gamma) > \max(\alpha_{1},2\alpha_{2}) $$

(1.8)

and

$$ \theta_{chr} := 2(\alpha_{2} + \eta - \gamma) - \frac{1}{c}\max(\alpha_{1},\alpha_{2}) > 1. $$

(1.9)

For all 𝜖 > 0 and η, γ, c satisfying (1.8) and (1.9), there is a positive integer N ≥ 1 so that

$$ \begin{array}{@{}rcl@{}} &&\mathbb{P}\left( \frac{n}{(2+2\epsilon)W_{n}+1} \leq \chi(G(n,1-p_{n})) \leq \frac{(1+\epsilon)n}{c(1-\eta-\alpha_{2})W_{n}}\right) \\ && \geq 1-3\exp\left( -\frac{1}{2}n^{c\theta_{chr}}\right) - 2\exp\left( -\epsilon(2+2\epsilon)W_{n}\log{n}\right) \end{array} $$

(1.10)

$$ \begin{array}{@{}rcl@{}} && \geq 1- 4n^{-\frac{2\epsilon}{\alpha_{1}+\epsilon}} \end{array} $$

(1.11)

for all n ≥ N.

Thus the chromatic number χ(G) is of the order of nW_n with high probability. As in Alon and Spencer (2003), we use the estimates in Theorem 1 regarding the clique number and consider the complement graph G(n,1 − p_n) to find upper and lower bounds on the chromatic number (see Lemma 9 in Section 4).

Remark: Because we use recursion (see Lemma 6) to estimate the probability of occurrence of cliques, the information regarding the graph G becomes coarser at each successive step and this reflects in the difference between the upper and lower bounds for the clique number in Theorem 1. Since we use the clique number estimates to bound the chromatic number (see Lemma 9 in Section 4), the corresponding difference appears in the chromatic number bounds (Theorem 2) as well.

1.3 Special Cases

For completeness and illustration, we use our results above to state and provide brief proofs for the special cases where the probability sequence {p_n} belongs to one of the three regimes, sparse, intermediate and dense. For stronger versions of below stated results, we refer to Alon and Spencer (2003) and references therein.

Theorem 3.

• (i) Suppose $p_{n} = \frac {1}{n^{\theta _{1}}}$ for some 0 < θ₁ < 2. For every ξ > 0, there is a positive integer N ≥ 1 so that

  $$ \mathbb{P}\left( \frac{2-\theta_{1}}{2\theta_{1}} -\xi \leq \omega(G(n,p_{n})) \leq \frac{2+\theta_{1}}{\theta_{1}} + \xi\right) \geq 1-4 n^{-\xi} $$

  (1.12)

  for all n ≥ N.

• (ii) Suppose p_n = p ∈ (0, 1) for all n. For every ξ > 0, there is a positive integer N ≥ 1 so that

  $$ \begin{array}{@{}rcl@{}} &&\mathbb{P}\left( \frac{(1-\xi)\log{n}}{\log\left( \frac{1}{p}\right)} \leq \omega(G(n,p_{n})) \leq \frac{(2+\xi)\log{n}}{\log\left( \frac{1}{p}\right)} \right) \\ && \geq 1- 4\exp\left( \frac{-\xi}{\log\left( \frac{1}{p}\right)}(\log{n})^{2}\right) \end{array} $$

  (1.13)

  for all N ≥ N.

• (iii) Suppose $p_{n} = 1-\frac {1}{n^{\theta _{2}}}$ for some 0 < θ₂ < 1. For every ξ > 0, there is a positive integer N ≥ 1 so that

  $$ \begin{array}{@{}rcl@{}} &&\mathbb{P}\left( (1-\theta_{2})(1- \xi)n^{\theta_{2}} \log{n} \leq \omega(G(n,p_{n})) \leq (2+\xi)n^{\theta_{2}}\log{n}\right) \\ && \geq 1- 4\exp\left( -\frac{\xi}{4} n^{\theta_{2}}(\log{n})^{2}\right) \end{array} $$

  (1.14)

  for all n ≥ N.

Using the bounds for the clique number in Theorem 3, we derive bounds for the chromatic number of ER graphs where each edge is independently open with probability r_n, belonging to one of the three regimes sparse, intermediate or dense. As before, we discuss separate cases depending on the asymptotic behaviour of r_n.

Theorem 4.

• (i) Suppose $r_{n} = \frac {1}{n^{\theta _{2}}}$ for some 0 < θ₂ < 1 2. For all ξ > 0, there is a constant N ≥ 1 so that

  $$ \begin{array}{@{}rcl@{}}&&\mathbb{P}\left( (1-\xi)\frac{n^{1-\theta_{2}}}{2\log{n}} \leq \chi(G(n,r_{n})) \leq \frac{2(1+\xi)}{1-2\theta_{2}} \frac{n^{1-\theta_{2}}}{\log{n}} \right) \\ && \geq 1-4\exp\left( -\frac{\xi}{4}n^{\theta_{2}}(\log{n})^{2}\right) \end{array} $$

  (1.15)

  for all n ≥ N.

• (ii) Suppose r_n = p for some constant 0 < p < 1 and for all n. For all ξ > 0, there is a constant N ≥ 1 so that

  $$ \begin{array}{@{}rcl@{}}&&\mathbb{P}\left( (1-\xi)\frac{n\log\left( \frac{1}{1-p}\right)}{2\log{n}} \leq \chi(G(n,r_{n})) \leq 2(1+\xi) \frac{n\log\left( \frac{1}{1-p}\right)}{\log{n}} \right) \\ && \geq 1-4\exp\left( -\frac{\xi}{3\log\left( \frac{1}{1-p}\right)}(\log{n})^{2}\right) \end{array} $$

  (1.16)

  for all n ≥ N.

• (iii) Suppose $r_{n} = 1-\frac {1}{n^{\theta _{1}}}$ for some 0 < θ₁ < 1. For all ξ > 0, there is a constant N ≥ 1 so that

  $$ \begin{array}{@{}rcl@{}}&&\mathbb{P}\left( (1-\xi)\frac{\theta_{1} n}{2+\theta_{1}}\leq \chi(G(n,r_{n})) \leq (1+\xi) \frac{2\theta_{1}n}{1-\theta_{1}} \right) \\ && \geq 1-4n^{-\frac{\xi^{2}}{3\theta_{1}}} \end{array} $$

  (1.17)

  for all n ≥ N.

We remark here that Alon and Spencer (2003) consider the random graph G as a whole and use the extended Janson’s inequality to obtain sharp concentration type estimates for the clique number ω(G) for example, when the edge probability is p_n = 1 2. Using the bounds for the chromatic number in terms of the clique number (see Lemma 9 in Section 4) then results in the property that χ(G) is concentrated around n log ₂n with high probability. Because we use recursion to estimate the probability of occurrence of cliques, this inherently results in a “loss of information” at each successive step and reflects in the differences between our upper and lower bounds for the clique number and correspondingly the chromatic number. Indeed, we compute the chromatic number using the clique number estimates (Lemma 9) analogous to Alon and Spencer (2003) (see Section 4 for more details). For additional results regarding the chromatic number in the sparse regime, we also refer to Bollobás (2001).

The paper is organized as follows. In Section 2, we obtain preliminary estimates used for proving the main Theorems 1 and 2. In Section 3, we prove Theorem 1 and in Section 4, we prove Theorem 1. Finally, in Appendix, we prove Theorems 3 and 4.

2 Preliminary Estimates

We use the following estimates throughout.

Logarithm estimate::

The following logarithmic estimate is used throughout. For 0 < x < 1,

$$ x < -\log(1-x) = \sum\limits_{k\geq 1}\frac{x^{k}}{k} < \sum\limits_{k\geq 1}x^{k} < \frac{x}{1-x}. $$

(2.1)

Binomial Estimate::

Let {X_j}_1≤j≤m be independent Bernoulli random variables with ℙ(X_j = 1) = p_j = 1 − ℙ(X_j = 0) and fix 0 < 𝜖 < 1 6. If T_m = ∑ j= 1mX_j and μ_m = ET_m, then

$$ \mathbb{P}\left( \left|T_{m} - \mu_{m}\right| \geq \mu_{m} \epsilon \right) \leq 2\exp\left( -\frac{\epsilon^{2}}{4}\mu_{m}\right) $$

(2.2)

for all m ≥ 1. For a proof of Eq. 2.2, we refer to Corollary A.1.14, pp. 312 of Alon and Spencer (2003).

The rest of the section is divided into three parts: The first part concerns a technical Lemma (see Lemma 5) that estimates a number δ_n and a decreasing sequence {q_i}_{i≥ 0} both of which occur in the recursive estimate of the second part. In the second part, we estimate the probability t_L(q_i) of finding a L −open clique (i.e., an open clique formed by L vertices) from among a total of q_i vertices, in terms of t_L− 1(q_i+ 1) (see estimate (2.12) in Lemma 6). The final part uses the recursion estimate (2.12) to explicitly compute t_L(q₀) for arbitrary q₀ and L (see Lemma 7).

In Sections 3 and 4, we use the estimate for t_L(q₀) computed in Lemma 7 with appropriately chosen values of L = L_n and q₀ = q₀(n) to prove Theorems 1 and 2, respectively.

2.1 A Technical Lemma

In this subsection, we define and estimate certain quantities that are used throughout in the proofs of the main theorems. Let 0 < 𝜖 < 1 6 and let M = M(𝜖) ≥ 2 be large such that

$$ \frac{1+\epsilon}{1-\frac{1+\epsilon}{M}} < 1+2\epsilon. $$

(2.3)

Fixing such an M, we let 𝜖₁ = 𝜖₁(𝜖, M) ≤ 𝜖 be small so that

$$ \frac{\log\left( \frac{1}{1-\epsilon_{1}}\right)}{\log\left( \frac{M}{M-1}\right)} \leq \epsilon. $$

(2.4)

For n ≥ 1, we now set

$$ \delta_{n} := \left\{ \begin{array}{cc} \epsilon_{1} p_{n} & \text{ if } p_{n} < 1- \frac{1}{M}\\ \epsilon(1-p_{n}) & \text{ if } p_{n} \geq 1-\frac{1}{M}. \end{array} \right. $$

(2.5)

For a positive integer q let q₀ = q and for i ≥ 1, let

$$ q_{i} = q_{i}(n) := \lfloor(p_{n}-\delta_{n})(q_{i-1}-1)\rfloor $$

(2.6)

be the largest integer less than or equal to (p_n − δ_n)(q_i− 1 − 1).

In the next subsection, we see that the number δ_n and the numbers {q_i} both occur in the main recursive estimate used in the proof of Theorem 1. Indeed, the quantity δ_n occurs in the exponent of a term in Eq. 2.12 of Lemma 6 below and is a part of an estimate that relates the probability t_L(q_i) of finding an L −open clique among q_i vertices, in terms of t_L− 1(q_i+ 1). For convenience, we therefore record properties of δ_n and the numbers of {q_i} for future use. We recall from Eq. 1.1 that W_n = log n log(1 p_n).

Lemma 5.

For any n ≥ 2, the difference p_n − δ_n > 0 and there is a constant K ≥ 1 such that for all n ≥ K,

$$ W_{n} \leq \left\{ \begin{array}{cc} \frac{\log{n}}{\log\left( \frac{M}{M-1}\right)} & \text{ if }p_{n} < 1-\frac{1}{M} \\ &\\ n^{\alpha_{2}+\epsilon} \log{n} & \text{ if } p_{n} \geq 1-\frac{1}{M}, \end{array} \right. $$

(2.7)

and

$$ R_{n} := \frac{\log\left( \frac{1}{p_{n}-\delta_{n}}\right)}{\log\left( \frac{1}{p_{n}}\right)} < 1+2\epsilon. $$

(2.8)

The numbers {q_i} satisfy the following properties. For i ≥ 1,

$$ (p_{n}-\delta_{n}) (q_{i-1} -1 ) -1 \leq q_{i} \leq (p_{n} -\delta_{n}) q_{i-1} \leq q_{i-1} \leq q $$

(2.9)

and

$$ v_{i} := (p_{n}-\delta_{n})^{i}q - \frac{2}{1-p_{n}+\delta_{n}} \leq q_{i} \leq (p_{n}-\delta_{n})^{i}q. $$

(2.10)

(Proof of Eqs. 2.7 and 2.8 in Lemma 5).

If p_n < 1 − 1 M then δ_n = 𝜖₁p_n and so p_n − δ_n = (1 − 𝜖₁)p_n > 0. Also log (1p_n) ≥ log (MM− 1) . Consequently

$$ W_{n}= \frac{\log{n}}{\log\left( \frac{1}{p_{n}}\right)} \leq \frac{\log{n}}{\log\left( \frac{M}{M-1}\right)} \text{ and }R_{n} \leq 1 + \frac{\log\left( \frac{1}{1-\epsilon_{1}}\right)}{\log\left( \frac{M}{M-1}\right)} \leq 1+\epsilon, $$

by the choice of 𝜖₁ in Eq. 2.4.

If p_n ≥ 1 − 1 M, then δ_n = 𝜖(1 − p_n) and so

$$p_{n} - \delta_{n} = p_{n}(1+\epsilon) - \epsilon \geq \left( 1-\frac{1}{M}\right)(1+\epsilon)-\epsilon \geq \frac{1+\epsilon}{1+2\epsilon},$$

using Eq. 2.4. Moreover using the bound − log(1 − x) > x (see Eq. 2.1) with x = 1 − p_n we get

$$\log\left( \frac{1}{p_{n}}\right) = -\log(1-(1-p_{n})) > 1-p_{n} \geq \frac{1}{n^{\alpha_{2}+\epsilon}}$$

for all n large, where α₂ = limsup_n log(1 1−p_n) log n is as defined in Eq. 1.2. This means that $W_{n} = \frac {\log {n}}{\log \left (\frac {1}{p_{n}}\right )} \leq n^{\alpha _{2}+\epsilon } \log {n},$ giving Eq. 2.7.

To prove (2.8), we use the fact that (1 + 𝜖)(1 − p_n) ≤ 1+𝜖 M < 1, since M ≥ 2 and 0 < 𝜖 < 1. Therefore using the upper bound − log(1 − x) < x 1−x from Eq. 2.1 with x = (1 + 𝜖)(1 − p_n) = 1 − (p_n − δ_n), we have that

$$ -\log(p_{n} - \delta_{n}) \leq \frac{(1+\epsilon)(1-p_{n})}{1-(1+\epsilon)(1-p_{n})} \leq \frac{(1+\epsilon)(1-p_{n})}{1-\frac{1+\epsilon}{M}}. $$

Similarly using the lower bound estimate − log(1 − x) > x from Eq. 2.1, we have − logp_n = −log(1 − (1 − p_n)) > 1 − p_n. Thus

$$R_{n} = \frac{\log\left( \frac{1}{p_{n}-\delta_{n}}\right)}{\log\left( \frac{1}{p_{n}}\right)} \leq \frac{1+\epsilon}{1-\frac{1+\epsilon}{M}} \leq 1+2\epsilon, $$

by choice of M in Eq. 2.3. This proves (2.8). □

(Proof of Eqs. 2.9 and 2.10 in Lemma 5).

The relation (2.9) is obtained using the property x − 1 ≤⌊x⌋≤ x for any x > 0. Set Δ = p_n − δ_n ∈ (0,1) and apply the upper bound in Eq. 2.9 recursively, to get q_i ≤Δⁱq₀ = Δⁱq. This proves the upper bound in Eq. 2.10. For the lower bound we again proceed iteratively and first obtain for i ≥ 2 that q_i ≥Δ(q_i− 1 − 1) − 1 = Δq_i− 1 − (1 + Δ). Continuing iteratively we obtain q_i ≥Δⁱq₀ − (1 + Δ)∑ j= 0iΔ^j− 1. Since Δ < 1, the sum ∑ j= 0iΔ^j ≤ 1 1−Δ and so q_i ≥Δⁱq₀ − 1+Δ 1−Δ ≥Δⁱq − 2 1−Δ, since Δ ∈ (0,1). This proves (2.10). □

2.2 Recursion Estimate

Recall that the random graph G = G(n, p_n) is said to have an open L −clique if there exists a subset S ⊂ {1, 2, … , n} such that #S = L and for any u, v ∈ S, the edge e(u, v) is open (see statement prior to Eq. 1.1). For integer 2 ≤ q ≤ n, let S_q := {1, 2, … , q} and let G(S_q) be the induced subgraph of G = G(n, p_n), with vertex set S_q. For integer L ≥ 2, let B_L(S_q) denote the event that the random subgraph G(S_q) contains an open L −clique and set

$$ t_{L}(q) := \mathbb{P}({B^{c}_{L}}(S_{q})). $$

(2.11)

By definition t_L(q) = 0 if L > q.

In this subsection, we obtain a recursive estimate for the probability t_L(q) for arbitrary L and q in terms of t_L− 1(q₁) where q₁ is as defined in Eq. 2.6 with i = 1. In the next subsection, we use the recurrence relation obtained below to obtain an explicit estimate for t_L(q).

Lemma 6.

Fix 0 < 𝜖 < 1 6 and let 𝜖₁ and δ_n be as defined in Eqs. 2.4and 2.5, respectively. There exists a constant N₀ = N₀(𝜖) such that the following holds for all n ≥ N₀ : If q, L ≥ 2 are such that L − 1 ≥ 2 and q₁ = ⌊(p_n − δ_n)(q − 1)⌋ ≥ 2 (see Eq. 2.6) then

$$ \begin{array}{@{}rcl@{}} t_{L}(q) \leq qt_{L-1}(q_{1}) + \exp\left( -\frac{\epsilon_{1} \delta_{n}}{16}q^{2}\right). \end{array} $$

(2.12)

In Lemma 7 stated below, we use recursion to estimate the first term in Eq. 2.12 and obtain explicit estimates for t_L(q) (see proof of Lemma 7).

(Proof of Lemma 6).

Recall from Eq. 2.5 that δ_n ∈{𝜖₁p_n,(1 − 𝜖)p_n}. For simplicity, we write p = p_n, δ = δ_n and first prove that Eq. 2.12 is satisfied with δ = p𝜖₁.

If N_e denotes the number of open edges in the random graph G(S_q), then EN_e = p(q2). Fixing 0 < 𝜖 < 1 6, setting δ = p𝜖₁ and applying the binomial estimate (2.2) with T_m = N_e then gives

$$ \mathbb{P}\left( N_{e} \geq p(1-\epsilon_{1}) {q \choose 2}\right) \geq 1- \exp\left( -\frac{\epsilon_{1} \delta}{4} {q \choose 2}\right) \geq 1- \exp\left( -\frac{\epsilon_{1} \delta}{16} q^{2}\right) $$

(2.13)

since 14(q2) ≥ q² 16 for all q ≥ 2.

We now write ℙ(BLc(S_q)) = I₁ + I₂, where

$$ I_{1} := \mathbb{P}\left( {B^{c}_{L}}(S_{q}) \bigcap \left\{N_{e} \geq (p-\delta) {q \choose 2}\right\}\right) $$

(2.14)

and I₂ := ℙ (BLc(S_q)⋂ {N_e < (p − δ)(q2)}) is bounded above as

$$ I_{2} \leq \mathbb{P}\left( N_{e} < (p-\delta) {q \choose 2}\right) \leq \exp\left( -\frac{\epsilon_{1} \delta}{16}q^{2}\right), $$

(2.15)

by Eq. 2.13.

It remains to estimate I₁. Suppose that the event N_e ≥ (p − δ)(q2) occurs. If d(v) denotes the degree of vertex v ∈ S_q in the random graph G(S_q), then ∑ _1≤v≤qd(v) = 2N_e ≥ (p − δ)q(q − 1) and so there exists a vertex w such that d(w) ≥ (p − δ)(q − 1) ≥ q₁, where q₁ is as defined in the statement of the Lemma. Thus

$$ \begin{array}{@{}rcl@{}} I_{1} &\leq& \mathbb{P}\left( {B^{c}_{L}}(S_{q}) \bigcap \left( \bigcup_{1 \leq z \leq q}\left\{d(z) \geq q_{1}\right\}\right)\right)\\ &\leq& \sum\limits_{1 \leq z \leq q} \mathbb{P}\left( {B^{c}_{L}}(S_{q}) \bigcap \left\{d(z) \geq q_{1}\right\}\right). \end{array} $$

(2.16)

If N(z) = N(z, G(S_q)) is the set of neighbours of z in the random graph G(S_q), then

$$ \mathbb{P}\left( {B^{c}_{L}}(S_{q}) \bigcap \left\{d(z) \geq q_{1}\right\}\right) = \sum\limits_{S \subseteq S_{q}} \mathbb{P}\left( {B^{c}_{L}}(S_{q}) \bigcap \left\{N(z) = S \right\}\right), $$

(2.17)

where the summation is over all subsets S of S_q such that #S ≥ q₁ and z∉S.

Suppose now that the event BLc(S_q)⋂ {N(z) = S} occurs for some fixed set S ⊆ S_q. We recall that since BLc(S_q) occurs, there is no open L −clique in the random graph G(S_q) with vertex set S_q. This necessarily means that there is no open (L − 1) −clique in the random induced subgraph of G(S_q) formed by the vertices of S; i.e., the event BL− 1c(S) occurs. This is because each vertex of S is connected to z by an open edge. Therefore ℙ (BLc(S_q) ⋂ {N(z) = S}) is bounded above by

$$ \mathbb{P}\left( B^{c}_{L-1}(S) \cap \{N(z) = S\} \right) = \mathbb{P}\left( B^{c}_{L-1}(S)\right)\mathbb{P}\left( N(z) = S\right), $$

(2.18)

where the final equality is true since the event {N(z) = S} depends only on the state of edges containing z as an endvertex. On the other hand, the event BL− 1c(S) depends only on the state of edges having both their endvertices in S. Since the set S does not contain the vertex z (see Eq. 2.17), the events {N(z) = S} and BL− 1c(S) are independent.

To obtain the desired recursion (2.12) using Eq. 2.18, let T denote the set of the q₁ least indices in S, where q₁ ≤ #S is as defined in the statement of the Lemma. Since T ⊆ S, the events BL− 1c(S) ⊆ BL− 1c(T); i.e., there is no open (L − 1) −clique in the random induced subgraph formed by the vertices of T. From Eq. 2.18, we then get that ℙ (BLc(S_q)⋂ {N(z) = S}) is bounded above by

$$ \mathbb{P}\left( N(z) = S\right)\mathbb{P}\left( B^{c}_{L-1}(T)\right) = \mathbb{P}\left( N(z) = S\right)t_{L-1}(q_{1}), $$

(2.19)

since #T = q₁ (see Eq. 2.11).

Substituting (2.19) into (2.17) we get that ℙ (BLc(S_q)⋂ {N(z) ≥ q₁}) is bounded above by

$$ \sum\limits_{S \subseteq S_{q}: \#S \geq q_{1}, z \notin S} \mathbb{P}\left( N(z) = S\right)t_{L-1}(q_{1}) = \mathbb{P}\left( d(z) \geq q_{1}\right) t_{L-1}(q_{1}) \leq t_{L-1}(q_{1}), $$

(2.20)

where the equality (2.20) is true since the events {N(z) = S} are disjoint for distinct S. Substituting (2.20) into (2.16) gives

$$I_{1} \leq \sum\limits_{1 \leq z \leq q} t_{L-1}(q_{1}) = q t_{L-1}(q_{1}).$$

Using this estimate for I₁ and Eq. 2.15 we get

$$\mathbb{P}({B^{c}_{L}}(S_{q})) \leq qt_{L-1}(q_{1}) + \exp\left( -\frac{\epsilon_{1} \delta}{16}q^{2}\right).$$

This proves (2.12) for δ = p𝜖₁.

Suppose now that δ = 𝜖(1 − p). Recalling that N_e denotes the number of open edges in the random graph G(S_q) (see the first paragraph of this proof), we let W_e =(q2) − N_e denote the number of closed edges so that EW_e = (1 − p)(q2). If W_e ≤ (1 − p)(1 + 𝜖)(q2), then W_e − EW_e ≤ 𝜖 EW_e. Applying the binomial estimate (2.2) with T_m = W_e therefore gives that ℙ (W_e ≤ (1 − p)(1 + 𝜖)(q2)) is bounded below by

$$ 1- \exp\left( -\frac{\epsilon^{2}}{4}\mathbb{E}W_{e}\right) = 1- \exp\left( -\frac{\epsilon^{2}}{4}(1-p) {q \choose 2}\right) = 1- \exp\left( -\frac{\epsilon \delta}{4} {q \choose 2}\right) $$

(2.21)

for all q ≥ 2, since δ = 𝜖(1 − p). Moreover,

$$\left\{W_{e} \leq (1-p)(1+\epsilon) {q \choose 2} \right\} = \left\{N_{e} \geq (p-\delta) {q \choose 2} \right\}$$

and so we again obtain (2.13) with 𝜖 instead of 𝜖₁. Arguing as before, we then get ℙ(BLc(S_q)) ≤ qt_L− 1(q₁) + exp (−𝜖δ16q²) . Since 𝜖₁ ≤ 𝜖 (see Eq. 2.4), this proves (2.12). □

2.3 Small Cliques Estimate

We now use the recursion obtained in the Lemma 6 iteratively, to obtain an explicit estimate for the probability t_L(q).

Lemma 7.

Fix 0 < 𝜖 < 1 6 and let 𝜖₁, δ_n be as defined in Eqs. 2.4and 2.5, respectively. There is a constant N₀ = N₀(𝜖) ≥ 1 so that the following holds for all n ≥ N₀ : If q = q_n and L = L_n are such that

$$ v_{L} = (p_{n} - \delta_{n})^{L}q - \frac{2}{1-p_{n}+\delta_{n}} \geq 2, $$

(2.22)

then $t_{L}(q) \leq e^{-A_{1}} + 2e^{-A_{2}}$ where

$$A_{1} := \frac{p_{n}}{4} {v^{2}_{L}} - L\log{q} \text{ and } A_{2} := \frac{\epsilon_{1} \delta_{n}}{16} {v^{2}_{L}} - L\log{q}.$$

We recall that v_L is as defined in Eq. 2.10. In the proof of Theorem 1, we use a auxiliary lemma (Lemma 8) to first check that the condition (2.22) holds and then use Lemma 7 to obtain lower bounds on the clique number.

(Proof of Lemma 7).

For simplicity, let p = p_n, δ = δ_n and r(q) := exp (−𝜖₁δ16 q²) . Recalling the definition of {q_i} in Eq. 2.6 and applying the recursion (2.12) twice we get t_L(q) ≤ qt_L− 1(q₁) + r(q) ≤ q(q₁t_L− 2(q₂) + r(q₁)) + r(q) provided L − 2 and q₂ are both at least 2. Since q₂ ≤ q₁ ≤ q₀ = q, (see Eq. 2.9), we further get t_L(q) ≤ q²t_L− 2(q₂) + qr(q₁) + r(q). Proceeding iteratively, we therefore get that

$$ t_{L}(q) \leq q^{L-2}t_{2}(q_{L-2}) + \sum\limits_{j=0}^{L-3}q^{j}r(q_{j}), $$

(2.23)

provided q_L− 2 ≥ 2.

Since q_L− 2 ≥ q_L ≥ v_L (see Esqs. 2.9 and 2.10), it is enough to prove the estimate for t_L(q) in the Lemma from Eq. 2.23, assuming that v_L ≥ 2. We now show that if v_L ≥ 2, then the first term in Eq. 2.23 is at most $e^{-A_{1}}$ and the second summation in Eq. 2.23 is at most $2e^{-A_{2}},$ where A₁ and A₂ are as in the statement of the Lemma. This proves the Lemma. To estimate the summation term in Eq. 2.23, we use q_j ≥ q_L ≥ v_L for 1 ≤ j ≤ L − 1 (see Eqs. 2.9 and 2.10) to get that r(q_j) ≤ r(v_L). Thus

$$ \sum\limits_{j=0}^{L-3}q^{j}r(q_{j}) \leq \left( \sum\limits_{j=0}^{L-3}q^{j}\right) r(v_{L}) = \frac{q^{L-2}-1}{q-1} r(v_{L}) \leq 2q^{L-3} r(v_{L}) \leq 2q^{L}r(v_{L}), $$

(2.24)

where the second inequality in Eq. 2.24 follows from the fact that q^L− 2− 1q− 1 ≤ 2q^L− 3 for all q ≥ 2. Since the final term of Eq. 2.24 is in fact $2e^{-A_{2}},$ we have bounded the summation in Eq. 2.23.

To bound the first term in Eqs. 2.23, we use the estimate

$$ t_{2}(q_{L-2}) = (1-p)^{q_{L-2} \choose 2} \leq \exp\left( -p{q_{L-2} \choose 2}\right) \leq \exp\left( -p{v_{L} \choose 2}\right), $$

(2.25)

where the first equality in Eq. 2.25 is true since there is no open 2 −clique among a set of vertices if and only if all the edges between the vertices are closed. The final inequality in Eq. 2.25 follows from the fact that q_L− 2 ≥ q_L ≥ v_L (see Eqas. 2.9 and 2.10). Since (v_L 2) ≥ vL2 4 for all v_L ≥ 2, we get from Eq. 2.25 that the first term in Eq. 2.23 is at most $e^{-A_{1}},$ proving the Lemma. □

3 Proof of Theorem 1

We use the small cliques estimate in Lemma 7 with appropriately chosen value of L = L_n, to obtain the lower bound on the clique number. For the upper bound on the clique number, we use the union bound to estimate the probability that there an open clique of size L, chosen sufficiently large.

We begin with the proof of the lower bound on the clique number. To apply the small cliques estimate in Lemma 7, we first state and prove an auxiliary result (Lemma 8 below) that describes the feasibility of using Lemma 7. Let η, γ > 0 and 0 < c ≤ 1 be constants such that

$$ \alpha_{2} < c(\eta+\alpha_{2}) < 1 \text{ and } 2c(\alpha_{2} + \eta-\gamma)> \max(\alpha_{1},2\alpha_{2}). $$

(3.1)

For c = 1, this corresponds to the conditions mentioned in Eq. 1.3 of the statement of Theorem 1. To see that are constants η, γ and c satisfying (3.1), we recall that α₁ < 2 and α₂ < 1. Therefore 2 > max(α₁,2α₂) and choosing α₂ + η₀ and c₀ close enough to one and γ₀ close enough to zero, we get that Eq. 3.1 is satisfied with γ₀, η₀ and c₀. Arguing similarly, we also have that there are constants η and γ such that Eq. 3.1 holds with c = 1.

For future use, we perform the analysis below for a general 0 < c ≤ 1. We recall the definition of 𝜖, 𝜖₁ and δ_n prior to Eq. 2.5 and the term W_n = log n log(1 p_n) from Eq. 1.1. We now set

$$ L_{n} = (1-\eta - \alpha_{2}) \frac{\log(n^{c})}{\log\left( \frac{1}{p_{n}}\right)} = c(1-\eta - \alpha_{2}) W_{n} $$

(3.2)

and show that the quantities $v_{L_{n}}, A_{1}$ and A₂ defined in Lemma 7 satisfy the following estimates.

Lemma 8.

There are constants 𝜖 > 0 small and K = K(𝜖) ≥ 1 large such that for all n ≥ K

$$ v_{L_{n}} \geq n^{c(\alpha_{2} + \eta -3\epsilon)}, A_{1} \geq n^{2c(\alpha_{2} + \eta - \gamma)-\alpha_{1}} \text{ and } A_{2} \geq n^{2c(\alpha_{2} + \eta - \gamma)-\max(\alpha_{1},\alpha_{2})}. $$

(3.3)

The first condition in Eq. 3.3 in the above Lemma implies that condition (2.22) holds for all large n and therefore ensures the feasibility of using the small cliques estimate Lemma 7. Below, in the proof of Theorem 1, we use the estimates in Eq. 3.3 with c = 1 together with Lemma 7, to get the following lower bound for ω(G(n, p_n)) :

$$ \mathbb{P}(\omega(G(n,p_{n})) \geq (1-\eta-\alpha_{2})W_{n}) \geq 1-\exp(-n^{\theta_{clq}}), $$

(3.4)

where θ_clq = 2(α₂ + η − γ) − max(α₁, α₂) is as defined in Eq. 1.6.

(Proof of Lemma 8).

Let 0 < 𝜖 < 1 6 be arbitrary but fixed. We first estimate $v_{L_{n}}$ by writing

$$ v_{L_{n}} = \exp\left( L_{n}\log(p_{n}-\delta_{n}) + c\log{n}\right) - \frac{2}{1-p_{n}+\delta_{n}} $$

(3.5)

(see Lemma 7 for the expression for v_L) and use Eq. 2.8 (which states that log(p_n−δ_n) log p_n < 1 + 2𝜖) and the fact that L_n logp_n < 0 to get

$$ L_{n}\log(p_{n}-\delta_{n}) \geq (1+2\epsilon) L_{n} \log{p_{n}} = -(1+2\epsilon)(1-\eta-\alpha_{2})c\log{n}, $$

(3.6)

by the definition of L_n in Eq. 3.2. Thus

$$ \begin{array}{@{}rcl@{}} L_{n}\log(p_{n}-\delta_{n}) + c\log{n} &\geq& \left( \alpha_{2} + \eta - 2\epsilon(1-\eta -\alpha_{2})\right)c\log{n} \\ &\geq& (\alpha_{2} + \eta - 3\epsilon)c\log{n} \end{array} $$

(3.7)

for all n large and so the exponent term in the expression for $v_{L_{n}}$ in Eq. 3.5 is at least $n^{c(\alpha _{2}+ \eta -3\epsilon )}.$

To evaluate the term 11−p_n+δ_n in Eq. 3.5, we consider two cases depending on whether δ_n = 𝜖₁p_n or δ_n = 𝜖(1 − p_n) (see Eq. 2.5). If δ_n = 𝜖₁p_n, then

$$p_{n}-\delta_{n} = p_{n}(1-\epsilon_{1}) \leq 1-\epsilon_{1}$$

and so 11−p_n+δ_n ≤ 1 𝜖₁ . If δ_n = 𝜖(1 − p_n), then

$$1-p_{n}+\delta_{n} = (1+\epsilon)(1-p_{n}) \geq (1+\epsilon)\frac{1}{n^{\alpha_{2}+\epsilon}}$$

for all n large, by definition of α₂ = limsup_n log(1 1−p_n) log n in Eq. 1.2. In any case, $\frac {1}{1-p_{n}+\delta _{n}} \leq \frac {n^{\alpha _{2}+\epsilon }}{1+\epsilon }$ for all n large and so combining with the estimate (3.7) obtained in the previous paragraph we get that

$$ v_{L_{n}} \geq n^{c(\alpha_{2} + \eta - 2\epsilon)} - \frac{2n^{\alpha_{2}+\epsilon}}{1+\epsilon} $$

for all n large. Using the fact that c(α₂ + η) > α₂ (see Eq. 3.1), we choose 𝜖 > 0 small so that

$$c(\alpha_{2} + \eta -2\epsilon) > c(\alpha_{2} + \eta - 3\epsilon) > \alpha_{2} + \epsilon.$$

Fixing such an 𝜖, we get $v_{L_{n}} \geq n^{c(\alpha _{2} + \eta - 3\epsilon )}$ for all n large, proving the estimate for $v_{L_{n}}$ in Eq. 3.3.

To estimate A₁ and A₂, we consider two separate cases depending on whether p_n < 1 − 1 M and p_n ≥ 1 − 1 M. If p_n < 1 − 1 M, then δ_n = 𝜖₁p_n (see the definition of δ_n in Eq. 2.5). From the estimate for W_n in Eq. 2.7 we have L_n ≤ W_n ≤ log n log(MM− 1) . Since α₁ = limsup_n log(1 p_n) log n < 1 (see Eq. 1.2), we have that $p_{n} \geq \frac {1}{n^{\alpha _{1}+\epsilon }}$ for all n large. Together with the estimate for $v_{L_{n}}$ obtained above in Eq. 3.3, we therefore get that

$$ A_{1} = \frac{p_{n}}{4}v_{L_{n}}^{2} -L_{n} \log{n} \geq \frac{1}{4n^{\alpha_{1}+\epsilon}}n^{2c(\alpha_{2} + \eta - 3\epsilon)} - \frac{(\log{n})^{2}}{\log\left( \frac{M}{M-1}\right)} , $$

(3.8)

for all n large. Using the condition (3.1) and choosing 𝜖 > 0 smaller if necessary, we have that 2c(α₂ + η − 3𝜖) − (α₁ + 𝜖) > 2c(α₂ + η − γ) − α₁ > 0. Thus $A_{1} \geq n^{2c(\alpha _{2} + \eta - \gamma ) - \alpha _{1}}$ and since δ_n = 𝜖₁p_n, an analogous analysis holds for A₂.

Suppose now that p_n ≥ 1 − 1 M. From Eq. 2.5 we have δ_n = 𝜖(1 − p_n) and from Eq. 2.7 we have that $L_{n} \leq W_{n} \leq n^{\alpha _{2} + \epsilon } \log {n}.$ Substituting into the expression for A₁ (see Eq. 3.8) we get

$$ A_{1} \geq \frac{1}{4}\left( 1-\frac{1}{M}\right)n^{2c(\alpha_{2} + \eta - 3\epsilon)} - n^{\alpha_{2}+\epsilon}(\log{n})^{2} \geq n^{2c(\alpha_{2} + \eta - \gamma)}, $$

for all n large, provided we choose 𝜖 > 0 smaller if necessary so that

$$2c(\alpha_{2}+\eta - 3\epsilon) > 2c(\alpha_{2}+\eta-\gamma) > \alpha_{2} + \epsilon.$$

This is possible by the conditions on α₂, η and c in Eq. 3.1.

To estimate A₂, we use α₂ = limsup_n log(1 1−p_n) log n < 1 (see Eq. 1.2) to get that $\delta _{n} = \epsilon (1-p_{n}) \geq \frac {\epsilon }{n^{\alpha _{2}+ \epsilon }}$ for all n large. Thus

$$A_{2} = \frac{\epsilon_{1}}{16}\delta_{n} v_{L_{n}}^{2} -L_{n} \log{n} \geq \frac{\epsilon_{1}}{16} \frac{\epsilon}{n^{\alpha_{2}+ \epsilon}} n^{2c(\alpha_{2} + \eta - 3\epsilon)} - n^{\alpha_{2}+\epsilon}(\log{n})^{2}.$$

As before, we use Eq. 3.1 and choose 𝜖 > 0 smaller if necessary to get that

$$2c(\alpha_{2} + \eta -3\epsilon) - (\alpha_{2}+\epsilon) > 2c(\alpha_{2} + \eta - \gamma) - \alpha_{2} > \alpha_{2} + \epsilon.$$

This implies that $A_{2} \geq n^{2c(\alpha _{2} + \eta - \gamma ) - \alpha _{2}}$ for all n large, proving the Lemma. □

(Proof of Theorem 1).

To prove the lower bound for ω(G) in Eq. 3.4, we set c = 1 in Eq. 3.1 and get from Lemma 8 that

$$\min(A_{1},A_{2}) \geq n^{2(\alpha_{2} + \eta - \gamma) - \max(\alpha_{1},\alpha_{2})} = n^{\theta_{clq}},$$

where θ_clq is as defined in Eq. 1.6. Moreover, from Eq. 3.3 we get $v_{L_{n}} \geq 2$ for all n large and so Lemma 7 is applicable. Thus $t_{L_{n}}(n) \leq e^{-A_{1}} + 2e^{-A_{2}} \leq 3\exp \left (-n^{\theta _{clq}}\right ).$ In other words, with probability at least $1-3\exp \left (-n^{\theta _{clq}}\right ),$ the random graph G contains an open clique of size L_n, proving the lower bound (3.4) for ω(G(n, p_n)).

To obtain the upper bound for ω(G(n, p_n)), we prove below that for any positive sequence {H_n}, the term

$$ \mathbb{P}\left( \omega(G(n,p_{n})) \leq H_{n}\right) \geq 1-\exp\left( -f_{n}H_{n}\right) $$

(3.9)

for all n ≥ 2, where f_n := (H_n− 1) 2 log (1p_n) − logn. Setting H_n = (2 + 2𝜖)W_n + 1 ≥ (2 + 2𝜖)W_n, where W_n = log n log(1 p_n) as defined in Eq. 1.1, we get that f_n = 𝜖 logn. From Eq. 3.9, we then get the desired upper bound (1.4). As argued in the discussion following Theorem 1, the estimate (1.5) follows from Eq. 1.4.

To prove (3.9) we use the fact that if there is an open L −clique in G with L = H_n, then some set T with #T = L has the property that every vertex in T is connected to every other vertex in T by an open edge. The number of edges with both endvertices in T is (L2) and the number of possible choices for T is (nL). Therefore,

$$ \begin{array}{@{}rcl@{}} \mathbb{P}(\omega(G(n,p_{n})) \geq H_{n}) &\leq& {n \choose L} p_{n}^{L \choose 2} \\ &\leq& n^{L} p_{n}^{L \choose 2} \\ &=& \exp\left( -L \left( \left( \frac{L-1}{2}\right)\log\left( \frac{1}{p_{n}}\right) - \log{n}\right)\right) \\ &=& e^{-f_{n} H_{n}}, \end{array} $$

since L = H_n. This proves (3.9). □

4 Proof of Theorem 2

We begin with the following definition:

Independence Number of a Graph

We recall that the graph G = G(n, p_n) is the random subgraph of K_n obtained by allowing each edge to be independently open with probability p_n. Also ω(G) is the size of the largest clique in G. The independence number α(G) is defined as follows: α(G) = h if and only if there is a set of h vertices, none of which have an open edge between them and every set of h + 1 vertices have an open edge between them in G.

Let G¯ = (V¯, E¯) denote the complement of the graph G obtained by flipping the states of all edges in G; i.e., all open edges in G are closed in G¯ and all closed edges in G are open in G¯. We use the following Lemma (Alon and Spencer (2003)) in the proof of Theorem 2.

Lemma 9.

(a1) The independence number α (G) = ω(G¯) and so the chromatic number

$$ \chi(G) \geq \frac{n}{\alpha(G)} = \frac{n}{\omega(\overline{G})}. $$

(4.1)

(a2) Suppose for some integer 1 ≤ m ≤ n, every set of m vertices in the complement graph G¯ contains an open clique of size L. We then have

$$ \chi(G) \leq \frac{n}{L} + m. $$

(4.2)

(Proof of Theorem 2).

As in Section 1, let G = G(n, p_n) be the random subgraph of the complete graph K_n where each edge is open with probability p_n. We recall that ω(G) is the clique number of G as defined prior to Theorem 1. The lower bound in Eq. 1.11 then follows from property (a1) in Lemma 9 and the upper bound for the clique number ω(G(n, p_n)) in Eq. 1.5, since the random graph G¯(n,1 − p_n) has the same distribution as the random graph G(n, p_n). Indeed, we recall from Eq. 3.9 that

$$ \mathbb{P}\left( \omega(G(n,p_{n})) \leq (2+2\epsilon) W_{n} +1\right) \geq 1-\exp\left( -(2+2\epsilon)\epsilon W_{n} \log{n}\right) $$

(4.3)

where W_n = log n log(1 p_n) is as defined in Eq. 1.1. Using Eq. 4.3 in Eq. 4.1 we therefore get

$$\mathbb{P}\left( \chi(G(n,1-p_{n})) \geq \frac{n}{(2+2\epsilon)W_{n}+ 1}\right) \geq 1- \exp\left( -(2+2\epsilon)\epsilon W_{n} \log{n}\right).$$

For the upper bound in Eq. 1.11, we use property (a2) with m = n^c, where c satisfies the conditions in the statement of Theorem 2. For that we first see that there are positive constants η, γ and c such that Eq. 1.8 holds; i.e.,

$$ \max(\eta,c) < 1-\alpha_{2}, \alpha_{2} < c(\alpha_{2} + \eta) <1 \text{ and } 2c(\alpha_{2} +\eta - \gamma) > \max(\alpha_{1},2\alpha_{2}). $$

(4.4)

Indeed, recalling that α₁ < 1 and α₂ < 1 2 we have that 2(1 − α₂) > max(α₁,2α₂). Therefore choosing c₀, α₂ + η₀ and γ₀, close enough to 1 − α₂, one and zero, respectively, we get that Eq. 4.4 holds. To see that Eq. 1.9 also holds; i.e.,

$$ \theta_{chr} = 2(\alpha_{2} + \eta - \gamma) - \frac{1}{c}\max(\alpha_{1},\alpha_{2}) > 1, $$

(4.5)

we recall that 1 − α₂ > max(α₁, α₂). Therefore 2 − 1 1−α₂ max(α₁, α₂) > 1. Choosing c₀, α₂ + η₀ and γ₀ closer to 1 − α₂, one and zero, respectively, if necessary, we get that Eq. 4.5 also holds.

We now let m = n^c where c satisfies (4.4) and let _m be the set of subsets of size m in {1,2, … , n}. For a set S ∈_m and integer L ≥ 2, we recall from Eq. 2.11 that B_L(S) denotes the event that the random induced subgraph of G(n, p_n) with vertex set S contains an open L −clique. We set

$$L := (1-\eta-\alpha_{2})\frac{\log{m}}{\log\left( \frac{1}{p_{n}}\right)} = c(1-\eta-\alpha_{2})W_{n},$$

by Eq. 1.1 and the fact that m = n^c. Also from our choices of c, γ and η in Eqs. 4.4 and 4.5, the conditions in Eq. 3.1 hold. Therefore the estimates for A₁ and A₂ Lemma 8 hold and we get

$$ \begin{array}{@{}rcl@{}} \mathbb{P}({B^{c}_{L}}(S)) &\leq& e^{-A_{1}} + 2e^{-A_{2}} \leq 3\exp\left( -n^{2c(\alpha_{2}+\eta-\gamma)-\max(\alpha_{1},\alpha_{2})}\right)\\ &=& 3\exp\left( -m^{\theta_{chr}}\right), \end{array} $$

(4.6)

where θ_chr > 1, by Eq. 4.5.

If $F_{n} = \bigcap _{S \in \mathcal {S}_{m}}B_{L}(S)$ denotes the event that every set of m vertices in the random graph G(n, p_n) contains an open L −clique, then

$$ \mathbb{P}({F_{n}^{c}}) \leq {n \choose m}3\exp\left( -m^{\theta_{chr}}\right) \leq n^{m} 3\exp\left( -m^{\theta_{chr}}\right) = 3e^{-B}, $$

(4.7)

where $B = m^{\theta _{chr}} - m\log {n} \geq \frac {1}{2}m^{\theta _{chr}}$ for all n large, since θ_chr > 1 by Eq. 4.5. The first estimate in Eq. 4.7 is obtained from the fact that the number of subsets of size m in the set {1,2, … , m} is (nm) and the probability that any subset of size m does not contain an open L −clique is at most $3\exp \left (-m^{\theta _{chr}}\right )$ by Eq. 4.6. If the event F_n occurs, then using property (a2) in Lemma 9, we have that

$$ \chi(G(n,1-p_{n})) \leq \frac{n}{L} + m =\frac{n}{c(1-\eta-\alpha_{2})W_{n}} + m. $$

(4.8)

We now estimate nW_n and show that it is much larger than m = n^c. Fix 𝜖 > 0 and recall from Eq. 1.1 that W_n = log n log(1 p_n). Using the bound − log(1 − x) > x in Eq. 2.1 with x = 1 − p_n, we get $\log \left (\frac {1}{p_{n}}\right ) = -\log (1-(1-p_{n})) > 1-p_{n} \geq \frac {1}{n^{\alpha _{2}+\epsilon }}$ for all n large, by the definition of α₂ in Eq. 1.2. Thus the term $W_{n} \leq n^{\alpha _{2}+\epsilon }\log {n}$ and so $\frac {n}{W_{n} } \geq \frac {n^{1-\alpha _{2}-\epsilon }}{\log {n}}.$ Since c < 1 − α₂ (see Eq. 1.8), we choose 𝜖 > 0 small so that c < 1 − α₂ − 𝜖. Fixing such an 𝜖, we get from Eq. 4.8 that χ(G(n,1 − p_n)) ≤ n(1+𝜖) c(1−η−α₂)W_n for all n large, proving the upper bound in Eq. 1.10. Arguing as in the discussion following Theorem 1, the estimate (1.11) follows from Eq. 1.10. □

Appendices

Appendix

Appendix: Proof of Theorems 3 and 4

Proof of Theorem 3

We use Theorem 1 with appropriate choices of η and γ.

• (i) Here α₁ = θ₁ < 2, α₂ = 0 and W_n = log n log(1 p_n) = 1 θ₁ . For 0 < ξ < 2−θ₁ θ₁ , we set 𝜖 = ξθ₁ 2 , η = θ₁ 2 + ξθ₁ and γ = ξθ₁ 2 so that Eq. 1.3 is satisfied and θ_clq = ξ. Using 𝜖(2 + 2𝜖)W_n logn ≥ 2𝜖W_n logn = ξ logn in Eq. 1.5, we then get Eq. 1.12.

• (ii) Here α₁ = α₂ = 0 and W_n = log n log(1 p). We let 0 < ξ < 1 and set 𝜖 = ξ 2, η = ξ and γ = ξ 2 and so that Eq. 1.3 is satisfied and θ_clq = ξ. As before, we use 𝜖(2 + 2𝜖)W_n logn ≥ 2𝜖W_n logn = ξ(log n)² log(1 p) and get Eq. 1.13 from Eq. 1.5.

• (iii) Here α₁ = 0 and α₂ = θ₂ < 1 and letting 0 < ξ < 1 we set 𝜖 = ξ 4, η = ξ 2 −θ₂ξ 2 and γ > 0 smaller than η. With these choices (1.3) is satisfied and moreover θ_clq = θ₂ + 2(η − γ) > θ₂. To evaluate W_n, use the log estimates (2.1) and (2.1) to get that $\frac {\frac {1}{n^{\theta _{2}}}}{1-n^{-\theta _{2}}} > \log \left (\frac {1}{p_{n}}\right ) = -\log \left (1-\frac {1}{n^{\theta _{2}}}\right ) > \frac {1}{n^{\theta _{2}}}$ and so

  $$ n^{\theta_{2}}\log{n}\left( 1-\frac{1}{n^{\theta_{2}}}\right) \leq W_{n} = \frac{\log{n}}{\log\left( \frac{1}{p_{n}}\right)} \leq n^{\theta_{2}}\log{n} $$

  (A.1)

  for all n large. Moreover

  $$ (1-\eta - \alpha_{2})W_{n} = (1-\theta_{2})\left( 1-\frac{\xi}{2}\right)W_{n} \geq (1-\theta_{2})(1-\xi)n^{\theta_{2}} \log{n} $$

  for all n large and $(2+2\epsilon )W_{n} +1 \leq (2+\xi )n^{\theta _{2}}\log {n}$ and $\epsilon (2+2\epsilon )W_{n}\log {n} \geq \frac {\xi }{4} n^{\theta _{2}} (\log {n})^{2}$ for all n large. Plugging the above into Eq. 1.5 we get Eq. 1.14.

Proof of Theorem 4

We use Theorem 2 with p_n = 1 − r_n and appropriate choices of η and γ.

• (i) Here p_n = 1 − r_n with α₁ = 0 and α₂ = θ₂ < 1 2. Thus η₀ := 1 2(1−θ₂) − θ₂ < 1 − θ₂ and for 0 < ξ < 1 to be determined later, we set

  $$ \epsilon = \frac{\xi}{6}, c = (1-\theta_{2})\left( 1-\frac{\xi^{3}}{6}\right) , \eta = \eta_{0} \left( 1+\frac{\xi^{2}}{6}\right) \text{ and } \gamma = \frac{\eta_{0} \xi^{2}}{12}. $$

  (A.2)

  We need to ensure that conditions (1.8) and (1.9) hold with α₁ = 0 and α₂ = θ₂. By definition c < 1 − θ₂ and η₀ < 1 − θ₂ and so max(η, c) < 1 − θ₂ provided ξ > 0 is small. We choose ξ > 0 smaller if necessary so that

  $$ c(\theta_{2} + \eta) = \frac{1}{2} - \frac{\xi^{3}}{12} + \frac{\eta_{0}\xi^{2}}{6}(1-\theta_{2})\left( 1-\frac{\xi^{3}}{6}\right) \geq \frac{1}{2} + \frac{\eta_{0}\xi^{2}}{12}(1-\theta_{2})\left( 1-\frac{\xi^{3}}{6}\right) $$

  and so θ₂ < 1 2 < c(θ₂ + η) < 1. To ensure the third condition in Eq. 1.8, we have

  $$ 2c(\theta_{2} + \eta-\gamma) = 1-\frac{\xi^{3}}{6} + \frac{\eta_{0}\xi^{2}}{6}(1-\theta_{2})\left( 1 - \frac{\xi^{3}}{6}\right) \!\geq\! 1 + \frac{\eta_{0}\xi^{2}}{12}(1-\theta_{2})\left( 1 - \frac{\xi^{3}}{6}\right) $$

  provided ξ > 0 is small. Fixing such a ξ we get 2c(θ₂ + η − γ) > 1 > 2θ₂, since θ₂ < 1 2. Thus Eq. 1.8 holds.

  To ensure (1.9), we write θ_chr = 1 1−θ₂ + η₀ξ² 6 − θ₂ (1−θ₂)(1−ξ³ 6) and choose ξ > 0 small so that (1 −ξ³ 6)^− 1 ≤ 1 + ξ³ 4 and so θ_chr ≥ 1 + η₀ξ² 6 − θ₂ (1−θ₂) ξ³ 4 ≥ 1 + η₀ξ² 12 . For future use we choose ξ > 0 smaller if necessary so that

  $$ c\theta_{chr} \geq (1-\theta_{2})\left( 1-\frac{\xi^{3}}{6}\right)\left( 1 + \frac{\eta_{0} \xi^{2}}{12}\right) \geq (1-\theta_{2})\left( 1+\frac{\eta_{0}\xi^{2}}{24}\right) > 1-\theta_{2}. $$

  (A.3)

  Thus the bounds in Eq. 1.11 is true. We now evaluate the upper and lower bounds in Eq. 1.11. From Eq. A.1 and the fact that 0 < ξ < 1, we get $(2+2\epsilon )W_{n} + 1 \leq \frac {2n^{\theta _{2}}\log {n}}{1-\xi }.$ Similarly

  $$ \frac{1+\epsilon}{c(1-\eta - \theta_{2})} = \frac{2\left( 1+\frac{\xi}{6}\right)}{\left( 1-\frac{\xi^{3}}{6}\right)\left( 1-2\theta_{2} - \frac{\eta_{0}\xi^{2}}{3}(1-\theta_{2})\right)} \leq \frac{2(1+\xi)}{1-2\theta_{2}}, $$

  provided ξ > 0 is small and these estimates obtain the bounds for χ(.) in Eq. 1.15.

  To evaluate the exponents in Eq. 1.11, we use Eq. A.1 to get that $\epsilon (2+\epsilon )W_{n} \log {n} \geq \frac {\xi }{4} n^{\theta _{2}}(\log {n})^{2}$ for all n large. Similarly from Eq. A.3 we get cθ_chr > 1 − θ₂ and this obtains (1.15).

• (ii) Here p_n = 1 − r_n = 1 − p and so α₁ = α₂ = 0. Letting ξ be small such that

  $$ \epsilon = \frac{\xi}{6}, \eta = \frac{1}{2} + 2\xi^{2} < 1, \gamma = \xi^{2} \text{ and } c=1-\xi^{3} $$

  (A.4)

  we get that the conditions in Eq. 1.8 are true. Also θ_chr = 1 + 2ξ² > 1 and so Eq. 1.9 is also true. Thus the bounds in Eq. 1.11 hold. Recalling that W_n = log n log(1 p_n) we have that (2 + 2𝜖)W_n + 1 = (2 + ξ 3) log n log(1 1−p) + 1 ≤ 2 (1−ξ) log n log(1 1−p) for all n large. Similarly, the scaling factor in the upper bound in Eq. 1.11 is 1+𝜖c(1−η−α₂) = 1+ξ6 (1−ξ³) (1 2 − 2ξ²) ≤ (1 + ξ) if ξ > 0 is small. The exponents in Eq. 1.11 evaluate to cθ_chr = (1 − ξ³)(1 + 2ξ²) ≥ 1 + ξ² for all ξ > 0 small and 𝜖(2 + 2𝜖)W_n ≥ 2𝜖W_n = ξ 3 log n log(1 1−p). This obtains (1.16).

• (iii) Here $p_{n} = 1-r_{n} = \frac {1}{n^{\theta _{1}}}$ and so α₁ = θ₁ < 1 and α₂ = 0. Let ξ be small such that

  $$ \epsilon = \frac{\xi^{2}}{6}, \eta = \frac{1+\theta_{1}}{2} + 2\theta_{1}\xi^{2} < 1, \gamma = \theta_{1}\xi^{2} \text{ and } c=1-\xi^{3}. $$

  (A.5)

  Recalling condition (1.8), we have max(η, c) < 1 = 1 − α₂,0 < cη = c(α₂ + η) < 1 and

  $$ \begin{array}{@{}rcl@{}} 2c(\alpha_{2} + \eta-\gamma) &=& 2(1-\xi^{3})(\eta-\gamma) = 2(\eta-\gamma) - 2\xi^{3}(\eta-\gamma)\\ &=& 1+\theta_{1} +2\theta_{1} \xi^{2} - 2\xi^{3}(\eta-\gamma). \end{array} $$

  (A.6)

  which is greater than one if ξ > 0 small. Thus Eq. 1.8 is true. Also θ_chr = 1 + θ₁ + 2θ₁ξ² − θ₁ 1−ξ³ and for all ξ > 0 small, we have 11−ξ³ ≤ 1 + ξ² and for such ξ, we have θ_chr ≥ 1 + θ₁ + 2θ₁ξ² − θ₁(1 + ξ²) = 1 + θ₁ξ² > 1. For future use we set ξ > 0 smaller if necessary so that

  $$ c\theta_{chr} \geq (1-\xi^{3}) (1+\theta_{1}\xi^{2}) \geq 1+\frac{\theta_{1}\xi^{2}}{2} > 1. $$

  (A.7)

  Thus Eq. 1.9 is also true and consequently, the bounds in Eq. 1.11 hold.

Recalling that W_n = log n log(1 p_n) = 1 θ₁ we have from Eq. A.5 that (2 + 2𝜖)W_n + 1 = (2 + ξ² 3) 1 θ₁ + 1 ≤ 2+θ₁ θ₁(1−ξ) for all n large, provided ξ > 0 small. Fixing such a ξ, the scaling factor in the upper bound in Eq. 1.11 is

$$ \frac{1+\epsilon}{c(1-\eta-\alpha_{2})} = \frac{1+\frac{\xi^{2}}{6}}{\left( 1-\xi^{3}\right)\left( 1-\frac{1+\theta_{1}}{2}-2\xi^{2}\right)} \leq (1+\xi)\frac{2}{1-\theta_{1}} $$

(A.8)

provided we set ξ > 0 smaller if necessary.

Finally, regarding the exponents in Eq. 1.17, we have from Eq. A.7 that cθ_chr > 1 and moreover 𝜖(2 + 2𝜖)W_n ≥ 2𝜖W_n = ξ² 3 1 θ₁ . This obtains (1.17).