On independent sets in random graphs

Introduction and Results

In the early papers on the subject, the motivation for the probabilistic analysis of algorithms was to alleviate the glum of worst-case analyses by establishing a brighter ‘average-case’ scenario . This optimism was stirred by early analyses of simple, greedy-type algorithms, showing that these perform rather well on randomly generated input instances, at least for certain ranges of the parameters. Examples of such analyses include Grimmett and McDiarmid (independent set problem), Wilf , Achlioptas and Molloy (graph coloring), and Frieze and Suen ($k$-SAT). Yet, remarkably, in spite of 30 years of research, for many problems no efficient algorithms, howsoever sophisticated, have been found to outperform those simple greedy algorithms markedly.

The independent set problem in random graphs $G(n,m)$ is a case in point. Recall that $G(n,m)$ is a graph on $n$ vertices obtained by choosing $m$ edges uniformly at random (without replacement). We say that $G(n,m)$ has a property with high probability if the probability that the property holds tends to 1 as $n\rightarrow\infty$. One of the earliest results in the theory of random graphs is a non-constructive argument showing that for $m=\frac{1}{2}{{n}\choose{2}}$ the independence number of $G(n,m)$ is $\alpha(G(n,m))\sim 2\log_{2}(n)$ w.h.p. . Grimmett and McDiarmid analysed a simple algorithm that just constructs an inclusion-maximal independent set greedily on $G(n,m)$: it yields an independent set of size $(1+o(1))\log_{2}n$ w.h.p., about half the maximum size. But no algorithm is known to produce an independent set of size $(1+\varepsilon)\log_{2}n$ for any fixed $\varepsilon>0$ in polynomial time with a non-vanishing probability, neither on the basis of a rigorous analysis, nor on the basis of experiments or other evidence. In fact, devising such an algorithm is probably the most prominent open problem in the algorithmic theory of random graphs . (However, note that one can find a maximum independent set w.h.p. by trying all $n^{O(\ln n)}$ possible sets of size $2\log_{2}n$.)

Matters are no better on sparse random graphs. If we let $d=2m/n$ denote the average degree, then non-constructive arguments yield

for $1\ll d=o(n)$. In the case $d\gg\sqrt{n}$, the proof of this is via a simple second moment argument . By contrast, for $1\ll d\ll\sqrt{n}$, the second moment argument breaks down and additional methods such as large deviations inequalities are needed . Yet in either case, no algorithm is known to find an independent set of size $(1+\varepsilon)\frac{\ln d}{d}\cdot n$ in polynomial time with a non-vanishing probability, while ‘greedy’ yields an independent set of size $(1+o(1))\frac{\ln d}{d}\cdot n$ w.h.p. In the sparse case, the time needed for exhaustive search scales as $\exp(\frac{2n}{d}\ln^{2}(d))$, i.e., the complexity grows as $d$ decreases.

The aim of this paper is to explore the tenacity of finding large independent sets in random graphs. The focus is on the sparse case, both conceptually and computationally the most difficult case. We exhibit a phase transition in the structure of the problem that occurs as the size of the independent sets passes the point $\frac{\ln d}{d}\cdot n$ up to which efficient algorithms are known to succeed. Roughly speaking, we show that independent sets of sizes bigger than $(1+\varepsilon)\frac{\ln d}{d}\cdot n$ form an intricately ragged landscape, which plausibly explains why local-search algorithms get stuck. Thus, ironically, instead of showing that the ‘average case’ scenario is brighter, we end up suggesting that random graphs provide an excellent source of difficult examples. Taking into account the (substantially) different nature of the independent set problem, our work complements the results obtained in for random constraint satisfaction problem such as $k$-SAT or graph coloring.

2 Results

Throughout the paper we will be dealing with sparse random graphs where the average degree $d=2m/n$ is ‘large’ but remains bounded as $n\rightarrow\infty$. To formalise this sometimes we work with functions $\varepsilon_{d}$ that tend to zero as $d$ gets large. The reason why we need to speak about $d$ ‘large’ is that the sparse random graph $G(n,m)$ is not connected. This implies, for instance, that algorithms can find independent sets of size $(1+\varepsilon_{d})n\ln(d)/d$ for some $\varepsilon_{d}\rightarrow 0$ by optimizing carefully over the small tree components of $G(n,m)$. Our results/proofs actually carry over to the case that $d=d(n)$ tends to infinity as $n$ grows, but to keep matters as simple as possible, we will confine ourselves to fixed $d$. Thus $\alpha(G(n,m))=(2-\varepsilon_{d})\frac{\ln d}{d}\cdot n$ and the greedy algorithm finds independent sets of size $(1+\varepsilon^{\prime}_{d})\frac{\ln d}{d}\cdot n$ w.h.p., where $\varepsilon_{d},\varepsilon_{d}^{\prime}\rightarrow 0$. However, no efficient algorithm is known to find independent sets of size $(1+\varepsilon^{\prime\prime})\frac{\ln d}{d}\cdot n$ for any fixed $\varepsilon^{\prime\prime}>0$.

There exists $\varepsilon_{d}\rightarrow 0$ and for any $d$ a number $C_{d}>0$ (independent of $n$) such that $\mathcal{S}_{k}(G(n,m))$ is $C_{d}$-connected w.h.p. for any

By contrast, our next result shows that for $k>(1+\varepsilon_{d})\frac{\ln d}{d}\cdot n$ the set $\mathcal{S}_{k}(G(n,m))$ is not just disconnected w.h.p., but that it shatters into exponentially many, exponentially tiny pieces.

We say that $\mathcal{S}_{k}(G(n,m))$ shatters if there exist constants $\gamma,\zeta>0$ such that w.h.p. the set ${\cal S}_{k}(G(n,m))$ admits a partition into subsets such that

