Large independent sets in Markov random graphs

Computing the maximum size of an independent set in a graph is a famously hard combinatorial problem. There have been many analyses for the classical binomial random graph model of Erd\"os-R\'enyi-Gilbert and as a result, tight asymptotic bounds are known for these graphs. However, this classical model does not capture any dependency structure between edges that is widely prevalent in real-world networks. We initiate study in this direction by considering random graphs whose existence of edges is determined by a Markov process that is also governed by a decay parameter $\delta\in(0,1]$. We prove that the maximum size of an independent set in such an $n$-vertex random graph is with high probability lower bounded by $(\frac{1-\delta}{2+\epsilon}) \pi(n)$ for arbitrary $\epsilon > 0$, where $\pi(n)$ is the prime-counting function, and upper bounded by $c_{\delta} n$, where $c_{\delta} := e^{-\delta} + \delta/10$ is an explicit constant. Since our random graph model collapses to the classical binomial random graph model when there is no decay (i.e., $\delta=1$) and the latter are known to have independent sets roughly be of size no more than $\log{n}$, it follows from our lower bound that having even the slightest bit of dependency 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. We also prove that a greedy algorithm for finding a maximal independent set gives w.h.p. an output of size $\Omega(n^{1/(1+\tau)})$ where $\tau=\lceil 1/(1-\delta) \rceil$.