  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
Erd\H{o}s-R\'enyi-Gilbert 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}})$.