Each subset contains at most $\exp\left({-\gamma n}\right)\left|{{\cal S}_{k}(G(n,m))}\right|$ independent sets.

There is $\varepsilon_{d}\rightarrow 0$ so that $\mathcal{S}_{k}(G(n,m))$ shatters for all $k$ with

Theorems 1 and 2 deal with the geometry of a single ‘layer’ $\mathcal{S}_{k}(G(n,m))$ of independents of a specific size. The following two results explore if/how a ‘typical’ independent set in $\mathcal{S}_{k}(G(n,m))$ can be extended to a larger one. To formalize the notion of ‘typical’, we let $\Lambda_{k}(n,m)$ signify the set of all pairs $(G,\sigma)$, where $G$ is a graph on $V=\left\{{1,\ldots,n}\right\}$ with $m$ edges and $\sigma\in{\cal S}_{k}(G)$. Let $\mathcal{U}_{k}(n,m)$ be the probability distribution on $\Lambda_{k}(n,m)$ induced by the following experiment.

Choose a graph $G=G(n,m)$ at random. If $\alpha(G)\geq k$, choose an independent set $\sigma\in\mathcal{S}_{k}(G)$ uniformly at random and output $(G,\sigma)$.

We say a pair $(G,\sigma)$ chosen from the distribution $\mathcal{U}_{k}(n,m)$ has a property $\mathcal{P}$ with high probability if the probability of the event $\left\{{(G,\sigma)\in\mathcal{P}}\right\}$ tends to one as $n\rightarrow\infty$.

Let $\gamma,\delta\geq 0$, let $G$ be a graph, and let $\sigma$ be an independent set of $G$. We say that $(G,\sigma)$ is $(\gamma,\delta)$-expandable if $G$ has an independent set $\tau$ such that $|\tau|\geq(1+\gamma)|\sigma|$ and $|\tau\cap\sigma|\geq(1-\delta)|\sigma|$.

There are $\varepsilon_{d},\delta_{d}\rightarrow 0$ such that for any $\varepsilon_{d}\leq\varepsilon\leq 1-\varepsilon_{d}$ the following is true. For $k=(1-\varepsilon)\frac{\ln d}{d}\cdot n$ a pair $(G,\sigma)$ chosen from the distribution $\mathcal{U}_{k}(n,m)$ is $((2-\delta_{d})\varepsilon/(1-\varepsilon),0)$-expandable w.h.p.

Theorem 3 shows that w.h.p. in a random graph $G(n,m)$ almost all independent sets of size $k=(1-\varepsilon)\frac{\ln d}{d}\cdot n$ are contained in some bigger independent set of size $(1+\varepsilon)\frac{\ln d}{d}\cdot n$. That is, they can be expanded beyond the critical size $\frac{\ln d}{d}\cdot n$ where shattering occurs. However, as $k$ approaches the critical size $\frac{\ln d}{d}\cdot n$, i.e., as $\varepsilon\rightarrow 0$, the typical potential for expansion diminishes.

There is $\varepsilon_{d}\rightarrow 0$ such that for any $\varepsilon$ satisfying $\varepsilon_{d}\leq\varepsilon\leq 1-\varepsilon_{d}$ and $k=(1+\varepsilon)\frac{\ln d}{d}\cdot n$ w.h.p. a pair $(G,\sigma)$ chosen from the distribution $\mathcal{U}_{k}(n,m)$ is not $(\gamma,\delta)$-expandable for any $\gamma>\varepsilon_{d}$ and

In other words, Theorem 4 shows that for $k=(1+\varepsilon)\frac{\ln d}{d}\cdot n$, a typical $\sigma\in\mathcal{S}_{k}(G(n,m))$ cannot be expanded to an independent set of size $(1+\gamma)k$, $\gamma>\varepsilon_{d}$ without first reducing its size below

(However, a random independent set of size $k\leq(2-\varepsilon_{d})\ln(d)n/d$ is typically not inclusion-maximal because, for instance, it is unlikely to contain all isolated vertices of the random graph $G(n,m)$.)

Metaphorically, the above results show that w.h.p. the independent sets of $G(n,m)$ form a ragged mountain range. Beyond the ‘plateau level’ $k\sim\frac{\ln d}{d}\cdot n$ there is an abundance of smaller ‘peaks’, i.e., independent sets of sizes $(1+\varepsilon)k$ for any $\varepsilon_{d}<\varepsilon<1-\varepsilon_{d}$, almost all of which are not expandable (by much).

The algorithmic equivalent of a mountaineer aiming to ascend to the highest summit is a Markov chain called the Metropolis process, . For a given graph $G$ its state space is the set of all independent sets of $G$. Let $I_{t}$ be the state at time $t$. In step $t+1$, the chain chooses a vertex $v$ of $G$ uniformly at random. If $v\in I_{t}$, then with probability $1/\lambda$ the next state is $I_{t+1}=I_{t}\setminus\{v\}$, and with probability $1-1/\lambda$ we let $I_{t+1}=I_{t}$, where $\lambda\geq 1$ is a ‘temperature’ parameter. If $v\not\in I_{t}\cup N(I_{t})$ (with $N(I_{t})$ the neighbourhood of $I_{t}$), then $I_{t+1}=I_{t}\cup\left\{{v}\right\}$. Finally, if $v\in N(I_{t})$, then $I_{t+1}=I_{t}$. It is well know that the probability of an independent set $S$ of $G$ in the stationary distribution equals $\lambda^{|S|}/Z(G,\lambda)$, where

is the partition function. Hence, the larger $\lambda$, the higher the mass of large independent sets. Let

denote the average size of an independent set of $G$ under the stationary distribution.

