Local algorithms for independent sets are half-optimal

Introduction

Local algorithms are randomized algorithms that run in parallel at each vertex of a graph by using only local information around each vertex. They produce important structures in large graphs, such as independent sets, matchings and colourings, with only constant running time (see and the references therein). In this paper we investigate local algorithms for high density independent sets in random $d$-regular graphs. We find an optimal bound for the density of such independent sets as the degree becomes large. It turns out that in this limit local algorithms can only yield independent sets with half the maximum possible density.

The motivation for our work comes from questions that arose in the theory of graph limits (see and the references therein). In particular, Hatami, Lovász, and Szegedy conjecture ( Conjecture 7.13) that most optimization problems over typical, sparse graphs can be solved by local algorithms.

We use the following notion of local algorithm introduced in . The input to the algorithm is a graph $G$. The algorithm decorates $G$ by putting i.i.d. labels on the vertices. The output is $(f(i(v));v\in G)$ where $f$ depends on the isomorphism class $i(v)$ of the labelled, rooted $r$-neighbourhood of $v$ for some fixed $r$. The process $(f(i(v));v\in G)$ generated by the local algorithm will be called a factor of i.i.d. process. See Section 2 for a more formal definition.

While the conjecture of Hatami, Lovász, and Szegedy was verified for maximal matchings and covariance structures , Gamarnik and Sudan showed that it fails for maximal independent sets. An independent set in a graph is a set of vertices that have no edges between them.

It is known from that for each $d$ the size density of the largest independent sets in a random $d$-regular graph on $n$ vertices converges almost surely as $n\to\infty$. Furthermore, Bollobás and McKay proved that with high probability the size density of the largest independent sets in random $d$-regular graphs is at most $2(\log d)/d$ for every $d\geq 3$. Frieze and Łuczak provided lower bounds of matching asymptotic order for large $d$. Recently, precise formulae were given for large $d$ by Ding, Sly and Sun . On the other hand, several authors have produced local algorithms on $d$-regular graphs of large girth that yield independent sets of density $(\log d)/d$ for large $d$ (see ). These algorithms use greedy strategies to construct independent sets and can be easily adapted to random $d$-regular graphs.

Thus, for large $d$, the density of the largest independent sets in random $d$-regular graphs is of order $2(\log d)/d$ while local algorithms have only produced independent sets with density of order $(\log d)/d$. The conjecture of Hatami, Lovász, and Szegedy would imply that local algorithms can in fact produce independent sets in random $d$-regular graphs of density $2(\log d)/d$.

Gamarnik and Sudan disprove this conjecture by showing that for large $d$ local algorithms can not find independent sets in random $d$-regular graphs of density larger than $(1+\frac{1}{\sqrt{2}})(\log d)/d$. Their crucial step is to prove that with high probability any two high density independent sets in random $d$-regular graphs have a substantially large or substantially small intersection. This observation was guided by predictions from statistical physics regarding the solution-space geometry of constraint satisfaction problems . In particular, the so called clustering phenomenon is expected to hold for independent sets in sparse random graphs. Rigorous results have been established in this regard by Coja-Oghlan and Efthymiou and in the aforementioned work of Ding, Sly and Sun . It is shown that for large enough $d$, some of the properties that determine clustering emerge for independent sets in random $d$-regular graphs at size density $(\log d)/d$.

In this paper we analyze the intersection densities of many independent sets in random regular graphs. We show that with high probability (i.e., with probability tending to one as the size of the graphs tends to infinity) the intersection densities must satisfy various inequalities. These structural results on the admissible intersection densities imply quantitative bounds on the density of independent sets that can be generated from local algorithms. With the help of these inequalities we prove that for any $\epsilon>0$, local algorithms can not find independent sets in random $d$-regular graphs of density larger than $(1+\epsilon)(\log d)/d$ if $d$ is sufficiently large. In practice, iterative search algorithms that use local moves at each step fail to find independent sets with density exceeding the critical threshold of $(\log d)/d$ in random $d$-regular graphs. Our result provides some evidence as to why this is the case.

We also consider local algorithms for independent sets in Poisson-Galton-Watson trees. These yield local algorithms for independent sets in sparse Erdős-Rényi graphs. We prove that the maximal density of local independent sets in a Poisson-Galton-Watson tree of expected degree $\lambda$ is of asymptotic order $(\log\lambda)/\lambda$ as $\lambda\to\infty$. The aforementioned results of Bollobás , Frieze and Łuczak show that the largest independent sets in Erdős-Rényi graphs of average degree $\lambda$ have density of asymptotic order $2(\log\lambda)/\lambda$ as $\lambda\to\infty$.

The challenge in proving upper bounds to the density of local independent sets in Poisson-Galton-Watson trees is showing that the randomness of the tree does not provide local algorithms with extra power. Also, in order to show the existence of local independent sets having density close to $(\log\lambda)/\lambda$ we employ a coupling argument that produces independent sets in Poisson-Galton-Watson trees from independent sets in regular trees.

