  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}})$.