It is easy to see that every state in $\Omega=\bigcup_{k}S_{k}(G(n,m))$ communicates with every other in the Metropolis process. Thus the process is ergodic and possesses a unique stationary distribution. Let $\pi:\Omega\to$ denote the stationary distribution of the Metropolis process with parameter $\lambda$, for some $\lambda>0$. It is well known that $\pi(\sigma)={\lambda}^{|\sigma|}/Z$ where $Z=\sum_{\sigma\in\Omega}\lambda^{|\sigma|}$ (e.g. ).

Here, we are interested in finding the rate at which the Metropolis process converges to its equilibrium. There are a number of ways of quantifying the closeness to stationarity. Let $P^{t}(\sigma,\cdot):\Omega\to$ denote the distribution of the state at time $t$ given that $\sigma$ was the initial state. The total variation distance at time $t$ with respect to the initial state $\sigma$ is

Starting from $\sigma$, the rate of convergence to stationarity may then be measured by the function

The mixing time of the Metropolis process is defined as

Our above results on the structure of the sets $\mathcal{S}_{k}(G(n,m))$ imply that w.h.p. the mixing time of the Metropolis process is exponential if the parameter $\lambda$ is tuned so that the Metropolis process tries to ascend to independent sets bigger than $(1+\epsilon_{d})\frac{\ln d}{d}\cdot n$.

There is $\varepsilon_{d}\rightarrow 0$ such that for $\lambda>1$ with

the mixing time of the Metropolis process on $G(n,m)$ is $\exp(\Omega(n))$ w.h.p.

3 Related work

To our knowledge, the connection between transitions in the geometry of the ‘solution space’ (in our case, the set of all independent sets of a given size) and the apparent failure of local algorithms in finding a solution has been pointed first out in the statistical mechanics literature . In that work, which mostly deals with CSPs such as $k$-SAT, the shattering phenomenon goes by the name of ‘dynamic replica symmetry breaking.’ Our present work is clearly inspired by the statistical mechanics ideas, although we are unaware of explicit contributions from that line of work addressing the independent set problem in the case of random graphs with average degree $d\gg 1$. Generally, the statistical mechanics work is based on deep, insightful, but, alas, mathematically non-rigorous techniques.

In the case that the average degree $d$ satisfies $d\gg\sqrt{n}$, the independent set problem in random graphs is conceptually somewhat simpler than in the case of $d=o(\sqrt{n})$. The reason for this is that for $d\gg\sqrt{n}$ the second moment method can be used to show that the number of independent sets is concentrated about its mean. As we will see in Corollary 6 below, this is actually untrue for sparse random graphs.

The results of the present paper extend the main results from Achlioptas and Coja-Oghlan , which dealt with constraint satisfaction problems such as $k$-SAT or graph coloring, to the independent set problem. This requires new ideas, because the natural questions are somewhat different (for instance, the concept of ‘expandability’ has no counterpiece in CSPs). Furthermore, in we conjectured but did not manage to prove the counterpiece of Theorem 1 on the connectivity of $\mathcal{S}_{k}(G(n,m))$. On a technical level, we owe to the idea of analysing the distribution $\mathcal{U}_{k}(n,m)$ via a different distribution $\mathcal{P}_{k}(n,m)$, the so-called ‘planted model’ (see Section 3 for details). However, the proof that this approximation is indeed valid (Theorem 8 below) requires a rather different approach. In we derived the corresponding result from the second moment method in combination with sharp threshold results. By contrast, here we use an indirect approach that reduces the problem of estimating the number $|\mathcal{S}_{k}(G(n,m))|$ of independent sets of a given size to the problem of (very accurately) estimating the independence number $\alpha(G(n,m))$. Indeed, the argument used here carries over to other problems, particularly random $k$-SAT, for which it yields a conceptually simpler proof than given in (details omitted).

Subsequently to , it was shown in that in many random CSPs the threshold for the shattering of the solution space into exponentially small components coincides asymptotically with the reconstruction threshold. Roughly speaking, the reconstruction threshold marks the onset of long-range correlations in the Gibbs measure. More precisely, it is shown in that for a class of ‘symmetric’ random CSPs the reconstruction threshold derives from the corresponding threshold on random trees, and that it happens to coincide with the shattering threshold. Our Theorem 2 determines the threshold for shattering in the independent set problem in random graphs. Furthermore, Bhatnagar, Sly, and Tetali recently studied the reconstruction problem for the independent set problem on $k$-regular trees. It would be most interesting to obtain a result similar to , namely that the reconstruction threshold on the $G(n,m)$ random graph is given by the reconstruction threshold on trees and that it coincides with the shattering threshold from Theorem 2.

The work that is perhaps most closely related to ours is a remarkable paper of Jerrum , who studied the Metropolis process on random graphs $G(n,m)$ with average degree $d=2m/n>n^{2/3}$. The main result is that w.h.p. there exists an initial state from which the expected time for the Metropolis process to find an independent set of size $(1+\varepsilon)\frac{\ln d}{d}\cdot n$ is superpolynomial. This is quite a non-trivial achievement, as it is a result about the initial steps of the process where the states might potentially follow a very different distribution than the stationary distribution. The proof of this fact is via a concept called ‘gateways’, which is somewhat reminiscent of the expandability property in the present work. However, Jerrum’s proof hinges upon the fact that the number of independent sets of size $k\sim(1+\varepsilon)\frac{\ln d}{d}\cdot n$ is concentrated about its mean. The techniques from the present work (particularly Theorem 8 below) can be used to extend Jerrum’s result to the sparse case quite easily, showing that the expected time until a large independent set is found is fully exponential in $n$ w.h.p. Yet as also pointed out in , an unsatisfactory aspect of this type of result is that it only shows that there exists a ‘bad’ initial state, while it seems natural to conjecture that indeed most specific initial states (such as the empty set) are ‘bad’. Since we are currently unable to establish such a stronger statement, we will confine ourselves to proving an exponential lower bound on the mixing time (Corollary 1).