In Section 2 we define the notion of a local algorithm for independent sets in the $d$-regular tree and relate it to local algorithms on finite $d$-regular graphs. Our main result about the density of local independent sets in regular trees is stated in Theorem 2.1. In Section 2.1 we introduce the key inequality, stated in Theorem 2.2, that is satisfied by the intersection densities of any finite collection of local independent sets in the $d$-regular tree. Using this inequality we prove Theorem 2.1 in Section 2.2. In Section 3 we prove Theorem 2.2 by employing combinatorial arguments involving random regular graphs. In Section 4 we state and prove our main result, Theorem 4.1, on local independent sets in Poisson-Galton-Watson trees.

Local algorithms for independent sets in regular graphs

It is easy to see that a factor that generates independent sets can be approximated by similar factors that depend on finite size neighbourhoods of the root (see [16, Section 12]). In this manner a factor of i.i.d. independent set of density $\rho$ can be approximated by finite neighbourhood factor of i.i.d. independent sets whose densities converge to $\rho$. Hence, there is no harm in assuming that all our factors for independent sets depend on finite size neighbourhoods of the root.

Lauer and Wormald show that taking $k=\frac{c}{p}$ and then letting $p\to 0$, followed by $c\to\infty$, results in independent sets whose densities converge to $\beta(d):=\frac{1-(d-1)^{-2/(d-2)}}{2}$. A simple analysis shows that $\frac{\log(d-1)}{d-2}-2(\frac{\log(d-1)}{d-2})^{2}\leq\beta(d)\leq\frac{\log(d-1)}{d-2}$.

The following ineqaulity holds for $\alpha_{d}$:

1. Key inequality for intersection densities of local independent sets

We will achieve a contradiction by first showing that these intersection densities are constrained to satisfy an inequality for each $k$. Secondly, we will violate these inequalities by tuning the coupling parameter $p$ (under the assumption that $\alpha>1$). The next theorem introduces these key inequalities. Their proof, discussed in Section 3, is based on a structure theorem about independent sets in random $d$-regular graphs.

For each $k\geq 1$ the quantities $\alpha_{i,d,p}$ for $1\leq i\leq k$ satisfy the following

Theorem 2.2 is proved by counting the expected number of $k$-tuples of independent sets $(I_{i},\ldots,I_{k})$ in random $d$-regular graphs such that their intersection densities are close to the quantities $\alpha_{i,d,p}\frac{\log d}{d}$ for $1\leq i\leq k$. We show that if (2.2) fails then the probability of observing such $k$-tuples of independent sets in random $d$-regular graphs is vanishingly small as the size of the graphs tend to infinity. On the other hand, Lemma 3.4 implies that the existence of the local independent sets $(I_{d,1},\ldots,I_{d,k})$ allows us to observe such $k$-tuples of independent sets in random $d$-regular graphs with high probability and so (2.2) must hold.

In their paper Gamarnik and Sudan derive inequality (2.2) for $k=2$. The $k=2$ case gives

To minimize this in $p$ we certainly want to set $\alpha_{2,d,p}=1$ for every $d$. It turns out that $\alpha_{2,d,p}$ is continuous in $p$ (see Lemma 2.3) with $\alpha_{2,d,0}=\alpha$ and $\alpha_{2,d,1}=\alpha^{2}(\frac{\log d}{d})$. So if $\alpha>1$ then for all large $d$ we can find a value of $p$ such that $\alpha_{2,d,p}=1$. This implies that the density $\alpha$ satisfies $\alpha(2-\alpha)\geq 1/2$, or equivalently, that $\alpha\leq 1+\frac{1}{\sqrt{2}}$. This is the conclusion of Gamarnik and Sudan.

We may also analyze (2.2) for $k=3$ to conclude that $\alpha\leq 1+\frac{1}{\sqrt{3}}$. Indeed, we have that $3\alpha(2-\alpha)-2\alpha_{2,d,p}(2-\alpha_{2,d,p})+\alpha_{3,d,p}(2-\alpha_{3,d,p})\geq 0$ for large $d$. If $\alpha>1$ then for all large $d$ we may choose a value of $p$ such that $\alpha_{2,d,p}=1$. Also, observe that $\alpha_{3,d,p}(2-\alpha_{3,d,p})\leq 1$. Thus, we conclude from (2.2) that $3\alpha(2-\alpha)-2+1=3\alpha(2-\alpha)-1\geq 0$. This implies that $\alpha\leq 1+\frac{1}{\sqrt{3}}$.

We do not know how to solve the minimization problem in $p$ exactly for $k\geq 4$. In order to analyze (2.2) for large values of $k$ we are going to make a choice of $p$ for each $d$ (and fixed $k$) that allows us to bound the sum in (2.2) from above as $d\to\infty$. This upper bound is going to be a quantity that we can analyze in the large $k$ limit. From there we will derive a contradiction to the assumption that $\alpha>1$.

