# Large independent sets in Markov random graphs



Computing the maximum size of an independent set in a graph is a famously hard combinatorial problem that has been well-studied for various classes of graphs. When it comes to random graphs, only the classical binomial random graph $$G_{n,p}$$ has been analysed and shown to have largest independent sets of size $$\Theta(\log{n})$$ w.h.p. This classical model does not capture any dependency structure between edges that can appear in real-world networks. We initiate study in this direction by defining random graphs $$G^{r}_{n,p}$$ whose existence of edges is determined by a Markov process that is also governed by a decay parameter $$r\in(0,1]$$. We prove that w.h.p. $$G^{r}_{n,p}$$ has independent sets of size $$(\frac{1-r}{2+\epsilon}) \frac{n}{\log{n}}$$ for arbitrary $$\epsilon > 0$$, which implies an asymptotic lower bound of $$\Omega(\pi(n))$$ where $$\pi(n)$$ is the prime-counting function. This is derived using bounds on the terms of a harmonic series, Tur\'an bound on stability number, and a concentration analysis for a certain sequence of dependent Bernoulli variables that may also be of independent interest. Since $$G^{r}_{n,p}$$ collapses to $$G_{n,p}$$ when there is no decay, it follows that having even the slightest bit of dependency (any $$r < 1$$) in the random graph construction leads to the presence of large independent sets and thus our random model has a phase transition at its boundary value of $$r=1$$. For the maximal independent set output by a greedy algorithm, we deduce that it has a performance ratio of at most $$1 + \frac{\log{n}}{(1-r)}$$ w.h.p. when the lowest degree vertex is picked at each iteration, and also show that under any other permutation of vertices the algorithm outputs a set of size $$\Omega(n^{1/1+\tau})$$, where $$\tau=1/(1-r)$$, and hence has a performance ratio of $$O(n^{\frac{1}{2-r}})$$.