Recently Rossman obtained a monotone circuit lower bound for the clique problem on random graphs that is exponential in the size of the clique. The setup of is somewhat orthogonal to our contribution, as we are concerned with the case that the size of the desired object (i.e., the independent set) is linear in the number of vertices, while deals with the case that the size of the clique is $O(1)$ in terms of the order of the graph. Nevertheless, the punchline of viewing random graphs as a potential source of hard problem is similar.

In the course of the analysis in this paper we need a lower bound on $\alpha(G(n,m))$ which is bigger what is calculated in . For this reason, in , a previous version of this work, we improved slightly on the value of $\alpha(G(n,m))$. The analysis is similar to that in , i.e. combine vanilla second moment with Talagrand’s inequality. A bit later our result was improved even more by Dani and Moore . Raughly speaking, the authors show that a $G(n,m)$ of expected degree $d\leq 2(n/k)\ln(n/k)+2(n/k)-O(\sqrt{n/k})$ has an independent set of size $k$ w.h.p. In comparison to , our bound on $d$ in is $d<2(n/k)(\ln(n/k)+1)-O(\sqrt{\ln(n/k)\cdot(n/k)})$. To absolve our work from the tendious second moment calculations we make direct use of the result .

4 Organisation of the paper

The remaining material of this work is organised as follows: For completeness, in Section 2 we provide some very elementary results, which are either known or easy to derive. In Section 3 we analyse the so-called ‘planted model’ to approximate the distribution $\mathcal{U}_{k}(n,m)$. Then in Section 4 we show Theorem 1. In Section 5 we show Theorem 2. In Section 6 we show Theorem 3. In Section 7 we show Theorem 4. In Section 8 we show Corollary 1.

Preliminaries and notation

We will need the following Chernoff bounds on the tails of a sum of independent Bernoulli variables .

Let $I_{1},I_{2}\ldots,I_{n}$ be independent Bernoulli variables. Let $X=\sum_{i=1}^{n}I_{i}$ and $\mu=E[X]$. Then

Let $G^{*}(n,m)$ be random graph on $n$ vertices obtained as follows: choose $m$ pairs of vertices independently out of all $n^{2}$ possible pairs; insert the $\leq m$ edges induced by these pairs, omitting self-loops and replacing multiple edges by single edges. For technical reasons it will sometimes be easier to first work with $G^{*}(n,m)$ and then transfer the results to $G(n,m)$. The two distributions are related as follows.

Proof: This is a standard counting argument. The random graph $G^{*}(n,m)$ is obtained by choosing one of the $n^{2m}$ possible sequences of vertex pairs uniformly at random. Out of these $n^{2m}$ sequences, precisely $2^{m}{{n}\choose{2}}_{m}$ sequences induce simple graphs with $m$ edges (where $\left({\cdot}\right)_{m}$ denotes the falling factorial). Indeed, each of the ${{{{n}\choose{2}}}\choose{m}}$ simple graph with $m$ edges can be turned into a sequence of pairs by ordering the edges arbitrarily (a factor $m!$), and then choosing for each edge in which order its vertices appear in the sequence (a factor $2^{m}$). Hence, letting $\Sigma$ denote the event that $G^{*}(n,m)$ is a simple graph with $m$ edges, we see that

Furthermore, given that the event $\Sigma$ occurs, $G^{*}(n,m)$ is just a uniformly distributed (simple) graph with $m$ edges. Therefore, (4) yields

Suppose that $m=cn$ for a fixed $c>0$. For a graph $G$ let $Z_{k}(G)=|{\cal S}_{k}(G)|$. Then for any $1\leq k\leq 0.99n$ we have

Proof: Let $Q\subset V$ be a set of size $k$, and let $Z_{Q}(G)=1$ if $Q$ is independent in $G$, and set $Z_{Q}(G)=0$ otherwise. The total number of sequences of $m$ vertex pairs such that $Q$ is an independent set in the corresponding graph $G^{*}(n,m)$ equals $(n^{2}-k^{2})^{m}$ (just avoid the $k^{2}$ pairs of vertices in $Q$). Hence,

Combining (5) with (6) and using $\ln(1-x)=-x+O(x^{2})$ as $x\rightarrow 0$, we obtain

Taking logarithms and recalling that $k\leq 0.99n$ completes the proof. $\Box$

Finally we present a lemma that it will be very useful in the course of this paper.

Let $m=dn/2$ for a real $d>0$. Let $0<\beta<\ln d-\ln\ln d+1-\ln 2$ and set

If $Z_{k}(G)$ is the number of independent sets of size $k$ in $G$, then

Proof: Since $G^{*}(n,m)$ is obtained by choosing $m$ independent pairs of vertices, we have

Let $s=\frac{k}{n}$. By Stirling’s formula and the fact that for $x>0$ it holds that $\ln(1-x)=-x-\frac{x^{2}}{2(1-\xi)^{2}}$ for some $0<\xi<x$, we get that

where $q_{d}=\frac{\ln\ln d-1+\ln 2+\beta}{\ln d}$. As $m=\frac{d}{2}n$, we obtain

Note that both $\xi_{1},\xi_{2}$ tend to zero with $d$. Combining (8) and (9) yields the assertion. $\Box$

We also need the following theorem from Dani and Moore on the independence number of $G^{*}(n,m)$.

There is a constant $\alpha_{0}>0$ such that for any $x>4/e$ and any $k\leq\alpha_{0}n$ the following is true. Suppose that

and let $m=dn/2$. Then $\alpha(G^{*}(n,m))\geq k$ w.h.p.