2. Proof of Theorem 2.1 from Theorem 2.2

for any random variable $U$ defined on $\{f_{d}(X_{0})\equiv 1\}$.

If $\mathcal{F}$ is a $\sigma$-algebra such that $f_{d}(X_{0})$ is $\mathcal{F}$-measurable, then for any random variable $U$ defined on the original probability space we have

Define a sequence of $$-valued random variables$Q_{d,p}=Q_{d}(S,X_{0})$, which we denote the stability, on the restricted probability space as follows. Let

Roughly speaking, the stability is the conditional probability, given the root is included in the independent set, that it remains to be included after re-randomizing the labels on $S$.

The random variables $f_{d,i}$ are independent of each other conditioned on $(X_{0},S)$. Hence,

Furthermore, $f_{d,0}$ is measurable w.r.t. $(X_{0},S)$ and so we conclude that

We now translate the inequality from (2.2) in terms of the stability. Our goal is to rewrite (2.2) as an expectation of a function of the stability, which we can then analyze for large values of $d$ and $k$.

Observe the following identity that results from the binomial theorem:

Let $s_{k}(x)=\frac{1-(1-x)^{k}}{x}$ for $x\in$ and $k\geq 1$. Note that $s_{k}(0)=\lim_{x\to 0}s_{k}(x)=k$. We may now translate the inequality from (2.2) into

We make a particular choice of $p$ for every $d$ in order to analyze (2.4) in the large $d$ limit. Fix a parameter $u>0$ that we will tune later. In the statement of Lemma 2.3 take $g(x)=x^{u}$ for $0\leq x\leq 1$. From the assumption that $\alpha>1$, we employ Lemma 2.3 and deduce that for all sufficiently large $d$ we can select a $p=p(d,u)$ such that

We denote $Q_{d,p(d,u)}$ by $Q_{d}$. At this point our reasoning behind this choice is mysterious. The idea, of course, is that by choosing $p$ this way we try to minimize the left hand side of (2.4) in a manner that we can analyze as $k\to\infty$. The argument that follows will show that our choice is judicious.

Recall that probability distributions on $$are compact with respect to convergence in distribution. Therefore, from the sequence$(Q_{d},R_{d})$we can choose a subsequence$(Q_{d_{i}},R_{d_{i}})$that converges in distribution to limiting random variables$(Q,R)$. The random variables$Q$and$R$are independent and identically distributed with values in$$.

By passing to the subsequence $d_{i}$ and taking limits in $i$ the inequality (2.4) becomes

Simplifying the latter inequality gives $\alpha\leq 1$; a contradiction.

Fix $0<\epsilon<1$, and write $s_{k}(x)=s_{k,\leq\epsilon}(x)+s_{k,>\epsilon}(x)$ where $s_{k,\leq\epsilon}(x)=s_{k}(x)\,\mathbf{1}_{x\leq\epsilon}$. Note that $s_{k,>\epsilon}(x)\leq\epsilon^{-1}$ for all $k$. We have that

We also observe from the positivity of $s_{k}$ that

Due to the contradiction resulting from the previous two cases we deduce that for all $u>0$ we have $\alpha\leq 2^{\frac{u}{u+1}}$. By letting $u\to 0$ we conclude that $\alpha\leq 1$; the final contradiction.

Inequalities for intersection densities: proof of Theorem 2.2

We will prove Theoem 2.2 by reducing it to a problem about densities of independent sets in large, finite, $d$-regular graphs. First, we begin with some terminology. Let $\mathcal{G}_{n,d}$ denote a random $d$-regular graph on $n$ vertices sampled according to the configuration model (see chapter 2.4): each of the $n$ distinct vertices emit $d$ distinct half-edges, and we pair up these $nd$ half-edges uniformly at random. These $nd/2$ pairs of half-edges can be glued into full edges to yield a labelled, random, $d$-regular graph. Note that the resulting graph can have loops and multiple edges. There are $(nd-1)!!=(nd-1)(nd-3)\cdots 3\cdot 1$ possible pairings, or outcomes, of the model. Let $G_{n,d}$ denote the set of all these outcomes. So $\mathcal{G}_{n,d}$ is picked uniformly at random from $G_{n,d}$.

2. The expected number of independent sets satisfying a given density profile

For a $k$-tuple of independent sets $(I_{G,1},\ldots,I_{G,k})$ in $G\in G_{n,d}$, the density profile associated to this $k$-tuple is the vector $\rho=(\rho(T);T\subset[k])$ defined by $\rho(T)=|\cap_{i\in T}I_{G,i}|/n$ (set $\rho(\emptyset)=1$). Associated to this $k$-tuple is also an ordered partition $\Pi$ of $V(G)$ into $2^{k}$ cells defined as follows:

In other words, $\Pi(T)$ consists of vertices that belong to all the sets $I_{G,i}$ for $i\in T$ and none of the other sets. The partition $\Pi$ defines a probability measure $\pi=(\pi(T);T\subset[k])$ on $2^{[k]}$ by $\pi(T)=|\Pi(T)|/n$. This correspondence between $k$-tuples $(I_{G,1},\ldots,I_{G,k})$ and ordered partitions $\Pi$ is bijective, and by the inclusion-exclusion principle we have that

Finally, corresponding to $G$ and $\Pi$ is a $2^{k}\times 2^{k}$ matrix $M$ that we denote the edge profile of $\Pi$. For $T,T^{\prime}\subset[k]$, define

The tuple $(u,v)$ refers to a directed edge; so $(u,v)\neq(v,u)$ unless $u=v$. The number of directed edges of $G$ is $2|E(G)|=nd$. Notice that $M(T,T^{\prime})$ is the probability that a uniformly chosen directed edge of $G$ starts in $\Pi(T)$ and ends in $\Pi(T^{\prime})$. Clearly, $M$ is a symmetric matrix with non-negative entries that sum to 1. Also, the marginal of $M$ along either the rows or columns is $\pi$. A crucial observation is that if $T\cap T^{\prime}\neq\emptyset$ then $M(T,T^{\prime})=0$. Indeed, in this case both $\Pi(T)$ and $\Pi(T^{\prime})$ lie in the common independent set $I_{G,i}$ for any $i\in T\cap T^{\prime}$, and thus, there cannot be any edges joining $\Pi(T)$ to $\Pi(T^{\prime})$.

Conversely, suppose we begin with an ordered partition $\Pi$ as above that induces an edge profile $M$ on $G$. If the edge profile satisfies the constraints $M(T,T^{\prime})=0$ whenever $T\cap T^{\prime}\neq\emptyset$ then the $k$-tuple of subsets $(I_{G,1},\ldots,I_{G,k})$ of $V(G)$ corresponding to $\Pi$ will be independents sets in $G$. Indeed, for any $i$, the number of edges of $G$ that have both endpoints in $I_{G,i}$ is $(nd)/2\sum_{(T,T^{\prime}):i\in T\cap T^{\prime}}M(T,T^{\prime})=0$. In this case the density profile $\rho$ of $(I_{G,1},\ldots,I_{G,k})$ is given by (3.2) with $\pi$ being the marginal of $M$ along its rows.

With this terminology and bijection in mind let $Z(\rho)=Z(\mathcal{G},\rho)$ denote the number of $k$-tuples of independent sets in $\mathcal{G}$ with density profile $\rho$. Let $Z(\rho,M)$ denote the number of ordered partitions of $\mathcal{G}$ into $2^{k}$ cells such that the partitions induce the edge profile $M$, and $M$ is compatible with $\rho$ in the following sense. The marginal, $\pi$, of $M$ along its rows is given by $\rho$ via (3.1), and $M(T,T^{\prime})=0$ whenever $T\cap T^{\prime}\neq\emptyset$. It is clear from the discussion above that

where the sum is over all $M$ that is compatible with $\rho$.

Given the setup as above, define the entropies

The term $\rm{poly}(n,d,M_{\min})$ is a polynomial in $n,d$, and $\frac{1}{M_{\min}}$ where $M_{\min}=\min\{M(T,T^{\prime}):M(T,T^{\prime})>0\}$. The degree of this polynomial is bounded by a function of $k$ (at most $4^{k}$).

To compute the expectation we sum the probabilities of outcomes where each outcome uniquely specifies a pairing of half-edges in the configuration model that gives rise to a partition $\Pi$ with edge profile $M$. To specify such an outcome, do the following.

Partition the vertex set $[n]$ into $2^{k}$ distinguishable cells $\Pi(T),\;T\subset[k]$ with $|\Pi(T)|=n\pi(T)$.

Given the partition $\Pi$ from (1), and each subset $T\subset[k]$, partition the $nd\pi(T)$ half-edges attached to the vertices of $\Pi(T)$ into $2^{k}$ distinguishable cells $\Pi(T,T^{\prime}),T^{\prime}\subset[k],$ such that $|\Pi(T,T^{\prime})|=ndM(T,T^{\prime})$.

For each pair $\{T,T^{\prime}\}$ with $T\neq T^{\prime}$ pair up the half-edges from $\Pi(T,T^{\prime})$ with those from $\Pi(T^{\prime},T)$ in a specific way. Then for each $T$ pair the half-edges from $\Pi(T,T)$ with themselves in a specific way.

