\(\)
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}})\).