Remark. In a previous version of this work we derived a slightly weaker bound on $d$, i.e. $d<2(n/k)(\ln(n/k)+1)-O(\sqrt{\ln(n/k)\cdot(n/k)})$. As opposed to the weighted second moment in , our approach is based on “vanilla” second moment calculations and the use of a Talagrand type inequality, i.e. similar to that in .

From we, also, have the following corollary.

Let $W(z)$ denote the largest positive root $y$ of the equation $ye^{y}=z$. W.h.p. it holds that

for any constant $y>4\sqrt{2}/e$. Expanding $W(ed/2)$ asymptotically in $d$ we have that

It is well known that the independence number $\alpha(G^{*}(n,m))$ of the random graph is tightly concentrated. More precisely, the following lower tail bound follows from a standard application of Talagrand’s large deviations inequality , similar to the one used in [28, Section 7.1] to establish concentration for $\alpha(G(n,p))$.

Suppose that $d,k$ are as in Theorem 6. Then for $m=\frac{dn}{2}$ and for any positive integer $t<k$ it holds that

Proof: Consider the graph $G(n,p)$ where $p=d/n$ and let $E(G(n,p))$ denote the number of its edges. It holds that

From the above derivations and Theorem 6, it is direct that

A vertex exposure argument allows to apply Talagrand’s large deviation inequality for the independence number of $G(n,p)$ (in the form that appears in , page 41 (2.39)). The following holds:

Working as in (10) we get that $\frac{1}{3}Pr[\alpha(G^{*}(n,m))<t]\leq Pr[\alpha(G(n,p))<t].$ The theorem follows. $\Box$

There is a constant $\alpha_{0}>0$ such that for $k<\alpha_{0}n$ and $G^{*}(n,m)$ of expected degree $d\leq\delta_{k}$ it holds that

Also, for $d=\delta_{k}$ it holds that $E|{\cal S}_{k}(G^{*}(n,m))|\leq\exp\left(14n\sqrt{{\ln^{5}d}/{d^{3}}}\right)$.

Proof: Let $G^{*}(n,m)$ be of expected degree $d=2(n/k)(\ln(n/k)+1)-{8}{\sqrt{n/k}}$, where $k$ is as in the statement. Also, let $k^{\prime}$ be such that $d=2(n/k^{\prime})(\ln(n/k^{\prime})+1)-2{\sqrt{n/k^{\prime}}}$. By Theorem 7 we have that

where the last inequality follows from the fact that $k^{\prime}<2k$. The tail bound in (11) will follow by bounding appropriately $t=k^{\prime}-k>0$. We bound $t$ by using the fact that

Set $s=k/n$ and $q=t/k$. Let $h(s,q)$ be the difference of the l.h.s. minus r.h.s. in the above equality, written in terms of $s,t$. Clearly, it holds that that $h(s,q)=0$. That is

For $1.5n\ln d/d<k,k^{\prime}<2n\ln d/d$, it is direct to verify that for $q=10/\sqrt{d\ln^{5}d}$ and sufficiently small $s$ it holds that $h(s,q)<0$. Furthermore, it is easy to see that

For any $q\in$ and sufficiently small $s$ we have that $\frac{\partial}{\partial q}h(s,q)>0$. This yields to the fact that for any $q\leq 10/\sqrt{d\ln^{5}}$ and sufficiently small $s$ we have $h(s,q)<0$. Thus, we get that $k^{\prime}-k\geq 10k/\sqrt{d\ln^{5}d}$. Plugging this into (12) we get that

For the rest of the proof, consider $G^{*}(n,m)$ with expected degree $d=\delta_{k}$. Assume that we add to $G^{*}(n,m)$ edges at random so as to increase the expected degree to $d^{+}=2\frac{s\ln s+(1-s)\ln(1-s))}{\ln(1-s^{2})}$ and get the graph $G^{*}(n,m^{\prime})$. That is, we need to insert into $G^{*}(n,m)$ as many as $(d^{+}-d)n/2$ random edges. Therefore, each independent set of size $k$ in $G^{*}(n,m)$ is also an independent set of $G^{*}(n,m^{\prime})$ with probability $\left(1-(k/n)^{2}\right)^{(d^{+}-d)n/2}$. Let $s=(k/n)$. It is direct that

Furthermore, using the fact that $-\frac{x}{1-x}\leq\ln(1-x)\leq-x$, for $0<x<1$, it is direct that

Combining (13), (14) and (15), we get that

The upper bound for $E|{\cal S}_{k}(G(n,m))|$ follows by using the above inequality and noting that $k\leq 2n\ln d/d$, i.e. $s\leq 2\ln d/d$. $\Box$

For the graph $G(n,m)$ of expected degree $d$ it holds that

where $\epsilon_{d}\to 0$ as $d$ increases.

Proof: Consider $G^{*}(n,m)$ of expected degree $d$ and let $k$ be such that $k/n=\frac{2}{d}\left(W(ed/2)-10\sqrt{\ln d/d^{3}}-2\frac{\ln\ln d}{\ln d}\right)$, where $W(z)$ is defined in the statement of Corollary 3. Using Corollary 3 and Theorem 7, we get that

The corollary follows by using Lemma 1. $\Box$

The following is taken from [28, p. 156].

Let $d>0$ be fixed and $m=dn/2$. Let $Y$ be the number of isolated vertices in $G(n,m)$. Then $Y=(1+o(1))n\exp(-d)$ w.h.p.

Approaching the distribution 𝒰k​(n,m)\mathcal{U}_{k}(n,m)