Each outcome has probability $1/(nd-1)!!$ from definition of the configuration model. We compute the number of outcomes in the following. But first, we should mention some conventions that we use in the following calculations. For an even integer $m\geq 2$ we denote $(m-1)!!=(m-1)(m-3)\cdots 1$, and if $m=0$ then $(m-1)!!=1$. Also, note that in any valid edge profile $M$ the quantities $ndM(T,T^{\prime})$ have to be non-negative integers. Furthermore, $ndM(T,T)$ has to be even for every $T$ because for any $G\in G_{n,d}$ the number of half edges from $\Pi(T)$ to itself is twice the number of edges present in the subgraph of $G$ induced by $\Pi(T)$. We may assume that $M$ has all these properties. We now compute the number of outcomes.

The number of partitions of $[n]$ that satisfies the properties in (1) above is the multinomial coefficient

Given a partition $\Pi$ satisfying (1) from above, the number of partitions of the half-edges that satisfy the properties in (2) is

Given the two partitions arising from (1) and (2), the number of pairings that satisfy (3) is

Now we do the asymptotics in $n$ by using Stirling’s approximation of $m!\sim\sqrt{2\pi m}(m/e)^{m}$. More precisely, $\sqrt{2\pi m}(m/e)^{m}\leq m!\leq(1+\frac{1}{12m})\sqrt{2\pi m}(m/e)^{m}$. Also, for an even integer $m$, $(m-1)!!=\frac{m!}{2^{m/2}(m/2)!}$. In the following we need to consider only those values of $\pi(T)$ and $M(T,T^{\prime})$ that are strictly positive. We begin by simplifying the term

After incorporating the remaining two terms we see that the expectation is

Using Stirling’s approximation we can verify that (with universal constants)

Let $M=[M(T,T^{\prime})]_{\{T,T^{\prime}\subset[k]\}}$ be an edge profile matrix with the property that $M$ is symmetric, the support of $M$ is contained in the set $\{(T,T^{\prime}):T\cap T^{\prime}=\emptyset\}$ and that the marginal of $M$ along its row is a fixed probability distribution $\pi=(\pi(T);T\subset[k])$. Define the weights

With a matrix $M$ and vectors $\pi,w$ as above we have

Set $h(x)=-x\log(x)$ for $0\leq x\leq 1\;(0\log 0=0)$. Note that $h(x)$ is a smooth and strictly concave function on its domain. We have that

For the second equality we used that $h(xy)=xh(y)+yh(x)$.

By Jensen’s inequality applied to $h(x)$ and the identity (3.4) we deduce that

Using Lemma 3.2 and Theorem 3.1 we conclude that for any density profile $\rho$

where $\hat{H}(\pi)=\sum_{T}\pi(T)\log(w(T))$, and $\rm{poly}(n,d)$ is a polynomial in $n$ and $d$ of degree at most $4^{k}$.

For the purposes of our analysis we will be interested in density profiles $\rho$ such that $\rho(T)\in[\rho_{|T|}-\epsilon,\rho_{|T|}]$ with $\rho_{i}=\alpha_{i,d,p}\frac{\log d}{d}$. To this end let us fix $1=\rho_{0}\geq\rho_{1}\geq\ldots\geq\rho_{k}$ with $\rho_{i}=\alpha_{i,d,p}\frac{\log d}{d}$. Define the density profile $\rho$ by $\rho(T)=\rho_{|T|}$ for $T\subset[k]$. Let $\pi$ denote the probability distribution associated to $\rho$ as given by (3.1). For $T\neq\emptyset$ define the quantities $\beta(T)$ by $\pi(T)=\beta(T)\frac{\log d}{d}$. Note that $\pi(\emptyset)=1-[\sum_{T\neq\emptyset}\beta(T)]\frac{\log d}{d}$. By setting $\alpha(T)=\alpha_{|T|,d,p}$ and using the relation between $\rho$ and $\pi$ from (3.1) and (3.2) we conclude the following relation between $\alpha$ and $\beta$:

From the fact that $\alpha\leq 2$ we see that $0\leq\alpha_{k,d,p}\leq\cdots\leq\alpha_{1,d,p}\leq 2$. From (3.7) it follows that $\beta(T)\leq 2^{k+1}$ for all $T\subset[k]$. In particular, this estimate is uniform in $d$ and $p$.

With $\pi$, $\alpha$ and $\beta$ as above we have that

where the big $O$ term depends only on $k$.

We need the asymptotic behaviour of $H(\pi)-\frac{d}{2}\hat{H}(\pi)$ where the entries of $\pi$ are on the scale of $(\log d)/d$. By definition,

From Taylor expansion we observe that $-\log(1-x)\geq x$. Hence for $T\neq\emptyset$ we have

To analyze $H(\pi)$ we consider the terms $h(\pi(\emptyset))$ and $h(\pi(T))$ with $T\neq\emptyset$ separately. We note from Taylor expansion that $h(1-x)\leq x$ for $0\leq x\leq 1$. Thus,

Since $\beta(T)\leq 2^{k+1}$ for $T\neq\emptyset$, we see that $h(\pi(\emptyset))=O_{k}(\frac{\log d}{d})$.