The main results of this paper deal with properties of ‘typical’ independents sets of a given size in a random graph, i.e., the probability distribution $\mathcal{U}_{k}(n,m)$. In the theory of random discrete structures often the conceptual difficulty of analysing a probability distribution is closely linked to the computational difficulty of sampling from that distribution (e.g., [28, Chapter 9]). This could suggest that analysing $\mathcal{U}_{k}(n,m)$ is a formidable task, because for $k>(1+\varepsilon)n\ln(d)/d$ there is no efficient procedure known for finding an independent set of size $k$ in a random graph $G(n,m)$, let alone for sampling one at random. In effect, we do not know of an efficient method for sampling from $\mathcal{U}_{k}(n,m)$.

To get around this problem, we are going to ‘approximate’ the distribution $\mathcal{U}_{k}(n,m)$ by another distribution $\mathcal{P}_{k}(n,m)$ on the set $\Lambda_{k}(n,m)$ of graph/independent set pairs, the so-called planted model, which is easy to sample from. This distribution is induced by the following experiment:

Choose a subset $\sigma\subset\left[{n}\right]$ of size $k$ uniformly at random. Choose a graph $G$ with $m$ edges in which $\sigma$ is an independent set uniformly at random. Output the pair $(G,\sigma)$.

In other words, the probability assigned to a given pair $(G_{0},\sigma_{0})\in\Lambda_{k}(n,m)$ is

i.e., $\mathcal{P}_{k}(n,m)$ is nothing but the uniform distribution on $\Lambda_{k}(n,m)$. The key result that allows us to study the distribution $\mathcal{U}_{k}(n,m)$ is the following.

There is $\varepsilon_{d}\rightarrow 0$ such that for $k<(2-\varepsilon_{d})n\ln(d)/d$ the following is true. If $\mathcal{B}$ is an event such that

Hence, Theorem 8 allows us to bound the probability of some ‘bad’ event $\mathcal{B}$ in the distribution $\mathcal{U}_{k}(n,m)$ by bounding its probability in the distribution $\mathcal{P}_{k}(n,m)$.

To establish Theorem 8, we need to find a way to compare $\mathcal{P}_{k}(n,m)$ and $\mathcal{U}_{k}(n,m)$. Suppose that $k<(2-\varepsilon_{d})n\ln(d)/d$ is such that $\alpha(G(n,m))\geq k$ w.h.p. Then the probability of a pair $(G_{0},\sigma_{0})\in\Lambda_{k}(n,m)$ under the distribution $\mathcal{U}_{k}(n,m)$ is

(because we first choose a graph uniformly, and then an independent set of that graph). Hence, the probabilities assigned to $(G_{0},\sigma_{0})$ under (18) and (16) coincide (asymptotically) iff

There exist functions $\varepsilon_{d}\rightarrow 0$ and $g(d)>0$ such that for $10n/d<k<(2-\varepsilon_{d})n\ln(d)/d$ we have

The proof of Corollary 6 appears in Section 3.3.

Conversely, in order to prove Theorem 8 we need to bound the ‘gap’ between the typical value of $|\mathcal{S}_{k}(G(n,m))|$ and its expectation from above. This estimate can be summarized as follows.

There is $\varepsilon_{d}\rightarrow 0$ such that for $k<(2-\varepsilon_{d})n\ln(d)/d$ we have

with probability at least $1-\exp\left[-n/(2d^{2}\ln^{4}d)\right]$.

Before we prove Proposition 1 in Section 3.2, let us indicate how it implies Theorem 8.

There is $\varepsilon_{d}\rightarrow 0$ such that for $k<(2-\varepsilon_{d})n\ln(d)/d$ the following is true. Let

Proof: Proposition 1 directly implies that

Furthermore, by the definition (18) of the uniform distribution,

The assertion is immediate from (21) and (22). $\Box$

Proof of Theorem 8: The theorem follows directly from Corollary 7. $\Box$

2 Proof of Proposition 1

Since the second moment method fails to yield a lower bound on the typical number of independent sets $|\mathcal{S}_{k}(G(n,m))|$, we need to invent a less direct approach to prove Proposition 1. Of course, the demise of the second moment argument also presented an obstacle to Frieze in his proof that

However, unlike the number $|\mathcal{S}_{k}(G(n,m))|$ of independent sets $\alpha(G(n,m))$, the size of the largest one actually is concentrated about its expectation. In fact, an arsenal of large deviations inequalities applies (e.g., Azuma’s and Talagrand’s inequality), and uses these to bridge the gap left by the second moment argument.Unfortunately, these large deviations inequalities draw a blank on $|\mathcal{S}_{k}(G(n,m))|$. Therefore, we are going to derive the desired lower bound on $|\mathcal{S}_{k}(G(n,m))|$ directly from (23).

To simplify our derivations we consider the model of random graphs $G^{*}(n,m)$ and we show the following proposition.

There is $\varepsilon_{d}\rightarrow 0$ such that for $k<(2-\varepsilon_{d})n\ln(d)/d$ we have

with probability at least $1-\exp\left[-n/(d\ln^{2}d)^{2}\right]$.

Then, Proposition 1 follows by Lemmas 1 and 2.

Given some integer $k>0$ and $q\in$, let $Z_{k}(G^{*}(n,m))=|{\cal S}_{k}(G^{*}(n,m))|$ and let

In words, $M^{q}_{k}$ is the largest number of edges that we can squeeze in while keeping the probability that $G^{*}(n,m)$ has an independent set of size $k$ above $1-q$. The following lemma summarizes the key step of our proof of Proposition 2. The idea is that Lemma 4 gives a tradeoff between the likely number of independent set of size $k$ in the random graph with $m<M^{q}_{k}$ edges and the expected number of such independent sets in the random graph with $M^{q}_{k}$ edges.

Suppose that $k,m>0,q\in\left[{0,1}\right]$ are such that $m<M^{q}_{k}$. Then