On the other hand, for $T\neq\emptyset$ the quantity $h(\pi(T))$ equals

The inequality follows because $h(\frac{\log d}{d})\leq\frac{\log^{2}d}{d}$ and $h(x)\leq 1/e$ for all $x\geq 0$.

Therefore, $H(\pi)\leq\frac{\log^{2}d}{d}\sum_{T\neq\emptyset}\beta(T)+O_{k}(\frac{\log d}{d})$.

Finally, it follows by inclusion-exclusion that

The details are as follows. From the relations between $\alpha$ and $\beta$ in (3.7) and (3.6) it follows immediately that

because both terms equal $(|\cup_{i=1}^{k}I_{G,i}|/n)\cdot\frac{d}{\log d}\,$.

Also, from these relations it follows that $\alpha(T)^{2}=\sum_{(T_{1},T_{2}):T\subset T_{1}\cap T_{2}}\beta(T_{1})\beta(T_{2})$. Hence,

Now recall the binomial identity $\sum_{i=1}^{t}(-1)^{i-1}\binom{t}{i}=1-(1-1)^{t}=1$ for any integer $t\geq 1$. This identity implies that

With this the proof of the final claim is complete. ∎

Let $E_{d,p}(\epsilon)=E(\alpha,\epsilon,n,d,p)$ be the event that $\mathcal{G}_{n,d}$ contains some $k$-tuple of independent sets $(I_{1},\ldots,I_{k})$ whose density profile $\rho$ satisfies the property that for every $T\subset[k]$,

The error term $\rm{err}_{d,k}$ is such that $\rm{err}_{d,k}(\epsilon)\to 0$ as $\epsilon\to 0$, and this holds uniformly in $p\in$. This follows from the fact that $\pi$ is obtained from $\rho$ by a smooth transformation (see (3.1)), and that $H$ and $\hat{H}$ are smooth functions. The reason $\rm{err}_{d,k}(\epsilon)$ tends to 0 uniformly in $p$ is because it depends on the $\alpha_{i,d,p}$ smoothly and only through their absolute values. However, the $\alpha_{i,d,p}$ are all bounded as $0\leq\alpha_{k,d,p}\leq\cdots\leq\alpha_{1,d,p}=\alpha\leq 2$. A careful analysis will actually show that $\rm{err}_{d,k}(\epsilon)=O_{k}(\frac{\log^{2}d}{d}\,\epsilon)$.

From Lemma 3.3 applied to $\rho_{\alpha}$ it follows that for any admissible $\rho$ for the occurrence of the event $E_{d,p}(\epsilon)$,

For any $G\in G_{n,d}$ the independent sets $I_{G,1},\ldots,I_{G,k}$ satisfy the following with $C_{r,d}=O(r^{2}d^{2r})$:

For each $T\subset[k]$ the set $\cap_{i\in T}I_{G,i}$ is a function of $y=(y(v);v\in V(G))$, where each $y(v)\in^{k+1}\times\{0,1\}$ (the set of values of the random variable $Y(v)$). Modifying some entry $y(v)$ to $y^{\prime}(v)$ can switch the state of inclusion of a vertex $u$ within $\cap_{i\in T}I_{G,i}$ only if $u$ is in $N_{G}(r,v)$, where $r$ is the radius of the factor associated to $I_{d}$. Therefore, such a modification to $y$ can cause the size of $\cap_{i\in T}I_{G,i}$ to change by at most $|N_{G}(r,v)|=O(rd^{r})$ since $G$ is $d$-regular. Since the random input $Y$ is an i.i.d. process it follows from the Hoeffding–Azuma inequality [2, Theorem 1.20] that

The lemma follows by taking an union bound over $T\subset[k]$ and replacing $x$ by $n\epsilon$. ∎

Recall that for the random graph $\mathcal{G}_{n,d}$ we have

Therefore, the event $E_{d,p}$ occurs for $n\geq n_{d}$ (see the definition of $E_{d,p}$ in (3.8)). From Lemma 3.4 we conclude that for $n\geq n_{d}$,

For each $d$ we pick a $p^{\prime}=p^{\prime}(d)$ such that

Local algorithms for independent sets in Erdős-Rényi graphs