Proof: Let $M=M^{q}_{k}$. The random graph $G^{*}(n,M)$ is obtained by choosing $M$ pairs of vertices independently and inserting the corresponding edges (while omitting loops and reducing multiple edges to single edges). Let us think of the $M$ pairs as being generated in two rounds. In the first round, we generate $m$ pairs, which induce the random graph $G_{1}=G^{*}(n,m)$. In the second round, we choose a further $M-m$ pairs independently and add the corresponding edges to $G_{1}$ (again, omitting self-loops and reducing multiple edges to single edges) to obtain $G_{2}=G^{*}(n,M)$.

By the linearity of the expectation and because the $m$ (resp. $M$) pairs that the random graph $G_{1}$ (resp. $G_{2}$) consists of are chosen independently, we have (cf. (7))

Furthermore, with respect to the number of independent sets of size $k$ in $G_{2}$ given their number in the outcome $G_{1}$ of the ‘first round’, we have

Indeed, for each independent set $Q$ of size $k$ in $G_{1}$ each of the $M-m$ additional random pairs has its two vertices in $Q$ with probability $(k/n)^{2}$. Hence, (26) follows because these $M-m$ pairs are independent and by the linearity of the expectation.

Now, let ${\cal E}_{1}$ be the event that

Then by and Markov’s inequality and (26),

Combining (27) and (25), we see that $Pr\left[{{\cal E}_{1}}\right]\leq 2\,Pr\left[Z_{k}(G_{2})<1\right]\leq 2q,$ as claimed. $\Box$

Proof of Proposition 2. Consider $G^{*}(n,m)$ of expected degree $d$ and let $k=\frac{2}{d}\left(\ln d-\ln\ln d+1-\ln 2\right)$. We are going to show that (24) holds for $G^{*}(n,m)$ and $k$ with probability at least $1-\exp\left[-n/(d\ln^{2}d)^{2}\right]$.

Consider, now, the graph $G(n,M)$ of expected degree $d^{+}=2\frac{-\ln s+1}{s}+\frac{8}{\sqrt{s}}$, where $s=k/n$. According to 4 it holds that $Pr[|S_{k}(G(n,M))|>0]\geq 1-12\exp\left(-n/(d^{2}\ln^{5}d)\right)$ and $E|S_{k}(G(n,M))|\leq\exp\left(14\sqrt{\frac{\ln^{5}d}{d^{3}}}\right)$.

The proposition will follow by just showing that $m<M$, i.e. $d^{+}>d$, and using Lemma 4. Note, first, that

Using the above, it is elementary to derive that $2\frac{-\ln s+1}{s}\geq d$. Then, it follows that $d^{+}>d$ as promised. $\Box$

3 Proof of Corollary 6

In this section we keep the assumptions of Corollary 6, i.e., we let $k,d$ be such that $10n/d<k<(2-\varepsilon_{d})n\ln(d)/d$, with $\varepsilon_{d}\rightarrow 0$ sufficiently slowly in the limit of large $d$.

There is a number $\xi>0$ such that the following is true. Let $(G,\sigma)$ be a pair chosen from the distribution $\mathcal{P}_{k}(n,m)$. Let $X$ be the number of isolated vertices in $G$. Then

Proof: Let $\alpha=k/n$. It is convenient to first consider the following variant of the planted distribution: given a set $\sigma\subset V$ of size $k$, let $G^{\prime}$ be the random graph obtained by including each of the ${{n}\choose{2}}-{{k}\choose{2}}$ possible edges that do not link two vertices in $\sigma$ with probability

independently. Hence, the total number of edges in $G^{\prime}$ is binomially distributed with mean $m$. By Stirling’s formula, the event ${\cal E}$ that $G^{\prime}$ has precisely $m$ edges has probability $\Theta(m^{-1/2})$, and given that ${\cal E}$ occurs, the pair $(G^{\prime},\sigma)$ has the same distribution as the pair $(G,\sigma)$ chosen from the distribution $\mathcal{P}_{k}(n,m)$. Therefore, for any event $\mathcal{A}$ we have

Now, consider the number $X^{\prime}$ of vertices in $\sigma$ that are isolated in $G^{\prime}$. Since each possible edge is present in $G^{\prime}$ with probability $q$ independently, the degree of each vertex $v\in\sigma$ has a binomial distribution ${\rm Bin}(n-k,q)$ with mean

In particular, for each $v\in\sigma$ we have

Furthermore, because $\sigma$ is an independent set, the degrees of the vertices in $\sigma$ are mutually independent. Hence, $X^{\prime}$ has a binomial distribution ${\rm Bin}(k,(1+o(1))\exp(-(1+\alpha)d))$ with mean

provided that $d$ is sufficiently large. Since $X^{\prime}$ is binomially distributed, Chernoff bounds yield a number $\xi=\xi(d)>0$ such that

Finally, combining (30) and (29), we obtain

Proof of Corollary 6. Let $\mathcal{B}\subset\Lambda_{k}(n,m)$ be the set of all pairs $(G,\sigma)$ such that $G$ has fewer than $2n\exp(-d)$ isolated vertices. Lemmas 3 and 5 entail that

Since $\mathcal{P}_{k}(n,m)$ is the uniform distribution over $\Lambda_{k}(n,m)$, (31) implies that

Proof of Theorem 1

Instead of the random graph model $G(n,m)$ we consider the model $G(n,p)$, where $p=d/n$ for fixed real $d$ and we prove the following theorem.

There is $\varepsilon_{d}\rightarrow 0$ such that $\mathcal{S}_{k}(G(n,d/n))$ is $O(1)$-connected for any $k\leq(1-\varepsilon_{d})\frac{\ln d}{d}\cdot n$, with probability at least $1-\exp\left(-\frac{\ln^{40}d}{d}n\right)$.