Let $\Lambda_{r}$ denote the collection of all triples $(H,v,x)$ where (1) $(H,v)$ is a finite, connected, rooted graph with root $v$, (2) for all vertices $u\in V(H)$ we have $dist(u,v)\leq r$ where $dist$ denotes the graph distance, and (3) $x\in^{V(H)}$ is a labelling of $H$. $\Lambda_{r}$ has a natural $\sigma$-algebra, $\Sigma_{r}$, generated by sets of the form $(H,v)\times B$ where $(H,v)$ satisfies properties (1) and (2) above and $B$ is a Borel measurable subset of $^{V(H)}$. We consider two rooted graphs to be isomorphic if there exists a graph isomorphism between them that maps one root to the other. Given an isomorphism $\phi:(H,v)\to(H^{\prime},v^{\prime})$, any labelling $x$ of $(H,v)$ induces a labelling $\phi\cdot x$ of $(H^{\prime},v^{\prime})$ by defining $\phi\cdot x(i)=x(\phi^{-1}(i))$, and vice-versa. A function $f:\Lambda_{r}\to\{0,1\}$ is a factor if it is $\Sigma_{r}$ measurable and $f(H,v,x)=f(\phi(H),\phi(v),\phi\cdot x)$ for all isomorphisms $\phi$ of $H$, and all $H$.

The limit $\lim_{\lambda\to\infty}\alpha(\lambda)=1$.

In Section 4.1 we prove that $\limsup_{\lambda\to\infty}\alpha(\lambda)\leq 1$, and in Section 4.2 that $\liminf_{\lambda\to\infty}\alpha(\lambda)\geq 1$. The proof of the upper bound will employ the strategy used for regular trees in Section 2. We will highlight the key differences but be brief with parts of the argument that are analogous to the case for regular trees.

To prove that $\limsup\alpha(\lambda)\leq 1$ we assume to the contrary. Then we can find $\alpha>1$ and a subsequence of $\lambda\to\infty$ such that for each $\lambda$ there exists a factor of i.i.d. independent set $I_{n,\lambda}$ of $G_{n}$ with factor $f_{n,\lambda}:\Lambda_{r_{\lambda}}\to\{0,1\}$, and $E{|I_{n,\lambda}|/n}\geq\alpha\frac{\log\lambda}{\lambda}$ for all sufficiently large $n$. We can assume w.l.o.g. that these statements hold for all $\lambda$ and $n$. By setting $E{|I_{n,\lambda}|/n}=\alpha_{1,n,\lambda}\frac{\log\lambda}{\lambda}$ we have that $\alpha_{1,n,\lambda}\geq\alpha>1$.

For $0\leq p\leq 1$ let $S=S_{n,p}$ be a random subset of $V(G_{n})$ chosen by doing a Bernoulli percolation with density $p$. Let $G^{\prime}_{n}=G^{\prime}_{n}(G_{n},S)$ be the random graph that is obtained from $G_{n}$ by independently resampling the edge connections between each pair of vertices $\{u,v\}\subset S$ with inclusion probability $\lambda/n$. In other words, $G^{\prime}_{n}$ retains all edges of $G_{n}$ that do not connect $S$ to itself, and all possible edge connections between vertices within $S$ are resampled according to the Erdős-Rényi model. Note that $G^{\prime}_{n}$ is also distributed according to $ER(n,\lambda/n)$; if $p=0$ then $G^{\prime}_{n}=G_{n}$, and if $p=1$ then $G^{\prime}_{n}$ is independent of $G_{n}$.

The following inequality holds for each $k\geq 1$

Notice that we define the new probability space on finite graphs instead of on the infinite limiting graph as we did previously for regular graphs. This coupling takes into account the randomness in the local structure of the underlying Erdős-Rényi graphs, which is not an issue for regular graphs.

Define the stability $Q_{n,\lambda,p}=Q_{n,\lambda}(G_{n},\circ,S,X)$ on the new probability space by

Indeed, let $p_{1}\leq p_{2}$. We couple the labelled graphs $(G^{1}(S_{p_{1}}),\circ,Y^{1}_{p_{1}})$ and $(G^{1}(S_{p_{2}}),\circ,Y^{1}_{p_{2}})$ given $(G_{n},\circ,X)$ through the percolation subsets. Let $Z$ be a random labelling of $[n]$, and let $\tau_{\{u,v\}}$ for $\{u,v\}\subset[n]$ be independent Bernoulli trials of expectation $\lambda/n$. Set $S_{p_{1}}=\{v:Z(v)\leq p_{1}\}$ and $S_{p_{2}}=\{v:Z(v)\leq p_{2}\}$. The resampled edges of $G^{1}(S_{p_{1}})$ (resp. $G^{1}(S_{p_{2}})$) are determined according to the $\tau_{\{u,v\}}$ for $u,v\in S_{p_{1}}$ (resp. for $u,v\in S_{p_{2}}$). Similarly, the labelling $Y^{1}_{p_{1}}$ (resp. $Y^{1}_{p_{2}}$) agrees with $X^{1}$ on $S_{p_{1}}$ (resp. $S_{p_{2}}$) and agrees with $X$ otherwise. With this coupling we have that (ignoring some formalities with the notation)

With these observations we can now proceed with the proof exactly the same way as before. We skip the remainder of the argument for brevity and prove Theorem 4.2 in the following.

1.2. Proof of Theorem 4.2

We will show that the existence of the factor of i.i.d. independent sets $I^{i}$ on the graph $G^{i}$ implies that with high probability each graph $G^{i}$ contains a subset $S^{i}$ such that $S^{i}$ is an independent set in $G^{i}$, and the empirical intersection densities of the $S^{1},\ldots,S^{k}$ are close to the quantities $\alpha_{k,n,\lambda}\frac{\log\lambda}{\lambda}$ Then we will bound the probability of observing such a $k$-tuple of independent sets, and prove that this probability is vanishingly small unless Theorem (4.2) holds.

Fix $0<\epsilon<1$. Let $A(\epsilon,p)$ be the following event. For each $1\leq i\leq k$, $G^{i}$ contains an independent set $S^{i}$ such that the density profile of $(S^{1},\ldots,S^{k})$ satisfies the following for all $T\subset[k]$:

With $G^{1},\ldots,G^{k}$ as defined and corresponding independent sets $I^{1},\ldots,I^{k}$ as defined via the factor $f_{n,\lambda}$, one has that for all $\epsilon>0$, as $n\to\infty$,

Let $\tau_{i,u,v}$ for $1\leq i\leq k$ and $\{u,v\}\subset[n]$ be the indicator of the event that the edge $\{u,v\}$ belongs to $G^{i}$. Then the random vectors $(\tau_{i,u,v};1\leq i\leq k)$ are independent of each other as $\{u,v\}$ varies. Let $S\subset[n]$ be a random subset chosen by a Bernoulli percolation with density $p$. If both $u,v\in S$ then $(\tau_{i,u,v};1\leq i\leq k)$ are independent Bernoulli trials of expectation $\lambda/n$ for each $i$. Otherwise, $(\tau_{i,u,v};1\leq i\leq k)$ satisfies $\tau_{1,u,v}=\cdots=\tau_{k,u,v}$. In the latter case all $k$ of these indicators take the value 1 with probability $\lambda/n$ or they are all zero with the complementary probability.

The sampling procedure above will allow us to compute expectations involving independent sets in the $G^{i}$. Let $I^{i}\subset[n]$ be an independent set of $G^{i}$. Defining $\rho(T)=|\cap_{t\in T}I^{t}|/n$ for $T\subset[k]$, the density profile associated to these $k$ independent sets is $\rho=(\rho(T);T\subset[k])$. The density profile $\rho$ determines a probability distribution $\pi=(\pi(T);T\subset[k])$ by equation (3.1). Let $Z(\rho)$ be the number of $k$-tuple of subsets $(I^{1},\ldots,I^{k})$ of $[n]$ such that they have density profile $\rho$ and $I^{i}$ is an independent set of $G^{i}$.

Fix a $k$-tuple $(I^{1},\ldots,I^{k})$ with each $I^{i}\subset[n]$ such that density profile of the $k$-tuple is $\rho$. Given $v\in[n]$, let $T_{v}=\{i\in[k]:v\in I^{i}\}$. Let $E_{\{u,v\}}$ be the event that the edge $\{u,v\}$ is absent is all $G^{i}$ for which $i\in T_{u}\cap T_{v}$, that is, $E_{\{u,v\}}=\{\tau_{i,u,v}=0$ for all $i\in T_{u}\cap T_{v}\}$. The subsets $I^{1},\ldots,I^{k}$ have the property that $I^{i}$ is an independent set of $G^{i}$ if and only if the events $E_{\{u,v\}}$ occur for all pairs $\{u,v\}$.

From the sampling procedure for the graphs $G^{1},\ldots,G^{k}$, we note that the events $E_{\{u,v\}}$ are independent. Conditioning on the random subset $S$ and using the sampling procedure we conclude that

Observe that $(1-\frac{\lambda}{n})^{|T_{u}\cap T_{v}|}\leq(1-\frac{\lambda}{n})^{\mathbf{1}_{\{T_{u}\cap T_{v}\neq\emptyset\}}}$. Therefore, no matter the outcome of $S$ we have that

Recall that the probability distribution $(\pi(T);T\subset[k])$ is derived from $\rho$ from equation (3.1). To prove the equality above we begin by considering the ordered partition $\Pi$ associated to any $k$-tuple of subsets $(I^{1},\ldots,I^{k})$. The partition $\Pi$ has $2^{k}$ ordered cells $(\Pi(T);T\subset[k])$ defined by

It follows from the inclusion-exclusion principle that if $(I^{1},\ldots,I^{k})$ has the density profile $\rho$ then $|\Pi(T)|=\pi(T)n$. The point here is that since $\pi$ can be derived from $\rho$, it in fact does not depend any individual $\Pi$.

For any fixed $k$-tuple $(I^{1},\ldots,I^{k})$, the sum $\sum_{\{u,v\}}\mathbf{1}_{\{T_{u}\cap T_{v}\neq\emptyset\}}$ can be represented by accounting for the contribution of each pair of subsets $\{T,T^{\prime}\}$ to it.