Theorem 1 follows by using standard arguments, i.e. the following corollary.

For any fixed $d>0$, $m=dn/2$ and any graph property $A$ it holds that $Pr[G(n,m)\in A]\leq\Theta(\sqrt{n})Pr[G(n,d/n)\in A]$.

Proof: Let $E_{d}$ be the number of edges in $G(n,d/n)$. It holds that

$E_{d}$ is binomially distributed with parameters ${n\choose 2}$ and $d/n$. Straightforward calculations yield to that $Pr[E_{d}=dn/2]=\Theta(1/\sqrt{n})$. The corollary follows. $\Box$

Remark. We show Theorem 9 by just considering the adjacent independent sets with Hamming distance at most $20d$.

For every vertex $u$ in $G(n,d/n)$ we let $N(u)$ (or $N_{v}$) denote the set vertices which are adjacent to $u$. A sufficient condition for establishing the connectivity of ${\cal S}_{k}(G(n,d/n))$ is requiring this space to have what we call Property $\Gamma$:

Property $\boldsymbol{\Gamma}$. For any two $\sigma,\tau\in{\cal S}_{k}(G(n,d/n))$ there exist chains $\sigma,\sigma^{\prime},\sigma^{\prime\prime}$ and $\tau,\tau^{\prime},\tau^{\prime\prime}$ of independent sets in ${\cal S}_{k}(G(n,d/n))\bigcup{\cal S}_{k+1}(G(n,d/n))$ connected as in Figure 2. Furthermore, we have that $\sigma^{\prime\prime},\tau^{\prime\prime}\in{\cal S}_{k}(G(n,d/n))$ and $dist(\sigma^{\prime\prime},\tau^{\prime\prime})<dist(\sigma,\tau)$. In particular it holds that $|\sigma^{\prime\prime}\cap\tau^{\prime\prime}|=|\sigma\cap\tau|+1$.

If ${\cal S}_{k}(G(n,d/n))$ has Property $\Gamma$, then it is connected.

Using Corollary 9, Theorem 9 will follow by showing that with probability $1-o(1)$ the set ${\cal S}_{k}(G(n,d/n))$ has Property $\Gamma$, for $k<(1-\epsilon_{d})\ln d/d$ . For this, we need to introduce the notion of “augmenting vertex”.

For the pair $\sigma,\tau\in{\cal S}_{k}(G(n,d/n))$ the vertex $v\in V\backslash(\sigma\cup\tau)$ is augmenting if one of the following $A$, $B$ holds.

$N_{v}\cap(\sigma\cap\tau)=\emptyset$ and there are terminal sets $I_{v}(\sigma)$ and $I_{v}(\tau)$ of size at most $7d$ such that

$I_{v}(\sigma)\cup\{v\}$ is an independent set of $G(n,d/n)$

$\forall w\in I_{v}(\sigma)$ it holds that $|N_{w}\cap\sigma|=1$ and $|N_{w}\cap N_{u}\cap\sigma|=1$

The corresponding conditions should hold for $I_{v}(\tau)$, as well.

Figure 2 shows an example of a pair of independent sets where the vertex $v$ is an augmenting vertex.

We will show that for a pair $\sigma,\tau\in{\cal S}_{k}(G(n,d/n))$ that has an augmenting vertex $v$ we can find short chains $\sigma,\sigma^{\prime},\sigma^{\prime\prime}$ and $\tau,\tau^{\prime},\tau^{\prime\prime}$. That is, if we can find an augmenting vertex for any two members of ${\cal S}_{k}(G(n,d/n))$, then ${\cal S}_{k}(G(n,d/n))$ has Property $\Gamma$.

First, let us show how we can create short chains as in Figure 2 for two independent sets $\sigma,\tau$ with augmenting vertex $v$. For this, we introduce a process called Collider. This process takes as an input $\sigma$, $\tau$ and the augmenting vertex $v$ and returns the independent sets $\sigma^{\prime\prime}$ and $\tau^{\prime\prime}$ of the chains.

Phase 1. /*Creation of $\sigma^{\prime}$ and $\tau^{\prime}$.*/

Derive $\sigma^{\prime}$ from $\sigma$ by removing the all its vertices in $N_{v}\cap\sigma$ and by inserting $\{v\}\cup I_{v}(\sigma)$.

Phase 2. /* Creation of $\sigma^{\prime\prime}$ and $\tau^{\prime\prime}$*/.

$\sigma^{\prime\prime}$ is derived from $\sigma^{\prime}$ by deleting one (any) vertex from $\sigma^{\prime}\backslash\tau^{\prime}$.

$\tau^{\prime\prime}$ is derived from $\tau^{\prime}$ by deleting one (any) vertex from $\tau^{\prime}\backslash\sigma^{\prime}$.

Return $\sigma^{\prime\prime}$ and $\tau^{\prime\prime}$.

Figure 4 shows the changes that have taken place to the independent sets in Figure 2 at the end of “Phase 1”. Note that after Phase 1 both $\sigma^{\prime},\tau^{\prime}$ contain the augmenting vertex $v$, i.e. the overlap has increased as $\sigma^{\prime}\cap\tau^{\prime}=(\sigma\cap\tau)\cup\{v\}$.

After “Phase 2”, the independent sets in Figure 4 are transformed to those in Figure 4. There the vertices $u_{2}$ and $u_{7}$ are removed from $\sigma^{\prime}$ and $\tau^{\prime}$, correspondingly.

In the following lemma we show that Collider has all the desired properties we promise above.

Let $\sigma,\tau\in{\cal S}_{k}(G)$ with augmenting vertex $v$. Let $\sigma^{\prime\prime}$ and $\tau^{\prime\prime}$ be the two sets of vertices that are returned from Collider($\sigma,\tau,v$) . The two sets have the following properties: